ビットカウント（ポピュレーションカウント / popcount）

ポピュレーションカウント（popcount）

数値のポピュレーションカウントは、バイナリ表現で1に設定されたビットの数です。ハミング重みまたは横方向の合計とも呼ばれます。

Brian Kernighanのアルゴリズム

最もエレガントなソフトウェアアプローチは、各反復で1つの設定ビットをクリアします：

function popcount(n) {
  let count = 0;
  while (n) {
    n &= (n - 1);  // 最下位の設定ビットをクリア
    count++;
  }
  return count;
}

仕組み: n & (n - 1)は最下位の設定ビットをクリアします。各反復でちょうど1つの1ビットが削除されるため、ループは正確にpopcount(n)回実行されます。

例：popcount(42)

42 = 00101010  (3つの設定ビット)

反復1: 00101010 & 00101001 = 00101000  (ビット1クリア)
反復2: 00101000 & 00100111 = 00100000  (ビット3クリア)
反復3: 00100000 & 00011111 = 00000000  (ビット5クリア)

結果: 3

ルックアップテーブル方式

最大スループットのために、8ビット値の256エントリテーブルを事前計算し、1バイトずつ処理：

const TABLE = new Uint8Array(256);
for (let i = 1; i < 256; i++) {
  TABLE[i] = TABLE[i >> 1] + (i & 1);
}

function popcount32(n) {
  return TABLE[n & 0xFF] +
         TABLE[(n >> 8) & 0xFF] +
         TABLE[(n >> 16) & 0xFF] +
         TABLE[(n >> 24) & 0xFF];
}

ハードウェアサポート

最新のCPUには専用のpopcount命令があります（x86のPOPCNT、ARMのCNT）。C/C++では__builtin_popcount()でアクセスできます。JavaScriptのMath.clz32()はリーディングゼロのカウントを提供しますが、組み込みのpopcountはありません。

ハミング距離

2つの値間のハミング距離はpopcount(a ^ b)です — ビット位置が異なる数です。