GCC 位扫描向前查找下一个设置位？

Question

我有一个 uint64_t，我想找到第一个设置位的索引，将其重置为零并找到下一个设置位。

我怎么知道什么时候终止？全零的 BSF 未定义...

const uint64_t input = source;

if(0 != input){

    int32_t setIndex = GCC_BSF_INTRINSIC(input);

    while(setIndex != UNDEFINED???){

        //Do my logic

        //Reset
        input[setIndex] = 0;

        setIndex = BSF_Variant(input);
    }
}

有人可以帮忙吗？

Answer 1

最简单的方法就是检查输入：

while (input) {
    int32_t index = __builtin_ffsll(input);
    // do stuff
}

更复杂，根据文档 the docs:

— Built-in Function: int __builtin_ffs (int x)
Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.

你可以这样做：

for (int index  = __builtin_ffsll(input); 
     index; 
     index = __builtin_ffsll(input))
{
    // do stuff
}

它完成了同样的事情，你只需要重复 __builtin_ffsll 调用，所以它更冗长，在我看来无助于清晰。

Answer 2

使用__builtin_ffs时要记住的2点：

为了得到下一位，您需要清除最近找到的位
如果您打算将结果用于移位或 table 索引，您很可能需要将其减一。

while (m) {
    // Get the rightmost bit location. 

    int BitOffset = __builtin_ffs(m);

    // Clear the bit before the next iteration. 
    // Used in the loop condition.

    m = (m >> BitOffset) << BitOffset;

    // Do your stuff .....
}

GCC 位扫描向前查找下一个设置位？

GCC Bit-scan-forward to find next set bit?

c++

gcc

bit-manipulation

bit