快速计算正整数的非零位

Question

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

bin(n).count("1")

但我想知道是否有更快的方法这样做？

PS :(我代表一个大的2D二进制数组作为数字和按位操作的单一列表,并且将时间从几小时缩短到几分钟.现在我想摆脱那些额外的分钟.

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

并且对小数量进行优化并不重要,因为那不是一个明确的瓶颈,但我确实在某些地方有10 000 +位的数字

例如,这是一个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,请使用它.

要回答评论中的问题,对于字节我会使用o查找表.您可以在运行时生成它:

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

或者只是执行一次并粘贴以counts[x]按字面意思定义它:

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')

然后在0 <= x <= 255的位置x得到1位数bin(n).count("1").

Answer 2

Python 3.10 引入int.bit_count()：

>>> n = 19
>>> bin(n)
'0b10011'
>>> n.bit_count()
3
>>> (-n).bit_count()
3

这在功能上等同于bin(n).count("1")但应该快 6 倍。另见问题29882。

Answer 3

您可以调整以下算法:

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位字符串分成64个1位桶.每个桶的值等于桶中设置的位数(如果没有设置位,则为0,如果设置了一位,则为1).第一次转换导致类似的状态,但是每个2位长有32个桶.这是通过适当地移动桶并添加它们的值来实现的(一个添加处理所有桶,因为桶之间不会发生进位 - n位数总是足够长以编码数n).在我们到达一个64位长的桶之前,进一步的转换会导致状态呈指数级增长,呈指数级增长.这给出了原始参数中设置的位数.

Answer 4

这里的人口数算法的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.

Answer 5

我真的很喜欢这种方法。它简单且非常快，但也不受位长的限制，因为 python 具有无限整数。

它实际上比看起来更狡猾，因为它避免了浪费时间扫描零。例如，计算 1000000000000000000000010100000001 中的设置位所需的时间与 1111 中的相同。

def get_bit_count(value):
   n = 0
   while value:
      n += 1
      value &= value-1
   return n

Answer 6

根据这篇文章,这似乎是汉明重量最快的实现(如果你不介意使用大约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上你应该替换range为xrange.

编辑

如果您需要更好的性能(并且您的数字是大整数),请查看GMP库.它包含许多不同体系结构的手写程序集实现.

gmpy 是一个C编码的Python扩展模块,它包装了GMP库.

>>> import gmpy
>>> gmpy.popcount(2**1024-1)
1024