高效查找二进制中首个连续N位1的索引（C语言/GCC环境）

针对你需要处理1024个64位整数、快速定位首个连续N位1的需求，这里提供基于GCC内置位运算的高效方案，避免逐位移位遍历的低效问题。

核心逻辑：通过位运算快速标记连续1块 #

要定位连续N位1，核心思路是用多次按位与操作，把所有满足连续N位为1的位置标记出来，再借助GCC内置函数快速找到目标索引。具体步骤：

1. 构造掩码：从原数x开始，依次与x<<1、x<<2...x<<(N-1)做按位与。最终的掩码中，所有为1的位对应连续N位1块的最高位。
2. 偏移校正：将掩码右移N-1位，此时掩码中的1位就对应连续N位1块的最低位（和__builtin_ffs的索引计数规则一致）。
3. 提取索引：用__builtin_ffsll（64位版本的内置函数）获取偏移后掩码的最低有效1位位置，就是目标索引。

以你的示例验证：

• 输入x=0b0110010（十进制50），N=2
• 计算掩码：50 & (50<<1) = 50 & 100 = 32（二进制0b0100000，对应连续块的最高位第6位）
• 偏移校正：32 >> 1 = 16（二进制0b0010000，对应连续块的最低位第5位）
• 提取索引：__builtin_ffsll(16)返回5，完全符合预期。

通用代码实现 #

#include <stdint.h>
#include <limits.h>

// 返回首个连续N位1的最低位索引（1-based，与__builtin_ffs规则一致），无匹配则返回0
uint8_t find_first_consecutive_ones(uint64_t x, uint8_t N) {
    if (N == 0 || N > 64) return 0;
    if (N == 1) return __builtin_ffsll(x); // N=1直接复用内置函数
    
    uint64_t mask = x;
    for (uint8_t i = 1; i < N; ++i) {
        mask &= x << i;
        if (mask == 0) break; // 提前终止，已确认无符合条件的连续块
    }
    
    if (mask == 0) return 0;
    // 处理N=64的特殊情况：全1时掩码是UINT64_MAX，右移63位后是1，__builtin_ffsll返回1
    return __builtin_ffsll(mask >> (N-1));
}

批量处理的优化技巧 #

面对1024个64位整数的场景，可以进一步提升效率：

• 编译期循环展开：如果N是固定值（比如始终找连续2位1），直接把循环写成固定的位运算（如mask = x & (x<<1)），消除循环开销，GCC会自动优化。
• SIMD批量处理：利用AVX2等SIMD指令，一次处理8个64位整数。例如用_mm256_and_si256批量计算掩码，再批量提取结果，吞吐量能提升数倍。
• 提前终止判断：在循环计算掩码时，一旦掩码变为0，直接跳出循环，避免无效运算。

扩展：找最左边的连续N位1 #

如果需要找从最高位开始的第一个连续N位1（而非最低位开始的第一个），可以先反转64位整数（用GCC内置的__builtin_bitreverse64），调用上述函数得到反转后的索引，再用65 - 索引得到原数中的索引（因为1-based计数下，原最高位对应反转后的第1位）。

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