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

小开

结果表明，起始表示形式是一个 int 列表的列表，它可以是1，也可以是0。简单地把它们计算在那个表示中。

整数中的位数在 python 中是常数。

但是，如果想要计算集合位的数量，最快的方法是创建一个符合以下伪代码的列表: [numberofsetbits(n) for n in range(MAXINT)]

这将在生成列表后为您提供一个常量时间查找。请参见@PaoloMoretti 对此的良好实现的回答。当然，您不必将这些都保存在内存中——您可以使用某种持久的键值存储，甚至使用 MySql。(另一种选择是实现您自己的简单的基于磁盘的存储)。

小开

下面是人口计数算法的 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 上，应该用 xrange替换 range。

剪辑

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

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

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

小开

你可采用下列算法:

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位桶。每个 bucket 的值等于在 bucket 中设置的位数(如果没有设置位，则为0; 如果设置了一个位，则为1)。第一个转换的结果是类似的状态，但是有32个桶，每个桶的长度为2位。这是通过适当地移动存储桶并添加它们的值来实现的(一个附加值可以处理所有存储桶，因为不能在存储桶之间进位-n 位数总是足够长以编码 n)。进一步的转换会导致存储桶数量呈指数增长的状态，直到我们得到一个64位长的存储桶。这给出了在原始参数中设置的位数。

小开

最佳答案

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

我尝试采用奥斯卡和亚当的解决方案，分别处理64位和32位的整数块。两者都至少比 bin(n).count("1")慢10倍(32位版本花费的时间是 bin(n).count("1")的一半)。

另一方面，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。

小开

你说小笨笨太慢了。你是用它来储存个人信息的吗？为什么不扩展使用 int 作为位数组的想法，而使用 Numpy 来存储这些数组呢？

将 n 位存储为一个由 ceil(n/32.)32位整数组成的数组。然后，您可以使用与使用 int 相同(好吧，非常类似)的方式来处理 numpy 数组，包括使用它们来索引另一个数组。

该算法基本上是并行地计算每个单元中设置的位数，并将每个单元的位数相加。

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

虽然我很惊讶没人建议你写 C 模块。

小开

你可以使用这个算法来得到一个整数的二进制字符串[1] ，但是不用连接这个字符串，而是计算一个整数的数量:

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

[1] https://wiki.python.org/moin/BitManipulation

小开

我真的很喜欢这个方法。它简单而且相当快，但是也不限制位长度，因为 python 有无限的整数。

它实际上比看起来更狡猾，因为它避免了浪费时间扫描零。例如，计算1000000000000000000000001010000000000000000000010100000000000000000000001000000000000000000000000000000000000。

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

小开

#Python prg to count set bits
#Function to count set bits
def bin(n):
count=0
while(n>=1):
if(n%2==0):
n=n//2
else:
count+=1
n=n//2
print("Count of set bits:",count)
#Fetch the input from user
num=int(input("Enter number: "))
#Output
bin(num)

小开

可以将查找表与 int.to_bytes(仅用于 Python 3)组合在一起:

popcount8bit = bytes([popcount(x) for x in range(1<<8)])  # use any method to initialize this lookup table
popcount = lambda x: sum(map(popcount8bit.__getitem__,
x.to_bytes((x.bit_length()+7)//8, "little")))

不幸的是，这个解决方案比 Python3上的 bin(x).count('1')慢20% ，但是在 PyPy3上快两倍。

这是一个基准脚本，比较了这里提出的几种不同的解决方案，对于不同数量的比特:

from __future__ import print_function  #for Python 2


import sys
from timeit import timeit
import random


def popcount(x): return bin(x).count("1")


version3=sys.version.startswith("3")


for numBit in (2, 4, 8, 16, 31, 32, 63, 64, 1000, 10000):
maximum=int((1<<numBit)-1)  #int cast just in case it overflows to long in Python 2


functions=[
(popcount, "bin count"),
(lambda x: "{:b}".format(x).count("1"), "format string count"),
]


try:
import gmpy
functions.append((gmpy.popcount, "gmpy"))
except ImportError:
pass


if sys.version.startswith("3"):
exec('''functions.append((lambda x: f"{x:b}".count("1"), "f-string count"))''')


if numBit<=16:
table1=[popcount(x) for x in range(maximum+1)]
functions.append((lambda x: table1[x], "lookup list"))
functions.append((table1.__getitem__, "lookup list without lambda"))


table2="".join(map(chr, table1))
functions.append((lambda x: ord(table2[x]), "lookup str"))


if version3:
table3=bytes(table1)
functions.append((lambda x: table3[x], "lookup bytes"))


if numBit==8:
functions.append((
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'
.__getitem__, "lookup bytes hard coded 8 bit"))
table_hardcoded=(
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')
functions.append((
table_hardcoded.__getitem__, "lookup bytes hard coded 8 bit local variable"))
functions.append((table3.__getitem__, "lookup bytes without lambda"))


if version3:
popcount8bit=bytes([popcount(x) for x in range(1<<8)]) #bytes because benchmark says that it's fastest
functions.append((
lambda x: sum(popcount8bit[x] for x in x.to_bytes((x.bit_length()+7)//8, "big")),
"to_bytes"
))
functions.append((
lambda x: sum(map(popcount8bit.__getitem__, x.to_bytes((x.bit_length()+7)//8, "big"))),
"to_bytes without list comprehension"
))
functions.append((
lambda x: sum(map(popcount8bit.__getitem__, x.to_bytes((x.bit_length()+7)//8, "little"))),
"to_bytes little endian, without list comprehension"
))


#for x in (2, 4, 8, 16, 32, 64):
#   table1=[popcount(x) for x in range(1<<8)]




print("====== numBit=", numBit)
data=[]
numRepeat=10**7//(numBit+100)
for popcountFunction, description in functions:
random.seed(10) #make randint returns the same value
data.append((
timeit(lambda: popcountFunction(random.randint(0, maximum)), number=numRepeat),
description
))


time1, name1=data[0]
assert name1=="bin count"
data.sort()
maxLength=0
for time, description in data:
maxLength=max(maxLength, len(description))
for time, description in data:
print("{:{}} -> {:2f} = {} * {:2f}".format(description, maxLength+2, time, name1, time/time1))

它同时适用于 Python2和 Python3; 但是，如果解决方案不适用于 Python2，则不进行测量。

这里没有列出一些解决方案。

结果:

Python 2: “ lookup list without lambda”在 < = 16位时是最快的(比“ bin count”快25% ，比“ lookup list”(with lambda)快6%) ，大于“ bin count”是最快的。(我没有为 Python 2安装 gmpy)
Python 3: 大致相同的结果。
- “没有 lambda 的查找字节”与“没有 lambda 的查找列表”相当(+/-2%)。
- Gmpy 在所有情况下都比“ bin count”快，但在 numBit < = 16的情况下比“ lookup list without lambda”慢5% 。
- “ to _ bytes”是可比较的。
- 使用 f-string 比“ bin count”慢10% 。
PyPy3: lambda 不再需要很多成本，而且 to_bytes版本变得更快(比“ bin count”快两倍) ; 但是，我无法安装 gmpy。

小开

Python 3.10介绍 int.bit_count():

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

这在功能上等同于 bin(n).count("1")，但应该是 6倍的速度。参见第二九八八二期。

小开

@ 机器虫的回答，但是被 Numba 的 Njit 装饰器包裹起来，比我的 Gmpy 还快。

@njit(int64(uint64))
def get_bit_count(bitboard):
n = 0
bitboard = int64(bitboard)
while bitboard:
n += 1
bitboard &= bitboard - 1
return n

我必须将 uint64设置为参数类型，以避免 OverlowError。

小开

class popcount_lk:
""" Creates an instance for calculating the population count of
bitstring, based on a lookup table of 8 bits. """


def __init__(self):
""" Creates a large lookup table of the Hamming weight of every 8 bit integer. """
self.lookup_table = bytes.maketrans(bytes(range(1<<8)),bytes((bin(i).count('1') for i in range(1<<8))))
self.byteorder = sys.byteorder
    

def __call__(self,x):
""" Breaks x, which is a python integer type, into chuncks of 8 bits.
Calls the lookup table to get the population count of each chunck and returns
the aggregated population count. """


return sum(x.to_bytes((x.bit_length()>>3)+1,self.byteorder).translate(self.lookup_table))


popcount = popcount_lk
print(popcount(56437865483765))

在 CPython 和 PyPy3中，这应该比 bin(56437865483765).count('1')快3倍。