位运算循环n & (n−1)法通过每次清除最右1位，使循环次数精确等于二进制中1的个数，时间复杂度O(1的个数)，优于固定32次遍历；支持负数补码、零开销、无分支，适合嵌入式与算法竞赛。

“位巡航循环”并不是标准术语，实际指的是利用位运算特性设计的高效循环算法——核心是用 n & (n − 1) 每次清除一个最右的 1，从而让循环次数严格等于二进制中 1 的个数，而非总位数。它不依赖移位方向、不惧负数补码，硬件执行快，适合高频、嵌入式和算法竞赛场景。

为什么选 n & (n − 1) 而不是逐位扫描

普通遍历（如右移+&1 或 for i=0 to 31）固定执行 32 次，哪怕输入是 1（二进制仅一个 1）也要跑满；而 n & (n − 1) 利用一个关键恒等式：对任意非零整数 n，n & (n−1) 必将 n 的二进制表示中最右侧的 1 置为 0，其余位不变。

• 例如：n = 12 → 二进制 1100，n−1 = 11 → 1011，1100 & 1011 = 1000（清掉最右的 1）
• 再算一次：1000 & 0111 = 0000，循环结束，共 2 次 —— 正好等于 12 中 1 的个数
• 对稀疏数据（如掩码 0x100000、标志位组合）优势极明显，平均耗时远低于固定 32 次循环

实战代码（C 语言，兼容有符号整数）

无需转 unsigned，直接处理补码形式的负数：

int popcount(int n) {
  int count = 0;
  while (n) {
    n = n & (n - 1);
    count++;
  }
  return count;
}

• 原理上，负数在补码下也是合法整数，n−1 和 & 运算在硬件层面完全支持
• 比如 n = −1（32 位全 1），第一次 n & (n−1) = 0xffffffff & 0xfffffffe = 0xfffffffe，逐步清零，最终循环 32 次，结果正确
• 无分支、无条件跳转开销，现代 CPU 流水线友好

对比其他方法的关键差异

• 逐位右移法：需先转 unsigned 防算术右移陷阱；循环次数上限为位宽（32），时间复杂度 O(log n)
• 查表法 / 分治法：常数时间，但需额外内存或复杂逻辑，适合批量处理（如 SSE/AVX 向量指令）
• n & (n−1) 法：零内存开销、代码最短、逻辑最简、天然适配任意整型宽度，且循环次数下界最优

注意事项与边界处理

• 输入为 0 时，循环不执行，返回 0 —— 正确
• 不要在循环体内修改 n 后又误用原值做判断；写成 while(n) { n &= n-1; count++; } 最安全
• 在 Verilog 等 HDL 中，该逻辑综合为纯组合电路，但需注意：若用 for 循环描述，综合工具可能展开为 32 级加法器链；而 n&(n−1) 风格更易被优化为并行前缀结构