题目描述
这是 LeetCode 上的 338. 比特位计数 。
Tag : 「位运算」、「数学」、「线性 DP」
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2 输出: [0,1,1] 复制代码
示例 2:
输入: 5 输出: [0,1,1,2,1,2] 复制代码
进阶:
- 给出时间复杂度为 O(n*sizeof(integer))O(n∗sizeof(integer)) 的解答非常容易。但你可以在线性时间 O(n)O(n) 内用一趟扫描做到吗？
- 要求算法的空间复杂度为 O(n)O(n) 。
- 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。
朴素解法
这道题要对每个数进行统计，因此不会有比 O(n)O(n) 更低的做法。
而很容易想到的朴素做法是对每个数进行「位运算」计数，每个数都是 32 位的，因此是一个 O(32n)O(32n) 的做法。
32 作为常数不算大，OJ 要想做到卡掉 O(32n)O(32n)，同时确保 O(n)O(n) 都能过，需要把数据出到 10^6106。
根据在 LeetCode 的做题经验，通常 10^6106 是属于必须要进行说明的数据范围了，但是本题没有，所以我估摸着数据范围最多也就 10^4104 - 10^5105。
PS. 规范的题目应该无论数据范围是多少，都应该进行说明。
class Solution { public int[] countBits(int n) { int[] ans = new int[n + 1]; for (int i = 0; i <= n; i++) ans[i] = getCnt(i); return ans; } int getCnt(int u) { int ans = 0; for (int i = 0; i < 32; i++) ans += (u >> i) & 1; return ans; } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：使用与输入同等规模的空间存储答案。复杂度为 O(n)O(n)
动态规划
事实上，这道题是有严格 O(n)O(n) 的解法的，要求 O(n)O(n) 复杂度又是输出方案的题，通常就是递推的 DP 题。
用已算出的值去凑出要算的值。
那么对于这类问题我们该如何考虑呢？一般是靠经验，如果实在没见过这类题型的话，我们就需要在纸上画一下，分析一下我们朴素做法的最后一步是怎么进行的。
不失一般性的，假设当前我要统计的数的 i，i 对应的二进制表示是
00000...0010100101（共 32 位）
如果我们是使用「朴素解法」求解的话，无论是从高位进行统计，还是从低位进行统计，最后一位扫描的都是边缘的数（如果是 1 就计数，不是 1 就不计数）。
- 从低位到高位，最后一步在扫描最高位之前，统计出 1 的个数应该等同于将
i左移一位，并在最低位补 0，也就是等于ans[i << 1]，这时候就要求我们在计算i的时候i << 1已经被算出来（从大到小遍历） - 从高位到低位，最后一步在扫描最低位之前，统计出 1 的个数应该等同于将
i右移一位，并在最高位补 0，也就是等于ans[i >> 1]，这时候就要求我们在计算i的时候i >> 1已经被算出来（从小到大遍历）
通过对「朴素做法」的最后一步分析，转移方程就出来了：
- 当从大到小遍历 ：f(i) = f(i << 1) + ((i >>31 ) \& 1)f(i)=f(i<<1)+((i>>31)&1)
- 当从小到大遍历 ：f(i) = f(i >> 1) + ( i \& 1 )f(i)=f(i>>1)+(i&1)
class Solution { // 从小到大遍历 public int[] countBits(int n) { int[] ans = new int[n + 1]; // ans[i] = 「i >> 1 所包含的 1 的个数」+「i 的最低位是否为 1」 for (int i = 1; i <= n; i++) ans[i] = ans[i >> 1] + (i & 1); return ans; } } 复制代码
class Solution { // 从大到小遍历 public int[] countBits(int n) { int[] ans = new int[n + 1]; for (int i = n; i >= 0; i--) { // 如果计算 i 所需要的 i << 1 超过 n，则不存储在 ans 内，需要额外计算 int u = i << 1 <= n ? ans[i << 1] : getCnt(i << 1); // ans[i] =「i << 1 所包含的 1 的个数」 + 「i 的最高位是否为 1」 ans[i] = u + ((i >> 31) & 1); } return ans; } int getCnt(int u) { int ans = 0; for (int i = 0; i < 32; i++) ans += (u >> i) & 1; return ans; } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：使用与输入同等规模的空间存储答案。复杂度为 O(n)O(n)
位运算说明
- a >> b & 1 代表检查 a 的第 b 位是否为 1，有两种可能性 0 或者 1
- a += 1 << b 代表将 a 的第 b 位设置为 1 (当第 b 位为 0 的时候适用)
如不想写对第 b 位为 0 的前置判断，a += 1 << b 也可以改成 a |= 1 << b
PS. 1 的二进制就是最低位为 1，其他位为 0 哦
在之前的题解我就强调过，以上两个操作在位运算中使用频率超高，建议每位同学都加深理解。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.338 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
