競技プログラミングをしていると、ある数を二進数で表したときにいくつ1であるような桁があるか(= popcount)を求めたいときがあります。
PyPyではどのように求めるのが高速なのでしょうか。

bin(X).count("1")

二進数の文字列に変換して、そこに含まれる1の数をカウントします。

bin(X).count("1")

while文

while文で下のbitから1bitずつカウントします。

ans = 0
while X:
    ans += X&1
    X >>= 1

bit_count

新しいバージョンのpythonにはこのpopcountを求めるメソッドがあります。

X.bit_count()

bit演算

bit演算や足し算引き算を利用することで並列に処理します。

(下記のコードは32bit整数向けであることに注意してください)

def popcount(x):
    # from : https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
    # for 32-bit integers
    c = x - ((x >> 1) & 0x55555555)
    c = (c & 0x33333333) + ((c >> 2) & 0x33333333)
    c = (c + (c >> 4)) & 0x0F0F0F0F
    c = (c + (c >> 8)) & 0x00FF00FF
    c = (c + (c >> 16)) & 0x0000FFFF
    return c

PyPy3で速度比較

PyPy 7.3.12で速度を比較します。

	$0$ から　$ 2^{30}-1 $　まで
bin(x).count('1')	556.492s
while文	21.147s
bit_count	8.479s
bit演算	1.446s

比較に用いたコード

bin

ans = 0

for i in range(2**30):
    ans += bin(i).count('1')

print(ans)

while文

ans = 0

for i in range(2**30):
    while i:
        ans += i&1
        i >>= 1

print(ans)

bit_count

ans = 0

for i in range(2**30):
    ans += i.bit_count()

print(ans)

bit演算

ans = 0

def popcount(x):
    # from : https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
    # for 32-bit integers
    c = x - ((x >> 1) & 0x55555555)
    c = (c & 0x33333333) + ((c >> 2) & 0x33333333)
    c = (c + (c >> 4)) & 0x0F0F0F0F
    c = (c + (c >> 8)) & 0x00FF00FF
    c = (c + (c >> 16)) & 0x0000FFFF
    return c

for i in range(2**30):
    ans += popcount(i)

print(ans)

(おまけ) Python3で速度比較

Python 3.10.9で実行してみます。
($ 2^{30} $までだと終了する気がしなかったので範囲を変えています。)

	$0$ から　$ 2^{25}-1 $　まで
bin(x).count('1')	14.747s
while文	183.771s
bit_count	5.155s
bit演算	26.325s

かなりwhile文のプログラムが低速になりました。
PyPyではbit演算のものが高速でしたが、Pythonではbit_countの方が高速なようです。CPythonの場合は内部で__builtin_popcountを呼んでいる¹ので、それが効いていそうですね。(PyPyのbit_countでは内部でwhileループを用いて実装が行われています。²)

実際に、非常に大きなサイズの整数のbit_countを行う際は、PyPyよりもPythonの方が高速なこともあるようです。
https://atcoder.jp/contests/abc258/submissions/65727523
https://atcoder.jp/contests/abc258/submissions/66875602