141

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

bin(n).count("1")

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

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

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

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

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

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L
4

12 回答 12

137

对于任意长度的整数,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')

然后是得到0 ≤ x ≤ 255counts[x]中 1 的位数。x

于 2012-03-22T22:46:15.433 回答
62

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

于 2020-11-15T18:35:49.333 回答
36

您可以调整以下算法:

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 位长的桶。这给出了原始参数中设置的位数。

于 2012-03-22T20:48:53.973 回答
20

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

于 2012-03-22T20:09:27.893 回答
10

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

编辑

如果您需要更好的性能(并且您的数字是大整数),请查看该GMP库。它包含许多不同架构的手写汇编实现。

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

>>> import gmpy
>>> gmpy.popcount(2**1024-1)
1024
于 2012-03-22T20:19:37.627 回答
10

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

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

def get_bit_count(value):
   n = 0
   while value:
      n += 1
      value &= value-1
   return n
于 2019-04-25T00:03:22.613 回答
4

您可以使用该算法来获取整数的二进制字符串 [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

于 2017-08-31T06:17:14.173 回答
2

你说 Numpy 太慢了。您是否使用它来存储单个位?为什么不扩展使用整数作为位数组的想法,而是使用 Numpy 来存储它们呢?

ceil(n/32.)将 n 位存储为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 模块。

于 2014-05-03T06:01:53.220 回答
2

可以将查找表与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")))

不幸的是,这个解决方案比bin(x).count('1')Python 3 慢 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))

它适用于 Python 2 和 3;但是,如果解决方案不适用于 Python 2,则不会对其进行测量。

此处未列出某些解决方案。

结果:

  • Python 2:对于 <= 16 位,“没有 lambda 的查找列表”是最快的(比“bin 计数”快 25%,比“查找列表”(使用 lambda)快 6%),大于“bin 计数”是最快的。(我没有为 Python 2 安装 gmpy)
  • Python 3:大致相同的结果。
    • “没有 lambda 的查找字节”具有可比性(与“没有 lambda 的查找列表”相比 +/-2%)。
    • gmpy 在所有情况下都比“bin count”快,但在 numBit <= 16 时比“没有 lambda 的查找列表”慢约 5%。
    • “to_bytes”是可比较的。
    • 使用 f-string 比“bin count”慢大约 10%。
  • PyPy3:lambda 不再产生太多成本,并且to_bytes版本变得更快(比“bin count”快两倍);但是,我无法安装 gmpy。
于 2020-11-06T09:27:38.140 回答
0

@Robotbugs 的回答,但在我的情况下,包裹在 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。

于 2021-12-17T13:09:28.823 回答
-1
#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)

于 2019-06-15T05:14:47.187 回答
-2

事实证明,您的起始表示是整数列表的列表,它们是 1 或 0。只需在该表示中计算它们。


整数中的位数在python中是恒定的。

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

这将在您生成列表后为您提供恒定的时间查找。请参阅@PaoloMoretti 的答案以了解此问题的良好实现。当然,您不必将这一切都保存在内存中——您可以使用某种持久键值存储,甚至是 MySql。(另一种选择是实现您自己的简单的基于磁盘的存储)。

于 2012-03-22T20:04:16.987 回答