Pythonで2進数の1の数をカウント（int.bit_count）
Pythonで、整数intの2進数表記における1の数（立っているビットの数）をカウントする方法について説明する。このような処理はpopcount（population count）とも呼ばれる。
Pythonにおける2進数表記やビット演算については以下の記事を参照。
int.bit_count()（Python 3.10以降）
Python 3.10で、整数intにbit_count()メソッドが追加された。
i = 100
print(bin(i))
# 0b1100100
print(i.bit_count())
# 3
i = 255
print(bin(i))
# 0b11111111
print(i.bit_count())
# 8
公式ドキュメントにあるように、bit_count()は整数の絶対値の2進数表記における1の数を返す。
Return the number of ones in the binary representation of the absolute value of the integer. 組み込み型 - int.bit_count() — Python 3.11.3 ドキュメント
したがって、負の値に対しては、2の補数形式ではなくその絶対値の2進数表記における1の数を返す。
i = -100
print(bin(i))
# -0b1100100
print(i.bit_count())
# 3
i = -255
print(bin(i))
# -0b11111111
print(i.bit_count())
# 8
なお、上の例のように、bin()の結果も単に絶対値にマイナスが付いた形となる。2の補数形式で表現された文字列を取得したい場合は以下の記事を参照。
bin(self).count("1")（Python 3.9以前）
Python 3.9以前はbit_count()メソッドが提供されていないが、公式ドキュメントにあるように、bin(self).count("1")と等価。
整数intを2進数表記の文字列に変換する組み込み関数bin()、および、文字列に含まれる文字・部分文字列をカウントするcount()メソッドで同等の処理を実現できる。
- 関連記事: Pythonで文字・文字列の出現回数をカウント
def bit_count(self):
return bin(self).count("1")
print(bit_count(100))
# 3
print(bit_count(255))
# 8
print(bit_count(-100))
# 3
print(bit_count(-255))
# 8
なお、Python 3.10で追加されたintのbit_count()メソッドはbin()やcount()を使っているわけではなく、Cで効率的なアルゴリズムを用いて実装されているので、より高速。
- Add an efficient popcount method for integers · Issue #74068 · python/cpython
- Hamming weight - Wikipedia
- https://github.com/niklasf/cpython/blob/3e8422bb6c9fd0cdc4381815fca613e6975ee582/Objects/longobject.c#L5307-L5375
以下のコードはJupyter Notebook上でマジックコマンド%%timeitを使って計測したもの。Pythonスクリプトとして実行しても計測されないので注意。
i = 255
%%timeit
i.bit_count()
# 22 ns ± 0.072 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
%%timeit
bit_count(i)
# 121 ns ± 0.275 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)