有没有一种非迭代的方法来找到第N个集合位的索引？

Question

#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

Answer 1

至少如果我们将答案限制在普通硬件和相当实用的解决方案上，那么你几乎肯定会陷入some迭代。

查找表是明显不实用的 O(1) 解决方案。它不实用的原因是，对于 M 位输入，第 N 个设置位的位置的查找表将需要一个具有 N * 2^M 条目的查找表（每个 if 需要 6 位）在尺寸方面）。我很确定这比历史上产生的记忆还要多。

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