以正整数计算非零位的快速方法
我需要一个快速的方法来计算Python中的整数位数。 我目前的解决scheme是
bin(n).count("1") 但我想知道是否有更快的方式做到这一点？
PS：（我代表一个大的2D二进制数组作为数字的单子列表，并进行按位操作，并将时间从几小时缩短到几分钟，现在我想摆脱那些额外的分钟。
编辑：1.它必须在Python 2.7或2.6
对于小数字的优化并不重要，因为这不是一个明确的瓶颈，但是在某些地方我确实有10000个数字的数字
例如这是一个2000位的情况：
12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L
对于任意长度的整数， bin(n).count("1")是我能够在纯Python中find的最快速度。
我试着调整Óscar和Adam的解决scheme来分别处理64位和32位的整数。 两者至less比bin(n).count("1")慢十倍（32位版本花费了大约一半的时间）。
另一方面， gmpy popcount()花费了bin(n).count("1")大约1/20的时间。 所以，如果你可以安装gmpy，使用。
您可以调整以下algorithm：
def CountBits(n): n = (n & 0x5555555555555555) + ((n & 0xAAAAAAAAAAAAAAAA) >> 1) n = (n & 0x3333333333333333) + ((n & 0xCCCCCCCCCCCCCCCC) >> 2) n = (n & 0x0F0F0F0F0F0F0F0F) + ((n & 0xF0F0F0F0F0F0F0F0) >> 4) n = (n & 0x00FF00FF00FF00FF) + ((n & 0xFF00FF00FF00FF00) >> 8) n = (n & 0x0000FFFF0000FFFF) + ((n & 0xFFFF0000FFFF0000) >> 16) n = (n & 0x00000000FFFFFFFF) + ((n & 0xFFFFFFFF00000000) >> 32) # This last & isn't strictly necessary. return n
这适用于64位正数，但它很容易扩展，操作的数量随着参数的对数（即与参数的位长度成线性关系）而增长。
为了理解这个工作原理，可以想象将整个64位string分成64个1位的桶。 每个桶的值等于桶中设置的比特数（如果没有比特被设置则为0，如果设置了一个比特则为1）。 第一次转换的结果是一个类似的状态，但有32个桶，每个长度为2位。 这是通过适当地移动桶并添加它们的值来实现的（由于在桶之间不会发生进位，因此一个添加处理所有桶，n位数总是足够长以编码数n）。 进一步的转换导致状态呈指数级增长的桶的数量呈指数级递减，直到我们到达一个64位长的桶为止。 这给出了在原始参数中设置的位数。
下面是人口数algorithm的Python实现，正如本文中所解释的 ：
def numberOfSetBits(i): i = i - ((i >> 1) & 0x55555555) i = (i & 0x33333333) + ((i >> 2) & 0x33333333) return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
它将工作于0 <= i < 0x100000000 。
根据这篇文章 ，这似乎是最快的执行海明重量 （如果你不介意使用大约64KB的内存）。
#http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable POPCOUNT_TABLE16 = [0] * 2**16 for index in range(len(POPCOUNT_TABLE16)): POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1] def popcount32_table16(v): return (POPCOUNT_TABLE16[ v & 0xffff] + POPCOUNT_TABLE16[(v >> 16) & 0xffff])
在Python 2.x中，您应该使用xrangereplacerange 。
编辑
如果你需要更好的performance（和你的数字是大整数），看看GMP库。 它包含许多不同体系结构的手写汇编实现。
gmpy是一个C编码的Python扩展模块，它包装了GMP库。
>>> import gmpy >>> gmpy.popcount(2**1024-1) 1024
你说Numpy太慢了。 你用它来存储个人位？ 为什么不扩展使用int作为位数组的想法，但使用Numpy来存储这些？
将n位存储为一个32位整数的数组ceil(n/32.) 。 然后，您可以使用numpy数组与您使用整数（包括使用它们索引另一个数组）相同的方式（以及相似的方式）。
该algorithm基本上是并行地计算每个单元中设置的比特数，并且它们总计每个单元的比特数。
setup = """ import numpy as np #Using Paolo Moretti's answer http://stackoverflow.com/a/9829855/2963903 POPCOUNT_TABLE16 = np.zeros(2**16, dtype=int) #has to be an array for index in range(len(POPCOUNT_TABLE16)): POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1] def popcount32_table16(v): return (POPCOUNT_TABLE16[ v & 0xffff] + POPCOUNT_TABLE16[(v >> 16) & 0xffff]) def count1s(v): return popcount32_table16(v).sum() v1 = np.arange(1000)*1234567 #numpy array v2 = sum(int(x)<<(32*i) for i, x in enumerate(v1)) #single int """ from timeit import timeit timeit("count1s(v1)", setup=setup) #49.55184188873349 timeit("bin(v2).count('1')", setup=setup) #225.1857464598633
虽然我很惊讶没有人build议你写一个C模块。
您可以使用该algorithm来获取整数的二进制string[1]，而不是连接string，计算一个string的数量：
def count_ones(a): s = 0 t = {'0':0, '1':1, '2':1, '3':2, '4':1, '5':2, '6':2, '7':3} for c in oct(a)[1:]: s += t[c] return s
事实certificate，你的开始表示是一个列表，它是1或0的列表。只需在表示中对它们进行计数。
在Python中，整数中的位数是常量。
但是，如果要计算所设置的位数，最快的方法是创build一个符合以下伪代码的列表： [numberofsetbits(n) for n in range(MAXINT)]
这将为您提供一个恒定的时间查询生成列表后。 查看@ PaoloMoretti的答案是为了很好地实现这一点。 当然，你不需要将这一切都保存在内存中 – 你可以使用某种持久化的键值存储，甚至是MySql。 （另一个select是实现你自己的简单的基于磁盘的存储）。
