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

Обычно я могу найти большинство 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, но это касается моих знаний.

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

Спасибо

Ответы

Ответ 1

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

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

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

Ответ 2

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

Ответ 3

На моей машине kroundup32 дается 6.000 м раундов/сек
И следующая функция дает 7,693 м раундов/сек

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).