C 中的位旋转：如何从 2^N 转换为 N？

Question

将 [2^N,2^(N-1)-1] 范围内的数字转换为 N 的良好位操作例程是什么？

一些例子：

• f(1) -> 0
• f([2-3]) -> 0 f([2-3]) -> 1
• f([4-7])→ 2
• f([8-15])→ 3

这是一种实现：

uint f(uint num)
{
    for (uint shifts = 0; num; shifts++) 
        num >>= 1;
    return (shifts - 1);
}

Answer 1

作为最通用的方法，二分搜索可能会有所帮助。对于值 0..31，仅需要 5 个阶段。

y = 0;
if(x >= 0x10000<<y) y += 0x10;
if(x >= 0x100<<y) y += 0x08;
if(x >= 0x10<<y) y += 0x04;
if(x >= 0x4<<y) y += 0x02;
if(x >= 0x2<<y) y += 0x01;

Answer 2

在此页面上查看计算以 2 为底的对数（或前导零计数，它们是相同的）的 hack：http://www-graphics.stanford.edu/~seander/bithacks.html

您还可以发现有用的函数__builtin_clz（或_BitScanReverse 对于 VS) 对于 x86。

Answer 3

根据您的数据类型的宽度以及可用内存的大小，查找表是一种可能性。这几乎肯定是最快的方法。

有关其他方法，请参阅 http://www-graphics.stanford.edu/~ seander/bithacks.html#IntegerLogObvious 以及后续部分。