338.比特位计数

这道题目的意思是，计算每个数字的二进制表示里 1 的数量。其实，计算方法，也比较简单，就是写个循环，计算当前循环中的数字的 bit 位数。怎么计算一个数字的 bit 里的 1 的位数呢？

我想到的方法很简单，就是使用 “位与” 计算，一个整数，与 1 进行 & 运算，结果 1，说明最低位是 1，结果是 0，说明最低位是 0。然后，我们把这个数字往右移 1 位。重复这个过程，直到这个数字变为 0。就统计出了所有的 1 的数量。

然后我写出了这个算法：

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def countBits(self, num: int) -> List[int]:
        res = []
        for i in range(num + 1):
            cnt = 0
            n = i
            while n > 0:
                cnt += n & 1
                n = n >> 1
            res.append(cnt)
        return res

这个算法的复杂度是多少呢？第一重循环是 n 次，第二重循环最多是 log2(n)次，随着数字的缩小，次数还会减少。具体就比较复杂了：[
O(\sum_{i=1}^{n}\log_2i)
]但是，原来题目里有个提示，就是，它问能不能用 O(n) 的算法计算出来。还提示了一句，算法的空间复杂度是 O(n)。你看，上面那个算法空间复杂度是 O(1) 的，没有用额外的空间。而现在明告诉你用 O(n)，其实就是说这题目可以使用递推法。现在 LC 的人流行叫动态规划，不过，我觉得动态规划在这个场景里没有递推法听起来更明白。不过写起来是一回事。

什么是递推法，就是现在第 n 个解，可以用 n 以前的解推理得到。算是动态规划的特殊情况吧。不像动态规划理解起来那么抽象。当然，我说得头头是道的，当时看到题目的时候，脑子是空白的，这个读者你知道就行了。

其实，从我写的那个式子里就看出一种来。比如我用了移位操作，往右移位，其实就是除以 2 的意思。举个例子，假如我现在循环到 5 这个数字，最低位是个 1，然后往右移，继续循环，往右移后其实数字变成了 2，而刚才，其实计算过 2 里面的比特数的，但是在我的算法里，右继续计算了，如果我们不计算，而是查表所得，这里就不用循环了。不是么？

算法可以改改：

1
2
3
4
5
6

class Solution:
    def countBits(self, num: int) -> List[int]:
        res = [0]
        for i in range(1, num + 1):
            res.append(res[i >> 1] + (i & 1))
        return res

这个算法意思就是，先计算最低位的 1 的数量，然后高位部分，查表就行了。有了这个算法，官方题解的另一个算法就不难理解了。既然我们可以把最低位和上面部分分开计算。显然也可以把最高位和下面部分分开。不过，不像最低位这么直观。

我们可以把一个数字分解成，最高位 1 和剩余部分，举个例子：假如 5 二进制表示是 101，可以分解为 101 = 100 + 1，高位是 4，剩余的是 1，也就是 5 是 4 的比特数加上 1 的比特数。计算到 5 的时候，前面 1 和 4 肯定早就计算出来了。4 是什么呢？就是 5 前面最近的一个 2 的整数次幂。而怎么判断一个数字是 2 的整数次幂呢？i & (i - 1) == 0，想明白了么？

具体完整算法我就不写了。去看官方解答或者自己写也不难。