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

オンが「何個」あるかを知りたい

フラグを立てる、反転する、見る、という操作を読みました。次は「今いくつオンになっているか」を考えます。値の大きさではなく、1になっている桁の個数を見ます。

それでも数えられます。ただ、桁ごとに別のマスクを並べるより、見る場所を右端に固定すると、同じ手順で全体を追えます。

2進数に含まれる 1 の個数を数える操作をpopcountと呼びます。13は 1101 なので3、255は 11111111 なので8です。重みは足しません。先頭の0が増えても、1の個数は変わりません。

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

いちばん右の桁は n & 1 で取り出せます。結果が1なら個数を1増やし、0なら増やしません。そのあと右端を捨て、残りを右へ詰めます。これを値が0になるまで続けます。

1101   右端は1   個数1
 110   右端は0   個数1
  11   右端は1   個数2
   1   右端は1   個数3
   0   終了

右へ1桁詰める操作は n >> 1 と書き、右シフトと呼びます。ここでは0以上の整数を扱い、2で割った整数の商を残す操作として読めます。13なら6、6なら3、3なら1、1なら0です。仕組みは次の回で詳しく読みます。

前の変換では、10進数の0を2進数の表記 0 にする必要がありました。今回は数え始めの個数0が、そのまま正解です。同じ繰り返しでも、何を答えとして残すかで、0の扱いが違います。

同じ形は、10進数でも使える

端の桁を見て捨てる手順は、10進数の桁の合計にも使えます。Pythonの % 10 は余り、// 10 は整数の商です。

n = 4821
total = 0
while n > 0:
    total = total + n % 10    # 右端の数字を足す
    n = n // 10              # 右端を捨てる
print(total)                 # 15

足す数字は1、2、8、4の順なので、合計は15です。2進数なら足す数字が0か1に限られ、その合計が1の個数になります。元の値を後でも使う場合は、読み進める途中の値と分けて持ちます。

解説

現場の話 2つの数の ^ を取り、1を数えると、食い違う桁数が分かります。この個数をハミング距離と呼び、通信の誤りを調べるときに使います。

例題で確かめる

5つの機能の状態が 10110 です。オンの機能はいくつあるでしょうか。右端から読んだ数字は 0、1、1、0、1 なので、合計は3です。

値自体は 16 + 4 + 2 = 22 ですが、オンの数は22でも、全5桁を数えた5でもありません。1がある3か所だけを数えます。