2 進数に 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 にするので、AND で戻すとちょうどその 1 ビットだけが消えます。1 が少ない疎なビットマップでは、ほぼ最適です。

密なときは並列に数える

1 が半分くらいあると、1 の個数だけ回すループはビット数だけ回すループに退化します。SWAR（レジスタ内で複数の小さなフィールドを並列処理する）は、32 ビットを 2 ビット×16、4 ビット×8 と分割し、4 段のあと各 4 ビットフィールドがその個数を持ちます。

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

比較は次のとおりです。

方法	コスト
1 ビットずつ調べる	常に 32 回
最下位の 1 を消す	回数 = 1 の個数
表引き（256 バイト）	4 回の参照と加算
SWAR	約 12 演算、分岐なし

まず組み込みを探す

現代の言語にはたいてい用意されています。Rust の u32::count_ones()、C++20 の std::popcount、Java の Integer.bitCount、WebAssembly の i32.popcnt 命令です。これらは CPU の POPCNT 命令にコンパイルされ、1 行で上の 2 つより速い。手で SWAR を書く価値は、組み込みが何をしているかを知ることと、それがない環境（古い JS エンジン、制約のある Wasm）でどうするかを知ることです。

踏んだ 2 つの罠

• JS のシフトは 32 で割った余り：1 << 32 は 1 で、0 ではありません。32 ビットを超えるビットマップは BigInt か Math.imul の組み合わせが要ります。
• >> と >>> は別物：負数の算術右シフトは 1 を、論理右シフトは 0 を詰めます。SWAR は >>> を使わないと、符号ビットが数え上げを汚染します。

まず組み込み命令を探し、それから SWAR を検討する。仕組みを知る価値は、いつ書かないかを知ることにある。