popcount - かに

popcount

1回だけならbit_count()を使うと簡潔に書ける。

code: bc1.py

bit_count = i.bit_count()

何度もクエリが来る場合は前計算しておく。

前計算：$ O(N)

クエリ：$ O(1)

code: bc.py

bit_count = 0

for _ in range(N.bit_length()):

bit_count += x+1 for x in bit_count

#ビット演算