数二进制里有多少个 1：从循环到 SWAR

「有多少个 1」听着像课堂练习，实际出现在位图基数统计、汉明距离、布隆过滤器估算和位棋盘里 —— 最后一项我这周刚用过，五子棋与黑白棋的棋盘用 64 位整数表示时，胜负判定就是几次位运算。

最省事的写法

按位与掉最低位的 1，循环次数等于 1 的个数（Brian Kernighan 的做法）：

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

n - 1 会把最低位的 1 变成 0、把它右边的 0 全变成 1，再与回去正好消掉那一位。对一个稀疏的位图（1 很少），这个写法几乎是最优的。

稠密时改成并行

如果 1 很多（一半左右），按 1 的个数循环就退化成按位循环。SWAR（在寄存器内并行处理多个小字段）把 32 位分成 16 组两位、8 组四位……四步之后每 4 位里存的就是该组的计数：

function popcount32(x) {
  x = x - ((x >>> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
  x = (x + (x >>> 4)) & 0x0f0f0f0f;
  return (x * 0x01010101) >>> 24;
}

复杂度对比：

写法	代价
逐位检查	永远 32 轮
消最低位	循环次数 = 1 的个数
查表（256 字节）	4 次查表 + 加法
SWAR	固定约 12 次运算，无分支

先看内置

现代语言大多已经有：Rust 的 u32::count_ones()、C++20 的 std::popcount、Java 的 Integer.bitCount，WebAssembly 有 i32.popcnt 指令。它们会被编译成 CPU 的 POPCNT，一行就比上面两种都快。手写 SWAR 的意义在于：你知道那个内置函数背后是什么，以及在没有它的环境（老 JS 引擎、受限的 Wasm 环境）里该怎么办。

两个踩过的坑

• JS 的移位是按 32 取模的：1 << 32 等于 1，不是 0。处理 32 位以上的位图要用 BigInt 或 Math.imul 的组合。
• >> 与 >>> 不同：负数算术右移补 1，逻辑右移补 0。SWAR 里必须用 >>>，否则高位补进来的 1 会污染计数。

先找内置指令，再考虑 SWAR —— 知道原理的价值是知道什么时候不该手写。