popcount で 1 のビット数を数える｜コードで実践

popcount で 1 のビット数を数える

このレッスンで分かること

Brian Kernighan のテクニックは 立っているビット数 だけループ する

計算量は O(log n) (= ビット数) です

整数を 2 進数で表したときに含まれる 1 の個数 を求める操作を popcount (population count、人口計数) と呼びます

popcount で 1 のビット数を数えるとは

整数を 2 進数で表したときに含まれる 1 の個数 (popcount) を求める関数を実装する。本レッスンでは、popcount で 1 のビット数を数えるの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

整数を 2 進数で表したときに含まれる 1 の個数 を求める操作を popcount (population count、人口計数) と呼びます。13 = 1101 なら popcount は 3、255 = 11111111 なら 8、0 なら 0 です。

小さな関数ですが、内部で使われている場面は驚くほど広く、ハミング距離 の計算、データ圧縮、bitmap インデックス、暗号、機械学習の ハッシュ などで必須のテクニックです。多くの CPU には popcnt という専用命令が用意されているくらい重要な操作です。

popcount は CS の 古典的かつ実用的 な小ネタ。CPU 命令にもなっている。

素朴な実装 (右シフトで 1 ビットずつ見る)

最も基本的な実装は「最下位ビットを見て、1 ならカウントを増やし、右に 1 ビットシフトして次へ進む」という流れです。

Python

def popcount(n):
    count = 0
    while n > 0:
        count = count + (n & 1)
        n = n >> 1
    return count

n & 1 で最下位ビットだけを取り出す (0 か 1)
n >> 1 で次のビットを最下位に移動させる
n が 0 になったらループ終了

計算量は O(log n) (= ビット数) です。32 ビット整数なら最大 32 回のループで終わります。

Brian Kernighan のテクニック

もっと巧妙な方法もあります。n & (n - 1) という式を使うと、n の最下位の 1 ビットだけを 0 にできます。これを n が 0 になるまで繰り返した回数が、立っているビットの数です。

Python

def popcount(n):
    count = 0
    while n > 0:
        n = n & (n - 1)
        count = count + 1
    return count

なぜこれで動くのか。n - 1 は、最下位の 1 を 0 に、それより右の 0 を 1 に反転させます。だから n & (n - 1) は 最下位の 1 ビットだけが消える わけです。

例: n = 12 = 1100、n - 1 = 11 = 1011、n & (n - 1) = 1000。最下位の 1 (bit2) が消えました。

diagram (will load when visible)

図のポイント (テキスト併記)

この方法だと、立っているビットの数だけ ループが回ります

この方法だと、立っているビットの数だけ ループが回ります。popcount(0xFFFFFFFF) のような全部 1 の場合は 32 回ですが、popcount(0x00000001) のようなスカスカの値なら 1 回で終わります。

Brian Kernighan のテクニックは 立っているビット数 だけループ する。スカスカな値で特に有利。

JavaScript での実装

JavaScript

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

JavaScript では >>> (符号なし右シフト) を使うのが安全です。>> だと while (n > 0) の条件により負数はループに入らず、符号ビットが立っていても 0 を返してしまいます。>>> (符号なし右シフト) を使えば負数も 32 ビットの非負値として扱われ、正しく popcount を計算できます。

ハミング距離との関係

2 つの整数 a、b の ハミング距離 は、a ^ b の popcount で求められます。XOR は「桁ごとに違うところを 1 にする」演算なので、その popcount は「異なる桁の数」を意味します。たとえば 1101 ^ 1011 = 0110 なので、ハミング距離は 2。これは通信工学やエラー訂正符号で重要な指標です。

ハミング距離は a ^ b の popcount。シンプルなのに通信・暗号・ML で多用される。

よくある間違い

1 つ目は ループ条件 を n != 0 にして算術右シフト >> を組み合わせると、負数で -1 >> 1 が -1 のまま変化せず無限ループになる可能性があります。逆に n > 0 を使うと負数は最初からループに入らず、ビットが立っていても 0 を返してしまいます。負数を正しく扱うには n > 0 と符号なしシフト >>> を組み合わせるか、入力を非負整数に限定するのが安全です。2 つ目は JavaScript で >> を使って 符号ビットが残り続ける ケース。>>> を使えば安全です。3 つ目は count = count + n & 1 のように 括弧を省略 すると、(count + n) & 1 と解釈されて結果が壊れます。

やってみよう

popcount(0) popcount(1) popcount(7) popcount(255) を試して、それぞれ 0 1 3 8 になることを確認。
32 ビット最大値 0xFFFFFFFF = 4294967295 の popcount は 32。
数を 10 進数のまま見て直感を養うのは難しい。bin(n) で 2 進数表示してから数えてみよう。
Brian Kernighan のテクニックでも自分で実装してみる。素朴版と結果が一致することを確認。
Python 3.10 以降には int.bit_count() という組み込みメソッドがある。同じ結果が得られる。

popcount は一見地味ですが、bitmap compression ML crypto で当たり前に使われる重要な道具です。

よくある質問

Q. ビット演算は実務でいつ使いますか？

A. フラグ管理（permission の rwx）、画像処理（マスク）、ハッシュ計算の高速化などで使います。複数の真偽値を 1 つの整数にまとめると、メモリ削減と演算高速化の両方が得られます。例えば 8 個の権限を 1 byte で表せます。

Q. AND / OR / XOR の代表的な使い道は？

A. AND は「特定ビットの確認・抽出」（flags & PERM_READ）、OR は「ビットの立て上げ」（flags |= PERM_WRITE）、XOR は「ビット反転や暗号化」で使います。XOR は 2 回かけると元に戻る性質から、簡易暗号や両端ポインタの入れ替えなどに応用できます。

Q. シフト演算で割り算しても良いですか？

A. 正の整数の 2 のべき乗での除算なら x >> n と x / (1<<n) は同じ結果になります。ただし負の数では言語ごとに挙動が違う（算術シフトと論理シフトの区別）ため、可読性と安全性のために通常の演算子を使い、性能ボトルネックでのみシフトを検討してください。

次のレッスン

次は シフト演算で 2 倍 / 半分 に進みましょう。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

popcount の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. popcount とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

popcount で 1 のビット数を数える