c++ - 用于计算位或找到最右边|最左边的位的高效按位运算

Question

给定一个无符号整数，我必须执行以下操作:

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

海湾合作委员会:

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

这些通常直接映射到 native 硬件指令。所以它不会比这些更快。

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