用于计数位或找到最右边|最左边的高效按位运算 [英] Efficient bitwise operations for counting bits or find the right|left most ones

问题描述

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

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.

这篇关于用于计数位或找到最右边|最左边的高效按位运算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！