Brian Kernighan のアルゴリズムで高速にビット数をカウントする

1. 要約

• ビットのカウントを高速で行いたいとき、このアルゴリズムが有用
• 計算量は $O(K)$ （Kは入力された数字 N に含まれる1の個数）
• 実装は以下の通り

def count_bits(n):
    count = 0
    while n > 0:
        n &= n - 1 # 最下位のビット（=1）を1つ消す
        count += 1

    return count

2. Brian Kernighan's algorithm

Brian Kernighanというカナダ人の計算機科学者が考案したビット操作に関するアルゴリズムである。このアルゴリズムを利用すると、最下位のビットを1回の演算で削除できるという特徴がある。

通常、ビット列に含まれる1の個数をカウントしようとすると、全てのビットを1つずつ見ていくことになる為、計算量は$O(\log N)$となる。しかし、この方法では1の数に応じた回数だけループが回る為、実際にはより高速に処理できる場合が多い。

3. アルゴリズムの動作例

例として、入力 n を13として考える。13を2進数に変換すると、1101 となる。

1. n = 13 $\rightarrow$ 1101 $\rightarrow$ n & (n - 1) = 1100 (12)
2. n = 12 $\rightarrow$ 1100 $\rightarrow$ n & (n - 1) = 1000 (8)
3. n = 8 $\rightarrow$ 1000 $\rightarrow$ n & (n - 1) = 0000 (0)

$\rightarrow$ 3回で終了し、

ビット列に含まれる1の個数 = 3

と分かる。

4. 参考

[1] Brian Kernighan’s Algorithm: Count set bits in a number

[2] Count set bits in an integer