[解決済み] 正の整数の非ゼロビットを高速にカウントする方法

質問

Pythonで整数のビット数をカウントする高速な方法が必要です。 私の現在の解決策は

bin(n).count("1")

というのがありますが、これをもっと早くやる方法はないのでしょうか？

PS: (私は大きな2Dバイナリ配列を数値の単一のリストとして表現し、ビット演算を行っています。これにより、時間が数時間から数分に短縮されました。

編集 1. Python 2.7 または 2.6 である必要があります。

また、小さな数に対する最適化は、明確なボトルネックにならないので、それほど重要ではありませんが、私はいくつかの場所で10 000 +ビットの数を持っています。

例えばこれは2000ビットの場合です。

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L

どのように解決するのですか？

任意の長さの整数の場合。 bin(n).count("1") は私が純粋なPythonで見つけることができた最速のものです。

ÓscarとAdamのソリューションを適応して、それぞれ64ビットと32ビットのチャンクで整数を処理することを試してみました。どちらも bin(n).count("1") (32 ビット版はその約半分の時間を要しました)。

一方 gmpy popcount() に比べて約1/20の時間で bin(n).count("1") . というわけで、gmpyをインストールできる人はそれを使ってください。

コメントでの質問に答えると、バイトの場合はルックアップテーブルを使うことになります。実行時に生成することができます。

counts = bytes(bin(x).count("1") for x in range(256))  # py2: use bytearray

あるいは、文字通りに定義すればよい。

counts = (b'\x00\x01\x01\x02\x01\x02\x02\x03\x01\x02\x02\x03\x02\x03\x03\x04'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x04\x05\x05\x06\x05\x06\x06\x07\x05\x06\x06\x07\x06\x07\x07\x08')

では、それは counts[x] で1のビットの数を求めます。 x ここで、0≦x≦255です。