此问题在此处已有答案：
Find nth SET bit in an int（15个答案）
5天前关闭.
#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型
1条答案
按热度按时间o7jaxewo1#
至少，如果我们将答案限制在普通的硬件和合理实用的解决方案上，你几乎肯定会被 * 一些 * 迭代卡住。
最明显的O（1）解决方案是查找表。它不实用的原因是，对于M位输入，查找第N个设置位的位置的查找表将需要具有N * 2M个条目的查找表（每个条目的大小需要log2（M）位）。对于64位输入，我很确定这比历史上产生的内存要多。
然而，在保持查找表大小合理的情况下，减少最大迭代次数是很容易的。例如，我们可以在一个只有256个条目的表中查找一个字节中设置的位数。这样，我们最多执行8次表查找，以隔离包含第i个设置位的一个字节，然后在该字节内进行8次迭代以找到正确的位。这将最坏情况从64次迭代减少到16次迭代（以及从32到大约8的预期平均值）。查找表足够小以适合几乎任何具有高速缓存的CPU的L1高速缓存，所以访问它通常会相当快。