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

オンが「何個」あるかは、まだ数えられない

フラグを立てる、落とす、見る、まではできるようになりました。ところが「今いくつオンになっていますか」には、まだ答えられません。

マスクを桁の数だけ用意して全部当てる、という手もあります。しかし設定が 32 個あれば 32 行、64 個なら 64 行です。桁が増えるたびにコードが伸びる書き方は、どこかで必ず破綻します。

2 進数に含まれる 1 の個数を数える操作を popcount と呼びます。13 は 1101 なので 3、255 は 11111111 なので 8 です。

端の 1 桁だけを見て、見たら捨てる

桁の数だけコードを書かずに済ませるには、見る場所を固定します。いつもいちばん右の桁だけを見る、数え終わったらその桁を落として全体を右に詰める、これを数が無くなるまで続けます。見る場所が動かないので、書くのは 1 か所で済みます。

13 を追うと次のようになります。

いちばん右の桁だけを取り出す道具も、全体を右へ詰める道具も、ここまでの回で出そろっています。繰り返す回数は桁数までなので、32 ビットの数でも最大 32 回です。

0 を渡したときは、繰り返しに一度も入りません。10 進数への変換では、これが空の答えになって困りました。今回は数えた個数が 0 のままで返るので、そのまま正解になります。同じ形の繰り返しでも、入り口で止まったときに正しい答えが残るかどうかは問題ごとに違う、ということです。

同じ形は、10 進数でも書ける

「端の桁を見て、見たら捨てる」という形は、2 進数だけのものではありません。10 進数で各桁の合計を出すときも、骨組みはまったく同じです。

見る道具と詰める道具が入れ替わるだけで、while の形も、変数の増やし方も動きません。2 進数の場合に何を当てはめるかだけ考えてください。

なお n を書き換えながら進むので、元の値は途中で消えます。あとで使うなら、始める前に別の変数へ取っておいてください。

解説

現場の話 2 つの数がどれだけ食い違っているかは、^ を取ってから 1 を数えると出ます。^ は違う桁だけ 1 にするので、その個数がそのまま食い違いの桁数です。通信の誤り検出で使うハミング距離が、これです。

1. n は 0 以上の整数と仮定して良い
2. 文字列変換を介さず、ビット演算 (& と >> または >>>) で計算すること
3. n = 0 のときは 0 を返すこと