高效的按位运算，用于计数位或查找最右|最左的位
给定一个 unsigned int，我必须实现以下操作：
- 计算设置为 1 的位数
- 查找最左边 1 位的索引
- 查找最右边 1 位的索引
（该操作不应依赖于体系结构） 。
我已经使用按位移位完成了此操作，但我必须迭代几乎所有位(es.32) 。 例如计数1：
unsigned int number= ...;
while(number != 0){
if ((number & 0x01) != 0)
++count;
number >>=1;
}
其他操作类似。
所以我的问题是：有没有更快的方法来做到这一点？
Given an unsigned int, I have to implement the following operations :
- Count the number of bits set to 1
- Find the index of the left-most 1 bit
- Find the index of the righ-most 1 bit
(the operation should not be architecture dependents).
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;
}
The others operation are similar.
So my question is: is there any faster way to do that?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
如果您想要最快的方式，您将需要使用不可移植的方法。
Windows/MSVC：
GCC：
这些通常直接映射到本机硬件指令。所以它不会比这些快得多。
但由于它们没有 C/C++ 功能，因此只能通过编译器内在函数来访问它们。
If you want the fastest way, you will need to use non-portable methods.
Windows/MSVC:
GCC:
These typically map directly to native hardware instructions. So it doesn't get much faster than these.
But since there's no C/C++ functionality for them, they're only accessible via compiler intrinsics.
看一下 ffs(3)、ffsl(3)、fls(3)、flsl(3)。
ffs() 和 ffsl() 函数查找 i 中的第一个位集（从最低有效位开始）并返回该位的索引。
fls() 和 flsl() 函数查找 i 中设置的最后一个位并返回该位的索引。
您可能也对 bitstring(3) 感兴趣。
Take a look at ffs(3), ffsl(3), fls(3), flsl(3).
The ffs() and ffsl() functions find the first bit set (beginning with the least significant bit) in i and return the index of that bit.
The fls() and flsl() functions find the last bit set in i and return the index of that bit.
You might be interested in bitstring(3), too.
引用自 http://graphics.stanford.edu/~seander/bithacks.html
Quoting from http://graphics.stanford.edu/~seander/bithacks.html
数字 x 的“最右边的 1 位”由下式给出，
例如：
最后一行的 base2-log 给出了正确的位置 + 1。因此，从对数结果中减去 1，您将得到最右边的位置‘1’位。
对于最右边的“0”位，您可以使用
"The righ-most 1 bit" of number x is given by
E.g.:
The base2-log of the last line then gives you the correct position + 1. So substract 1 from the log-result and you'll have the most-right '1' bit.
For the most-right '0' bit you may use
使用 C++20，可以使用新添加的标头
<位>。popcountcountl_onecountr_one然后，它们中的每一个都会调用编译器特定的函数，例如
__popcnt()和__builtin_popcount()。With C++20, these operations can be done easily with the newly added header,
<bit>.popcountcountl_onecountr_oneEach of them would then call compiler specific functions like
__popcnt()and__builtin_popcount().对于最右边的一点简单的答案
}
}
for rightmost bit simple ans
}
}