Python 3でpopcountを計算する - にせねこメモある整数値が与えられたとき、それを二進数表記した時の1の個数(1になっているビットの数)を数えるのをpopcountと呼ぶらしい(population countの略)。これはハミング距離を計算するのに使え、2つの値のXORをとってpopcountを計算すればハミング距離となる。 Pythonには標準で用意されてないので、64ビット整数に対する演算を想定していくつかの実装を比べてみる。 Python 3系は整数に決まった上限がないので、64-bit unsigned int相当のの範囲の整数値を入力として計算する。 TL;DR bin(n).count("1")が簡潔でそこそこ速い メモリを使ってよければ、事前計算した216要素の配列を引くのが標準機能だけでは最速に近いかもしれない gmpy2ライブラリのgmpy2.popcount(n)を使うのが最速 速度の計測 Python 3でいくつ
