有没有一种快速的方法来获取二进制值中等于 1 的位的索引？

Question

我想得到二进制格式等于1的索引，现在我使用这样的代码：

inline static uint8_t the_index(uint32_t val){
  return uint8_t(log(val & ((~val) + 1))/log(2));
}

我想知道是否有其他方法可以达到同样的目的？有没有可能用位运算来解决这个问题？

我这样做是为了迭代一个值并构建一些取决于迭代位置的操作，伪代码如下：

 while (temp) {
            auto cur_index = the_index(temp);
            auto window = ((1 << i) - 1) << cur_index;
            if (((temp & window) ^ window) == 0) {
              //....do something
            }
            temp &= temp - 1;
        }

Answer 1

如果问题是关于查找值中单个位的索引，比如 uint32_t x = b000010000;，一个快速的方法是

auto index = builtin_popcount(x - 1);

// example: b000010000 - 1
//          b000001111
// popcount(b000001111) == 4

在 arm64 架构中，最好的方法是使用 count_leading_zero(x) instruction/operation，因为通用寄存器缺乏快速弹出计数。

更仔细地阅读 OP，不能保证 x 只设置了一位——问题似乎是找到最低有效位集的索引。可以用

隔离

 x = temp & (0-temp);

Answer 2

有一个标准函数：

auto cur_index = std::countr_zero(temp);

在我的系统上，编译为：

xor     eax, eax
tzcnt   eax, edi

请注意，无论输入是否恰好有一个设置位，此函数都会成功地从右到第一个位计算零位。

Answer 3

我建议您使用 __builtin_ctzl : Returns x 中尾随 0 位的数量，从最低有效位开始。（警告：如果 x 为 0，则结果未定义）。

示例：__builtin_ctzl(0x10) = 4，__builtin_ctzl(0x20) = 5

对于你的情况，你可以像这样使用它：

unsigned index;
do {
    index = temp ? __builtin_ctzl(temp) : 0;
    ... //do your stuff
    temp -= pow(2, index);
} while (index);

有没有一种快速的方法来获取二进制值中等于 1 的位的索引？

Is there a fast way to get the index of bit which equal 1 in a binary value?

c++

algorithm

bit-manipulation

bitwise-operators