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

Question

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

174

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

bin(n).count("1")

但我想知道是否有更快的方法来完成这个任务？

- zidarsk8

相关：https://dev59.com/KnRC5IYBdhLWcg3wG9Rb - dusan

1

如果你的“整数”比标准的Python int更长，那么你使用的是什么样的表示方法？这难道没有自己的计算方法吗？ - Marcin

1

在Python 3.6+中，可以尝试使用f"{n:b}"代替bin(n)。这样做应该更快，并且不会出现烦人的“0b”前缀。此外，您还可以执行类似f"{n:032b}"的操作，以获得宽度为32的零填充位串。 - PM 2Ring

@PM2Ring 看起来更慢。（请看我的基准测试。）-- 此外，如果所有的问题都在于字符串中的1的数量，则0b前缀或零填充并不重要。 - user202729

1

@user202729 哦，好的。感谢您进行基准测试。我认为f-string会更快，因为它避免了显式函数调用。另一方面，bin是一个C函数，比Python函数调用的开销要小。当然，在这里，0b前缀和零填充是无关紧要的，我只是提到这些事情是为了那些可能需要在其他上下文中了解它们的读者。 - PM 2Ring

13个回答

151

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

我尝试了将Óscar和Adam的解决方案分别适应为64位和32位块以处理整数。两者都比bin(n).count("1")慢至少十倍（32位版本所需的时间大约多一半）。

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

- kindall

8

+1！然而，它的逆命题并不准确。应该说明：bin(n).count("0")是不准确的，因为有前缀'0b'。对于那些计算"零"的情况，需要使用bin(n)[2:].count('0')。 - the wolf

12

不知道要填充多少字节，就无法准确计算零比特位的数量。对于 Python 的长整数来说尤其麻烦，因为它可能是任意长度。 - kindall

2

尽管这些是单个整数的快速选项，但请注意其他答案中提出的算法可能潜在地可以向量化，因此如果在大型numpy数组的许多元素上运行，则会更快。 - gerrit

2

我已经使用了bin(n).count("1")。然而，只能击败60%的Python提交。@[leetcode]（https://leetcode.com/submissions/detail/91593414/） - northtree

1

https://docs.python.org/3.10/library/stdtypes.html#int.bit_count 计算设置位的数量。 - user5556825

显示剩余4条评论

38

您可以采用以下算法：

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

- Adam Zalcman

我真的不知道这如何适用于10,000位数，但我喜欢这个解决方案。你能否给我一些提示，告诉我如何将其应用于更大的数字？ - zidarsk8

我没有看到你在这里处理的位数。你考虑过用像C这样的低级语言编写数据处理代码吗？也许作为你的Python代码的扩展？与Python中的大数字相比，使用C中的大数组可以显著提高性能。话虽如此，你可以通过添加仅8行代码来重写CountBits()以处理10k位数字。但由于巨大的常量，它将变得笨重。 - Adam Zalcman

3

您可以编写代码生成常数序列，并设置处理循环。 - Karl Knechtel

这个答案的巨大优势在于它可以对处理大型numpy数组的情况进行向量化。 - gerrit

“操作次数随参数的对数增长（即与参数的位数线性增长）是错误的。实际上，（加法、按位）操作的数量是（渐近地）log(log n)或log（比特数）。时间复杂度为log(n) log(log n)或（比特数*log(比特数))——因为Python的整数是任意精度（技术上Python 2中的'int'数据类型是64位，但OP在不知情的情况下使用了'long'）——所以它几乎肯定比单个数字的gmpy慢。” - user202729

22

以下是 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，它将起作用。

- Óscar López

这很聪明。查找资料而不是凭空猜测答案是完全适当的！ - MrGomez

1

你有进行基准测试吗？在我的机器上使用Python 2.7，我发现这实际上比 bin(n).count("1") 要慢一些。 - David Weldon

@DavidWeldon 我没有，请您发布一下您的基准测试结果好吗？ - Óscar López

%timeit numberOfSetBits(23544235423): 1000000 次循环，3 次取最佳结果：每次循环 818 纳秒; %timeit bitCountStr(23544235423): 1000000 次循环，3 次取最佳结果：每次循环 577 纳秒. - gerrit

7

然而，numberOfSetBits在 841 微秒内处理完我的 864x64 numpy.ndarray。而使用 bitCountStr，我必须显式循环，需要 40.7 毫秒，即几乎慢了 50 倍。 - gerrit

13

我真的很喜欢这种方法。它简单而且非常快，但也没有位数限制，因为Python有无限的整数。

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

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

- Robotbugs

看起来很不错，但只适用于非常“稀疏”的整数。平均而言，速度相当慢。尽管如此，在某些使用情况下它看起来确实非常有用。 - zidarsk8

1

我不太确定你所说的“平均而言它相当慢”是什么意思。相对于什么而言很慢？你是指相对于其他未引用的Python代码而言很慢吗？这个算法计算平均数比逐位计算快两倍。事实上，在我的MacBook上，它每秒可以计算1260万个位，比我自己数还要快得多。如果你有另一个通用的Python算法，可以处理任何长度的整数，并且比这个更快，我想听听。 - Robotbugs

1

我承认这比Manuel上面的答案要慢。 - Robotbugs

2

平均而言，对于具有10000位数字的10000个数字进行位计数，使用bin(n).count("1")只需0.15秒，但使用您的函数需要3.8秒。如果数字中设置的位非常少，则它将快速工作，但是如果您选择任何随机数字，则上述函数的速度将慢几个数量级。 - zidarsk8

好的，我接受了。我想我只是有点刻薄，因为你有点不太精确，但你是完全正确的。在我的评论之前，我还没有使用过Manuel上面的方法进行测试。它看起来非常笨重，但实际上非常快。我现在正在使用一个类似的版本，但字典中有16个值，这比他引用的那个版本更快。但是记录一下，我在应用程序中只使用了几个位设置为1的位。但对于完全随机的位，是会以大约50:50的比例出现，长度稍微变化一下。 - Robotbugs

还要感谢你抽出时间来实际输入并分析我引用的函数。这是受到赞赏的。 - Robotbugs

11

根据这个post，这似乎是最快的Hamming weight实现之一（如果您不介意使用约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

- Paolo Moretti

我已经编辑了我的问题，以明确表明我需要处理大数（10k位及以上）。优化32位整数的某些内容可能不会有太大的差异，因为计数的数量必须非常大，这将导致执行时间缓慢。 - zidarsk8

但是GMP正是用于非常大的数字，包括您提到的尺寸以及远远超出这些尺寸的数字。 - James Youngman

1

如果您在 POPCOUNT_TABLE16 中使用 array.array，那么内存使用将更加高效，因为它将被存储为整数数组，而不是 Python int 对象的动态大小列表。 - gsnedders

4

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

- Manuel

这个运行速度很快。但是至少在p3上有一个错误，[1：]应该改为[2：]，因为oct（）在字符串之前返回“0o”。如果使用hex（）并制作一个16项字典，则代码运行速度会更快。 - Robotbugs

你可以通过使用"%o" % a而不是oct(a)来避免删除前两个字符。（对于建议的十六进制改进，使用%x % a） - kindall

3

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

关于这种解决方案，不幸的是，与 Python 3 中的 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))

它可以与Python 2和3一起使用；然而，如果Python 2中没有可用的解决方案，则不予考虑。

这里没有列出所有的解决方案。

结果：

Python 2：对于 <= 16 个比特位，“没有lambda的查找列表”是最快的（比“bin count”快25％，比“有lambda的查找列表”快6％）；大于16位则“bin count”最快。（我没有为Python 2安装gmpy）
Python 3：结果差不多。
- “没有lambda的查找bytes”与“没有lambda的查找列表”相似（+/-2%）。
- 在所有情况下，gmpy都比“bin count”快，但比“没有lambda的查找列表”慢约5％（当 numBit <= 16 时）。
- “to_bytes”差不多。
- 使用f-string比“bin count”慢约10％。
PyPy3：lambda已经几乎不再产生额外开销，而“to_bytes”版本变得更快（比“bin count”快两倍）；然而，我无法安装gmpy。

- user202729

转念一想，速度可能会有很大的差异，取决于环境。我刚刚在SageMathCell上尝试了你的Python 3.7基准测试脚本，f-strings大多数情况下更快。但是我是在Sage模式下运行的。（在纯Python模式下会抛出错误，但该模式并非真正的纯Python，并且对字符串字面值的处理不稳定，例如你必须使用"\\n"来获取换行符）。 - PM 2Ring

如果适用的话，看到没有额外函数调用的时间会很有趣。这里是一个计时表达式而不是函数的简短示例：https://stackoverflow.com/a/50212230 顺便说一句，最好做几个（3-5）timeit循环的重复，并使用最小值，正如我在这里讨论的那样 https://dev59.com/vaHia4cB1Zd3GeqPRUwg#43678107 - PM 2Ring

2

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

将n个位作为ceil(n/32.)个32位整数的数组进行存储。然后，您可以以与使用整数相同（或类似）的方式使用numpy数组，包括使用它们来索引另一个数组。

该算法基本上是并行计算每个单元格中设置的位数，然后总结每个单元格的位数。

setup = """
import numpy as np
#Using Paolo Moretti's answer https://dev59.com/rmkw5IYBdhLWcg3wiq-s#9829855
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模块。

- leewz

1

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

- Ariad

1

目前来看，你的回答不够清晰。请编辑并添加更多细节，以帮助他人理解这如何回答所提出的问题。你可以在帮助中心找到关于如何编写好的答案的更多信息。 - Community

就结果而言，bytes.maketrans(bytes(range(1<<8)),bytes((bin(i).count('1') for i in range(1<<8)))) 和 bytes(bin(i).count('1') for i in range(1 << 8)) 是相同的。 - Mechanic Pig

调用函数可以加速事情的进行。 - Ariad

@Ariad 是的，它比 bin().count('1') 更快，所以加一分。我只是指出了可以修改的部分。另外，你能把代码注释中的文本描述移到正文中吗？这里的人似乎更喜欢在正文中而不是在代码注释中看到描述（我的浏览器翻译也无法处理代码注释）。 - Mechanic Pig

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Chris_Rands · Accepted Answer

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。