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

2022-01-09 00:00:00 binary c bit-manipulation bits c++

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

Given an unsigned int, I have to implement the following operations :

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

(操作不应依赖于架构).

(the operation should not be architecture dependents).

我已经使用按位移位完成了此操作，但我必须遍历几乎所有位(es.32).例如，计数 1:

I've done this using bitwise shift, but I have to iterate through almost all the bits(es.32) . For example, counting 1's:

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

其他操作类似

所以我的问题是:有没有更快的方法来做到这一点?

So my question is: is there any faster way to do that?

推荐答案

如果你想要最快的方式，你将需要使用不可移植的方法.

If you want the fastest way, you will need to use non-portable methods.

Windows/MSVC:

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

GCC:

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

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

These typically map directly to native hardware instructions. So it doesn't get much faster than these.

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

But since there's no C/C++ functionality for them, they're only accessible via compiler intrinsics.

相关文章