• 当前位置：首页
  • IT科技
  • 计算正整数中非零位的快速方法

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

2025-02-21 08:50:00
admin
原创
7
摘要：问题描述：我需要一种快速的方法来计算 Python 中整数的位数。我目前的解决方案是bin(n).count("1") 但我想知道是否有更快的方法来做到这一点？解决方案 1：Python 3.10 引入int.bit_count()：>>> n = 19 >>...

问题描述：

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

bin(n).count("1")

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

解决方案 1：

Python 3.10 引入int.bit_count()：

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

这在功能上相当于bin(n).count("1")但应该快约 6 倍。另请参阅Issue29882。

解决方案 2：

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

我尝试采用奥斯卡和亚当的解决方案分别以 64 位和 32 位块处理整数。两者的速度至少比前者慢 10 倍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'x00x01x01x02x01x02x02x03x01x02x02x03x02x03x03x04'
          b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
          b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
          b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
          b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
          b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
          b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
          b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
          b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
          b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
          b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
          b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
          b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
          b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
          b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
          b'x04x05x05x06x05x06x06x07x05x06x06x07x06x07x07x08')

然后获取0 ≤ x ≤ 255 中counts[x]的 1 的位数。x

解决方案 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）。第一次转换会产生类似的状态，但有 32 个存储桶，每个存储桶长 2 位。这是通过适当移动存储桶并添加它们的值来实现的（一次加法可以处理所有存储桶，因为存储桶之间不会发生进位 - n 位数字总是足够长以编码数字 n）。进一步的转换会导致存储桶数量呈指数减少、大小呈指数增长的状态，直到我们得到一个 64 位长的存储桶。这给出了原始参数中设置的位数。

解决方案 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。

解决方案 5：

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

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

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

解决方案 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

解决方案 7：

您可以使用该算法来获取整数的二进制字符串 [1]，但不是连接字符串，而是计算 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

解决方案 8：

可以将查找表与以下内容结合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'x00x01x01x02x01x02x02x03x01x02x02x03x02x03x03x04'
                        b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
                        b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
                        b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
                        b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
                        b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
                        b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
                        b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
                        b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
                        b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
                        b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
                        b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
                        b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
                        b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
                        b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
                        b'x04x05x05x06x05x06x06x07x05x06x06x07x06x07x07x08'
                        .__getitem__, "lookup bytes hard coded 8 bit"))
                table_hardcoded=(
                        b'x00x01x01x02x01x02x02x03x01x02x02x03x02x03x03x04'
                        b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
                        b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
                        b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
                        b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
                        b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
                        b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
                        b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
                        b'x01x02x02x03x02x03x03x04x02x03x03x04x03x04x04x05'
                        b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
                        b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
                        b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
                        b'x02x03x03x04x03x04x04x05x03x04x04x05x04x05x05x06'
                        b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
                        b'x03x04x04x05x04x05x05x06x04x05x05x06x05x06x06x07'
                        b'x04x05x05x06x05x06x06x07x05x06x06x07x06x07x07x08')
                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 count”快 25%，比“查找列表”（带 lambda）快 6%），大于 16 位时“bin count”是最快的。（我没有为 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。

解决方案 9：

您说 Numpy 太慢了。您用它来存储单个位吗？为什么不扩展使用 int 作为位数组的想法，而是使用 Numpy 来存储它们呢？

将 n 位存储为 32 位整数数组ceil(n/32.)。然后，您可以按照与使用整数相同（嗯，足够相似）的方式使用 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 模块。

解决方案 10：

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

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

解决方案 11：

@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。

解决方案 12：

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

解决方案 13：

事实证明，您的起始表示形式是 1 或 0 的整数列表的列表。只需在该表示形式中对它们进行计数即可。

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

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

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

相关推荐
置顶 2024年20款好用的项目管理软件推荐，项目管理提效的20个工具和技巧
2024年20款好用的项目管理软件推荐，项目管理提效的20个工具和技巧
  为什么项目管理通常仍然耗时且低效？您是否还在反复更新电子表格、淹没在便利贴中并参加每周更新会议？这确实是耗费时间和精力。借助软件工具的帮助，您可以一目了然地全面了解您的项目。如今，国内外有足够多优秀的项目管理软件可以帮助您掌控每个项目。什么是项目管理软件？项目管理软件是广泛行业用于项目规划、资源分配和调度的软件。它使项...
项目管理软件   1267  
IPD 项目管理咨询的市场需求与发展
IPD 项目管理咨询的市场需求与发展
  IPD（Integrated Product Development）即集成产品开发，是一套先进的、成熟的产品开发管理理念、模式和方法。随着市场竞争的日益激烈，企业对于提升产品开发效率、降低成本、提高产品质量的需求愈发迫切，IPD 项目管理咨询市场也迎来了广阔的发展空间。深入探讨 IPD 项目管理咨询的市场需求与发展，...
IPD集成产品开发流程   27  
IPD产品开发流程的五个关键阶段解析
IPD产品开发流程的五个关键阶段解析
  IPD（Integrated Product Development）产品开发流程是一套先进的、被广泛应用的产品开发管理体系，它涵盖了从产品概念产生到产品推向市场并持续优化的全过程。通过将市场、研发、生产、销售等多个环节紧密整合，IPD旨在提高产品开发的效率、质量，降低成本，增强企业的市场竞争力。深入了解IPD产品开发...
IPD流程中TR   31  
IPD 测试流程的三大核心要点
IPD 测试流程的三大核心要点
  IPD（Integrated Product Development）测试流程是确保产品质量、提升研发效率的关键环节。它贯穿于产品从概念到上市的整个生命周期，对企业的成功至关重要。深入理解IPD测试流程的核心要点，有助于企业优化研发过程，打造更具竞争力的产品。以下将详细阐述IPD测试流程的三大核心要点。测试策略规划测试...
华为IPD   26  
华为IPD流程中的创新管理与技术突破
华为IPD流程中的创新管理与技术突破
  华为作为全球知名的科技企业，其成功背后的管理体系备受关注。IPD（集成产品开发）流程作为华为核心的产品开发管理模式，在创新管理与技术突破方面发挥了至关重要的作用。深入剖析华为 IPD 流程中的创新管理与技术突破，对于众多企业探索自身发展路径具有重要的借鉴意义。IPD 流程概述IPD 流程是一种先进的产品开发管理理念和方...
TR评审   26  
热门文章
2024年项目管理软件排行榜
2024年20款好用的项目管理软件推荐，项目管理提效的20个工具和技巧
img020
使用 Python 'Requests' 模块的代理
img044
10个项目管理常见问题解答：包括难点和解决方法
项目管理软件
项目延期的原因有哪些？如何有效预防和管理？
项目里程碑计划模板
项目里程碑计划模板怎么写?设定项目里程碑的5个方法
项目管理软件
项目管理指南：制定项目实施计划的6大步骤有哪些？
img081
工程项目管理中的团队建设与激励策略
项目管理软件有哪些？
热门标签
更多>
IPD流程 项目管理 IT项目管理 敏捷开发 项目管理软件 Scrum 敏捷项目管理 IPD流程管理 项目风险管理 项目管理工具 项目经理 极限编程  产品管理  项目经理职责 项目路线图 项目进度管理 测试管理工具 项目预算管理 PMP认证 瀑布式管理 项目范围管理 IT科技 项目管理平台 工程项目管理 项目资源管理 pmp证书考试
云禅道AD
禅道项目管理软件

云端的项目管理软件

尊享禅道项目软件收费版功能

无需维护，随时随地协同办公

内置subversion和git源码管理

每天备份，随时转为私有部署

免费试用