pythonでbit count

整数を二進数で表したときに、1がいくつあるのかを数えるという処理がたまに欲しい時があります。

この処理はbit countとかpopulation countなんていうふうに呼ばれています。

ビットを数える・探すアルゴリズム にかなり詳しくまとまっています。

ここの三つ目のアルゴリズムは、前にカーニハンリッチーのCの入門書で見つけて感動したのを覚えています。

int numofbits3(int bits) {

  int num  = 0;

  

  for( ; bits != 0 ; bits &= bits - 1 ){  

    num++ ;

  }

  return num;

}

pythonでも今まで下のコードを書いてbitcountしていたのですが、このコードは1の個数が少ないと計算が速いですが、1の個数が多いとループの回数が多くなってしまいます。

def bc(x):

    n = 0

    while x:

        n += 1

        x &= x-1

    return n

ということで、ビットが密な場合でも高速に計算するにはどうしたらいいだろうと何通りかコードを書いてみたのですが、下のが断トツで最速でした。

def bc(x):

    return bin(x).count("1")

結果としてはちょっと詰まらないですが、今度からこう書こうと思います。