用于计数位的高效按位运算或找到最右侧的位

Question

给定unsigned int,我必须执行以下操作:

1. 计算设置为1的位数
2. 找到最左边1位的索引
3. 找到最右边1位的索引

(该操作不应该是架构依赖).

我已经使用按位移位完成了这个,但我必须迭代几乎所有的位(es.32).例如,计算1:

unsigned int number= ...;
while(number != 0){
    if ((number & 0x01) != 0)
        ++count;
    number >>=1;
}

其他操作类似.

所以我的问题是:有没有更快的方法呢？

Answer 1

如果您想要最快的方式,则需要使用非便携式方法.

在Windows/MSVC:

• _BitScanForward()
• _BitScanReverse()
• __popcnt()

GCC:

• __builtin_ffs()
• __builtin_ctz()
• __builtin_clz()
• __builtin_popcount()

这些通常直接映射到本机硬件指令.所以它没有比这些快得多.

但由于它们没有C/C++功能,因此只能通过编译器内在函数访问它们.

Answer 2

看看ffs(3),ffsl(3),fls(3),flsl(3).

ffs()和ffsl()函数在i中找到第一个位集(从最低有效位开始)并返回该位的索引.

fls()和flsl()函数在i中找到最后一位,并返回该位的索引.

您可能也对bitstring(3)感兴趣.

Answer 3

从http://graphics.stanford.edu/~seander/bithacks.html引用

计数32位整数v中的位的最佳方法如下：

unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here
v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

最佳位计数方法仅需执行12个操作，与查找表方法相同，但避免了表的内存和潜在的高速缓存未命中。尽管它不使用64位指令，但它是上面的纯并行方法与使用乘法的早期方法（在有关使用64位指令对位计数的部分中）的混合体。字节中设置的位的计数是并行进行的，字节中设置的位的总和是通过乘以0x1010101并右移24位来计算的。