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

Question

在2^ N，2^(N1)-1到N的范围内，什么是好的位旋转例程？

下面是一些例子：

• f(1) -> 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

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

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

Answer 2

作为最一般的方法，二进制搜索可能会有所帮助。对于值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 3

看看这个页面中计算基数2的对数(或前导零计数，它们是相同的)的黑客：http://www-graphics.stanford.edu/~seander/bithacks.html。

您还可以找到用于__builtin_clz的函数x86 (或用于VS的_BitScanReverse )。