有人可以帮忙解释这个C one liner的作用吗？

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的最接近的幂.OR部分将所有低位设置为最高位以下,因此它最终为2减去1的幂,然后再添加一个.它看起来有点优化,因此不太可读; 通过按位运算和单独的位移,以及作为宏(因此没有函数调用开销)来完成它.

Answer 2

按位或移位操作基本上设置最高设置位和位0之间的每个位.这将产生一些形式2^n - 1.最后的增量增加一个来获得一些表格2^n.初始递减确保您不会将已经为2的幂的数字舍入到下一个幂,因此例如2048不会变为4096.

Answer 3

在我的机器上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

由于某种原因,我没有在GCC的标准头文件中找到scan_msb(例如#define scan_msb(x) if (__builtin_constant_p (x)) ...)的适当实现(仅限__TBB_machine_lg/__TBB_Log2).