Python:试图计算整数中的1位数，但缺少1位

Question

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

当我在下面运行我的代码时，似乎只有两个1被识别.为什么会这样呢？

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        sum = 0
        
        for i in str(n):
            sum += int(i)
            
        return sum 

​

​

我想我误解了一些概念。希望你能给我一些指导。

Answer 1

Python 3.10引入了计数()，但是如果您必须自己实现该算法，那么您可以尝试如下所示：

test.py:

def count(n):
    bits = 0

    while n:
        bits += 1
        n &= n - 1

    return bits


def main():
    n = 0b110001010000000000111
    c = count(n)

    print(f"Bit length: {n.bit_length()}, bits: {c}")


if __name__ == "__main__":
    main()

测试：

$ python test.py
Bit length: 21, bits: 7

该算法的时间复杂度为O(k)，其中k为设置为1的位数。

Answer 2

将str(n)转换为bin(n)[2:]。通过这种方式，您将得到带有省略"0b“前缀的n的二进制表示字符串。

顺便说一句，你不需要在循环中手动计数。Python有.count()

return bin(n).count("1")