Может кто-нибудь помочь объяснить, что делает этот лайнер C?

Question

Обычно я могу понять большую часть кода на C, но этот у меня над головой.

#define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))

пример использования будет выглядеть примерно так:

int x = 57;
kroundup32(x);
//x is now 64

Несколько других примеров:

от 1 до 1
от 2 до 2
от 7 до 8
от 31 до 32
от 60 до 64
от 3000 до 4096

Я знаю, что это округлениецелое число с точностью до ближайшей степени 2, но это все, что мне известно.

Любые объяснения будут с благодарностью.

Спасибо

Answer 1

(--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))

1. Уменьшить x на 1
2. ИЛИ x с (x / 2).
3. ИЛИ x с (x / 4).
4. ИЛИx с (x / 16).
5. ИЛИ x с (x / 256).
6. ИЛИ x с (x / 65536).
7. Увеличение x на 1.

Для 32-разрядного целого числа без знака это должно сдвинуть значение до ближайшей степени 2, равной или большей.Секции ИЛИ устанавливают все младшие биты ниже старшего бита, так что он получается как степень 2 минус один, затем вы добавляете один обратно в него.Похоже, что это несколько оптимизировано и поэтому не очень читабельно;делать это с помощью побитовых операций и сдвига битов в одиночку, а также в виде макроса (поэтому нет необходимости в вызове функции).

Answer 2

На моей машине kroundup32 дает 6.000m раундов / сек
А следующая функция дает 7.693m раундов / сек

inline int scan_msb(int x)
{
#if defined(__i386__) || defined(__x86_64__)
    int y;
    __asm__("bsr %1, %0"
            : "=r" (y)
            : "r" (x)
            : "flags"); /* ZF */
    return y;
#else
#error "Implement me for your platform"
#endif
}

inline int roundup32(int x)
{
    if (x == 0) return x;
    else {
        const int bit = scan_msb(x);
        const int mask = ~((~0) << bit);
        if (x & mask) return (1 << (bit+1));
        else return (1 << bit);
    }
}

Так что @thomasrutter я не скажу, что он "высокооптимизирован"".

И соответствующая (только значимая часть) сборка (для GCC 4.4.4):

kroundup32:
    subl    $1, %edi
    movl    %edi, %eax
    sarl    %eax
    orl %edi, %eax
    movl    %eax, %edx
    sarl    $2, %edx
    orl %eax, %edx
    movl    %edx, %eax
    sarl    $4, %eax
    orl %edx, %eax
    movl    %eax, %edx
    sarl    $8, %edx
    orl %eax, %edx
    movl    %edx, %eax
    sarl    $16, %eax
    orl %edx, %eax
    addl    $1, %eax
    ret

roundup32:
    testl   %edi, %edi
    movl    %edi, %eax
    je  .L6
    movl    $-1, %edx
    bsr %edi, %ecx
    sall    %cl, %edx
    notl    %edx
    testl   %edi, %edx
    jne .L10
    movl    $1, %eax
    sall    %cl, %eax
.L6:
    rep
    ret
.L10:
    addl    $1, %ecx
    movl    $1, %eax
    sall    %cl, %eax
    ret

По какой-то причине я не нашел подходящей реализации scan_msb (например, #define scan_msb(x) if (__builtin_constant_p (x)) ...) в стандартных заголовках GCC (только __TBB_machine_lg / __TBB_Log2).

Answer 3

Битовые операции или и операции сдвига по существу устанавливают каждый бит между самым старшим установленным битом и нулевым битом. Это даст номер формы 2^n - 1. Последний шаг добавляет единицу, чтобы получить число вида 2^n. Начальный декремент гарантирует, что вы не округляете числа, которые уже являются степенями от двух до следующей степени, например, 2048 не становится 4096.