位 1 的个数

标签: 位运算

难度: Easy

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

提示：

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

示例 1：

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

示例 2：

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

示例 3：

输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3）
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

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

注意：本题与主站 191 题相同：https://leetcode-cn.com/problems/number-of-1-bits/

Submission

运行时间: 56 ms

内存: 14.9 MB

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += 1
            n &= n - 1  # 消去最右边的1
        return res

Explain

这个题解使用了一种称为'位操作的技巧'来计算二进制中1的个数。核心思想是使用一个循环，每次循环中使用n &= n - 1的操作，该操作将n的二进制表示中最低位的1变为0。这是因为从二进制的角度来看，n - 1操作会将最低位的1变为0，并将所有更低位的0变为1。因此，当n和n - 1进行AND操作时，就会抹去最低位的1。循环每执行一次，就计数一次，直到n变为0为止。

时间复杂度: O(k)，其中k是数字n中1的数量

空间复杂度: O(1)

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0  # 用于计数1的个数
        while n:  # 当n不为0时循环
            res += 1  # 增加1的计数
            n &= n - 1  # 消去n最低位的1
        return res  # 返回1的总数

Explore

操作 `n &= n - 1` 通过将 n 与 n - 1 进行按位与操作来有效去除 n 的最低位的 1。考虑 n 的二进制表示中，最低位的 1 及其右边的所有位会在 n-1 中变成 0 和一串 1，因此当 n 和 n - 1 进行按位与操作时，从最低位的 1 开始到最右边的所有位都会变成 0。例如，假设 n = 22，其二进制表示为 10110。因此 n - 1 = 21，二进制表示为 10101。执行 n &= n - 1 操作后，n 变为 10100（20），有效去除了最低位的 1。

是的，整数的有符号和无符号表示在不同编程语言中可能会影响循环的执行。例如，在 C 或 C++ 中，如果一个整数是有符号的，当它变得非常小（如负数）时，与操作可能会导致循环以意外的方式继续执行。在 Python 中，整数类型是自动管理大小的，所以 `while n:` 循环会在 n 变为 0 时停止，而不受正负影响。但在有符号整数的环境中，可能需要额外的条件或明确处理负数的情况。

确实，如果使用这种方法处理更长的二进制数（如 64 位整数），在最坏的情况下性能可能不是最优的。循环将执行的次数等于二进制表示中 1 的个数，因此对于包含许多 1 的长二进制数，这种方法的执行时间将随着位数的增加而增加。虽然这种方法在位数较少时非常高效，但在处理更长的二进制数时可能需要考虑其他更高效的算法，如并行位计数等技术。

对于非常大的输入值，特别是接近整数类型上限的数，这种方法的性能主要受到输入值中 1 的数量的影响。如果输入值接近整数上限且包含较多的 1，那么每次操作去除一个 1 的效率将减慢，因为每次循环都需要执行 n &= n - 1 操作。尽管如此，这种方法的时间复杂度与位中 1 的数量成正比，因此对于大多数实际应用来说，它仍然是高效的。但在极端情况或性能敏感的应用中，可能需要探索更快的算法。