高效查找比特掩码中第n个置位比特的索引

针对你的需求，这里有两种更高效的实现方案，比你当前的循环方法更快：

1. 基于BMI2指令集的硬件加速方案（最优） #

如果你的目标CPU支持BMI2指令集（大部分2013年后的x86处理器都支持），可以用GCC内置的__builtin_ia32_pdep_u32（32位）或__builtin_ia32_pdep_u64（64位）函数，这是单条硬件指令，直接完成位展开操作，效率拉满。

实现代码：

#include <stdint.h>

// 查找32位掩码中第n个1的索引（n从0开始计数）
uint32_t find_nth_set_bit(uint32_t mask, uint32_t n) {
    // 先校验n的合法性：n必须小于掩码中1的总数
    if (n >= __builtin_popcount(mask)) {
        // 这里可以返回错误值，比如-1或者做其他处理
        return (uint32_t)-1;
    }
    // 构造只有第n位为1的选择器
    uint32_t selector = 1U << n;
    // 用PDEP将选择器的1映射到原掩码的置位位置上
    uint32_t target_bit = __builtin_ia32_pdep_u32(selector, mask);
    // 返回该位的索引
    return __builtin_ctz(target_bit);
}

// 64位版本
uint64_t find_nth_set_bit_64(uint64_t mask, uint64_t n) {
    if (n >= __builtin_popcountll(mask)) {
        return (uint64_t)-1;
    }
    uint64_t selector = 1ULL << n;
    uint64_t target_bit = __builtin_ia32_pdep_u64(selector, mask);
    return __builtin_ctzll(target_bit);
}

原理：PDEP指令会把selector中的1填充到mask中所有为1的位位置上，最终得到的target_bit只会保留原掩码中第n个1的位置，再用__builtin_ctz取最低位索引即可。

2. 无BMI2支持时的二分查找优化方案 #

如果平台不支持BMI2，用二分查找替代逐个清除位的循环，最多只需要log2(位数)次迭代（32位是5次，64位是6次），比原循环高效得多。

32位实现代码：

#include <stdint.h>

uint32_t find_nth_set_bit(uint32_t mask, uint32_t n) {
    uint32_t total_bits = __builtin_popcount(mask);
    if (n >= total_bits) {
        return (uint32_t)-1;
    }

    uint32_t half = 16; // 32位的中间分割点
    while (half > 0) {
        // 取掩码的高half位
        uint32_t hi_part = mask >> half;
        uint32_t hi_count = __builtin_popcount(hi_part);
        if (hi_count > n) {
            // 目标位在高half位，更新掩码为高half位
            mask = hi_part;
        } else {
            // 目标位在低half位，减去高half位的1的数量，掩码保留低half位
            n -= hi_count;
            mask &= ((1U << half) - 1);
        }
        half >>= 1;
    }
    // 最终掩码只剩目标位，取索引
    return __builtin_ctz(mask);
}

这个方法通过不断将掩码分成两半，判断目标位在高半区还是低半区，快速缩小范围，避免了逐个遍历每一位的开销。

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