位1的个数

难度: Easy

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 3 中，输入表示有符号整数 -3。

示例 1：

输入：n = 00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

输入：n = 00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

输入：n = 11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

输入必须是长度为 32 的 二进制串 。

进阶：

如果多次调用这个函数，你将如何优化你的算法？

Submission

运行时间: 18 ms

内存: 16.0 MB

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += 1
            n &= n - 1
        return res

Explain

这个题解使用了位运算的技巧。通过 n &= n - 1 这个操作，可以消除 n 的二进制表示中最右边的一个 1。不断重复这个操作，直到 n 变为 0，就可以统计出 1 的个数。具体步骤为： 1. 初始化 res 为 0，用于记录 1 的个数 2. 当 n 不为 0 时，执行下面的循环： a. res 加 1，表示发现一个 1 b. 执行 n &= n - 1，消除最右边的一个 1 3. 返回 res，即为 1 的总个数

时间复杂度: O(m)，其中 m 为 1 的个数，m <= 32

空间复杂度: O(1)

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += 1  # 发现一个 1，计数加 1
            n &= n - 1  # 消除最右边的一个 1
        return res  # 返回 1 的总数

Explore

使用`n &= n - 1`的方法在计算汉明重量时具有特别的优势，因为这种操作直接对数字的二进制形式进行操作，有效地减少了算法的运行时间。每执行一次这个操作，就会消除二进制表示中最右边的1，从而直接减少了接下来处理的位数。这种方法比逐位检查每个位是否为1更高效，因为它不需要处理整个数字的每一位，而只关注数字中的1的位。这样，算法的时间复杂度与数字中1的数量成正比，而不是与位数成正比。

在`n &= n - 1`操作中，n-1的效果是将n的二进制表示中最低位的1变为0，并将这个1后面的所有0变为1。当这个结果与原来的n进行位与操作（&）时，最低位的1及其之后的位都会被清零，因为1与0的与结果为0。这样，n的最低位的1就被消除了。例如，若n为101100，则n-1为101011，n与n-1的结果为101000，即最低位的1被消除。

如果输入整数为最大值，即其二进制表示中所有位都是1，则算法性能将与整数的位数直接相关。由于每次`n &= n - 1`操作都会消除一个1，因此如果所有位都是1，算法将需要执行与整数位数相同的次数。例如，一个32位的整数，如果所有位都是1，算法将执行32次操作。虽然这仍然比检查每一位要快，因为总的操作次数与1的数量相等，但在这种极端情况下，算法的时间复杂度为O(b)，其中b是二进制位数。

这种位运算方法的优点在于其效率和简洁性。它直接在二进制级别操作，只关注1的位，因此操作次数通常少于二进制位数，尤其是当1的个数远少于位数时。其时间复杂度与1的数量成正比，而不是位数。缺点是，如果数字的二进制表示中1的数量接近总位数，那么这种方法的效率优势就不那么明显。另一个小缺点是，这种方法需要对位运算有一定的理解，对初学者来说可能不够直观。