是否存在非迭代且更高效的第N个置位比特位索引查找方法？

你提到的迭代实现代码如下：

#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(0b101001000, 0) = 3
pos_of_nth_bit(0b101001000, 1) = 6
pos_of_nth_bit(0b101001000, 2) = 8

确实存在非迭代且性能更优的实现方式，以下是几种实用方案：

1. 内置函数+二分查找 #

通过__builtin_popcountll（统计二进制中1的个数）配合二分法，快速定位第N个置位的位置：

#include <cassert>
#include <cstdint>

uint64_t pos_of_nth_bit(uint64_t X, uint64_t bit) {
    assert(bit < __builtin_popcountll(X));
    
    uint64_t low = 0, high = 63;
    while (low < high) {
        uint64_t mid = (low + high) / 2;
        uint64_t cnt = __builtin_popcountll(X & ((1ULL << (mid + 1)) - 1));
        if (cnt > bit) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

该方法时间复杂度为O(log64)，比迭代的O(k)（k为置位个数）更稳定，置位数量较多时性能优势明显。

2. BMI2指令集原生实现（x86平台） #

如果目标平台支持BMI2指令集，可直接利用硬件指令实现单周期级操作：

#include <cassert>
#include <cstdint>
#include <immintrin.h>

uint64_t pos_of_nth_bit(uint64_t X, uint64_t bit) {
    assert(bit < __builtin_popcountll(X));
    uint64_t mask = 1ULL << bit;
    uint64_t target = _pdep_u64(mask, X);
    return __builtin_ctzll(target);
}

_pdep_u64会将mask中的1填充到X的置位位置，得到的target仅保留第N个置位对应的1，再用__builtin_ctzll获取其索引，性能接近理论最优。

3. 分块预计算查找表（高频调用场景） #

若需极端性能，可按16位等小粒度分块预计算置位位置表，组合得到最终结果。这种方式内存占用可控，适合频繁调用的场景，但实现复杂度稍高。

内容的提问来源于stack exchange，提问作者Tyker