快速计数正整数中的非零位的方法

Question

我需要一种快速的方法来计算python中整数的位数。我当前的解决方案是bin(n).count("1")但我想知道是否有更快的方法？PS ：（我将一个大型2D二进制数组表示为单个数字列表并进行按位运算，这将时间从几小时缩短为几分钟。现在，我想摆脱那些多余的分钟。编辑：1.它必须在python 2.7或2.6中对小数字进行优化并不重要，因为这并不是一个明显的瓶颈，但是在某些地方，我确实拥有1万+位的数字例如，这是一个2000位的情况：12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L

Answer 1

对于任意长度的整数，这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]得到0≤x≤255处的1位数目x。