E191.位1的个数

bit manipulation, divide and conquer, https://leetcode.cn/problems/number-of-1-bits/

给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。

汉明重量是符号序列中非零符号的数量，在二进制数据中特指1的个数

示例 1：

输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。

示例 2：

输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。

示例 3：

输入：n = 2147483645
输出：30
解释：输入的二进制串 1111111111111111111111111111101 中，共有 30 个设置位。

提示：

• 1 <= n <= 2^31 - 1

进阶：

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

这个问题是关于计算一个正整数二进制表示中 1 的个数（汉明重量）。

下面为您提供几种不同的解决方法，以及针对“多次调用”进阶问题的优化思路。

---

方法一：Brian Kernighan 算法（最经典的位运算方法）

思路： 利用 n & (n - 1)。这个操作可以消除二进制表示中最低位的 1。 例如：对于 n = 12 (1100)：

1. n - 1 = 11 (1011)，1100 & 1011 = 1000（清除了最低位的 1）。
2. 重复上述操作，直到 n 变为 0。循环执行的次数就是二进制中 1 的个数。

这种方法的时间复杂度取决于 1 的个数，而不是二进制的位数，因此非常高效。

代码实现：

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

• 时间复杂度：$O(k)$，其中 $k$ 是 n 的二进制表示中 1 的个数，最坏情况下为 $O(32)$。
• 空间复杂度：$O(1)$。

---

方法二：利用内置函数（最简短的 Pythonic 方法）

思路： 在 Python 3.10 及以上版本中，可以直接使用 int.bit_count() 方法。在旧版本中，也可以使用 bin(n).count('1')。

代码实现：

class Solution:
    def hammingWeight(self, n: int) -> int:
        return n.bit_count()  # Python 3.10+
        # 或者使用：return bin(n).count('1')

• 时间复杂度：$O(\log n)$。
• 空间复杂度：$O(1)$（若使用 bin，则为 $O(\log n)$ 字符串开销）。

---

进阶：如何应对多次调用（优化方案）

如果这个函数被频繁、海量地调用，可以通过查表法（Lookup Table）进行空间换时间的优化。

思路： 一个 32 位的整数可以被拆分为 4 个 8 位的字节（Byte），或者 2 个 16 位的半字。 我们可以预先计算好所有 8 位整数（0 到 255）中 1 的个数，并存入一个长度为 256 的数组。 对于输入的任意 32 位整数，我们只需要将其拆分为 4 个字节，分别查表，然后将结果相加。

这样，每次查询只需要进行 4 次移位/按位与操作以及 4 次数组查询。

代码实现：

class Solution:
    # 类变量：只在类加载时初始化一次 256 大小的查找表
    # 也可以使用 @cache / @lru_cache 装饰器实现缓存
    _lookup = [0] * 256
    for i in range(256):
        _lookup[i] = (i & 1) + _lookup[i >> 1]

    def hammingWeight(self, n: int) -> int:
        # 将 32 位整数拆分为 4 个 8 位组分别查表
        return (
            self._lookup[n & 0xFF] +
            self._lookup[(n >> 8) & 0xFF] +
            self._lookup[(n >> 16) & 0xFF] +
            self._lookup[(n >> 24) & 0xFF]
        )

• 初始化时间复杂度：$O(256)=O(1)$
• 单次查询时间复杂度：$O(1)$
• 空间复杂度：$O(256)$ 存储查找表。

如果多次调用的参数重复率极高，还可以直接利用 Python 的 @functools.lru_cache 装饰器对函数进行缓存，以便直接返回已计算过的值。