python - 以正整数计算非零位的快速方法

Question

我需要一种快速的方法来计算 python 中整数的位数。我目前的解决方案是

bin(n).count("1")

但我想知道是否有更快的方法来做到这一点？

PS:(我将一个大的二维二进制数组表示为一个数字列表并进行按位运算，这将时间从几小时缩短到几分钟。现在我想摆脱那些额外的分钟。

编辑:1. 它必须在 python 2.7 或 2.6 中

优化小数字并不重要，因为这不是一个明显的瓶颈，但我确实在某些地方有 10 000 + 位的数字

例如这是一个 2000 位的情况:

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L

Answer 1

对于任意长度的整数，bin(n).count("1") 是我在纯 Python 中能找到的最快的。

我尝试采用 Óscar 和 Adam 的解决方案分别处理 64 位和 32 位 block 中的整数。两者都比 bin(n).count("1") 慢了至少十倍(32 位版本又花了大约一半的时间)。

另一方面，gmpy popcount() 的时间大约是 bin(n).count("1") 的 1/20。因此，如果您可以安装 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] 得到 x 中 1 的位数，其中 0 ≤ x ≤ 255。