有没有一种非迭代的方法来查找第 N 个集合位的索引？[复制]-解网

问：

9天前关闭。

#include <cassert>
#include <cstdint>

uint64_t pos_of_nth_bit(uint64_t X, uint64_t bit) {
  while (X) {
    if (!bit--)
      return __builtin_ctzll(X);
    X = X & (X - 1);
  }
  assert(false && "no such bit");
}

有没有更快的方法来做逻辑？pos_of_nth_bit

例如：

pos_of_nth_bit(0b101001000, 0) = 3
pos_of_nth_bit(0b101001000, 1) = 6
pos_of_nth_bit(0b101001000, 2) = 8

C++ C 位操作

这个问题不值得投票否决。该代码清楚地表明了所询问的内容，因为关闭了最低的设定位，因此循环正在计算设定的位。虽然不是每个人都能意识到这关闭了最低设定的位，但这个问题是被标记的，如果他们不熟悉这个基本的位操作习语，就应该对投票位操作问题保持克制。X & (X-1)X & (X - 1)bit-manipulation

4赞 harold 11/14/2023

这是 Rank-Select 的一部分，所以是一个相对深入研究的问题。例如：Select 的快速 x86 实现select

答：

0赞 Jerry Coffin 11/14/2023 #1

至少如果我们把答案限制在普通的硬件和相当实用的解决方案上，你几乎肯定会被困在一些迭代中。

不切实际的明显 O（1）解决方案是查找表。它不切实际的原因是，对于 M 位输入，第 N 个设置位位置的查找表将需要一个包含 N * 2 M 个条目的查找表（如果每个条目的大小需要为_{log 2}（^M）位）。对于 64 位输入，我很确定这比历史上产生的内存还要多。

但是，在保持查找表大小相当合理的同时，大幅减少最大迭代次数是很容易的。例如，我们可以查找一个字节中设置的位数，只有一个 256 个条目的表。这样，我们最多执行 8 次表查找以隔离一个包含第 i 个设置位的字节，然后在该字节内进行 8 次迭代以找到正确的位。这会将最坏情况从 64 次迭代减少到 16 次迭代（预期平均值从 32 次减少到 8 次左右）。查找表足够小，几乎可以容纳任何具有缓存的 CPU 的 L1 缓存，因此访问它通常非常快。

有没有一种非迭代的方法来查找第 N 个集合位的索引？[复制]

is there a non-iterative way of finding the index of the Nth set bit? [duplicate]

评论

评论