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

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个回答

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

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

- ArekKulczycki · Answer 1

@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设置为参数类型以避免OverflowError。

- Praveen Narala · Answer 2

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

- Marcin · Answer 3

原来你的起始表示是一个由整数列表组成的列表，这些整数要么是1，要么是0。只需在该表示中对它们进行计数即可。

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

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

生成列表后，您可以进行常量时间查找。请参考@PaoloMoretti的答案，了解如何很好地实现此功能。当然，您不必将所有内容都保存在内存中 - 您可以使用某种持久化键值存储，甚至是MySql。（另一种选择是实现自己的简单基于磁盘的存储）。