338. 比特位计数
题目描述
输入一个整数 n。对 0 到 n 之间（含两端）的每个整数 i，统计它的二进制表示里有多少个 1。
返回长度为 n + 1 的数组 ans，其中 ans[i] 就是 i 的二进制中 1 的个数。
不要借助语言自带的计数函数，例如 C++ 的 __builtin_popcount。
输入：n = 2 输出：[0,1,1]
解释：0、1、10 中 1 的个数分别是 0、1、1。
输入：n = 5 输出：[0,1,1,2,1,2]
解释：0 到 5 的二进制依次为 0,1,10,11,100,101。
数据范围
0 <= n <= 10^5
进阶：O(n log n) 的做法很直接。能否只扫描一遍，在 O(n) 时间内得到结果？
解题思路：动态规划（最低有效位）
把 i 右移一位得到 i>>1，它的二进制就是 i 去掉最低位。i>>1 比 i 小，其答案已经算好，所以 ans[i] = ans[i>>1] + (i&1)，其中 i&1 就是被去掉的最低位。从小到大一遍递推即可。
为什么正确
计算 ans[i] 时，ans[0..i-1] 已全部正确，而 i>>1 < i。
复杂度分析
时间 O(n)，空间 O(1)（不计输出）。
易错点
运算优先级：在 C++/Java/JS 中 + 的优先级高于 &，(i & 1) 必须加括号；ans 长度是 n+1，不要漏掉 0。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def countBits(self, n: int) -> List[int]:
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i >> 1] + (i & 1)
return ansclass Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = 1; i <= n; i++)
ans[i] = ans[i >> 1] + (i & 1);
return ans;
}
}class Solution {
public:
vector<int> countBits(int n) {
vector<int> ans(n + 1, 0);
for (int i = 1; i <= n; i++)
ans[i] = ans[i >> 1] + (i & 1);
return ans;
}
};func countBits(n int) []int {
ans := make([]int, n+1)
for i := 1; i <= n; i++ {
ans[i] = ans[i>>1] + (i & 1)
}
return ans
}var countBits = function(n) {
const ans = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++)
ans[i] = ans[i >> 1] + (i & 1);
return ans;
};function countBits(n: number): number[] {
const ans: number[] = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++)
ans[i] = ans[i >> 1] + (i & 1);
return ans;
}其他解法
Brian Kernighan 算法逐个计数，O(n log n)；两种动态规划都是 O(n)，主解法从 i >> 1 转移，另一种从 i & (i - 1) 转移。
解法 2：Brian Kernighan 算法 时间 O(n log n)，空间 O(1)
对每个 i 单独计数。反复执行 x &= x - 1，每次会把 x 最低的一个 1 清零。执行的次数就是 x 中 1 的个数。
不依赖前面的结果，可以单独用来求任意整数的 1 的个数。每个数最多循环 log n 次，整体比动态规划慢。
class Solution:
def countBits(self, n: int) -> List[int]:
ans = [0] * (n + 1)
for i in range(1, n + 1):
x, cnt = i, 0
while x:
x &= x - 1
cnt += 1
ans[i] = cnt
return ansclass Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = 1; i <= n; i++) {
int x = i, cnt = 0;
while (x != 0) {
x &= x - 1;
cnt++;
}
ans[i] = cnt;
}
return ans;
}
}class Solution {
public:
vector<int> countBits(int n) {
vector<int> ans(n + 1, 0);
for (int i = 1; i <= n; i++) {
int x = i, cnt = 0;
while (x) {
x &= x - 1;
cnt++;
}
ans[i] = cnt;
}
return ans;
}
};func countBits(n int) []int {
ans := make([]int, n+1)
for i := 1; i <= n; i++ {
x, cnt := i, 0
for x != 0 {
x &= x - 1
cnt++
}
ans[i] = cnt
}
return ans
}var countBits = function(n) {
const ans = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
let x = i, cnt = 0;
while (x) {
x &= x - 1;
cnt++;
}
ans[i] = cnt;
}
return ans;
};function countBits(n: number): number[] {
const ans: number[] = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
let x = i, cnt = 0;
while (x) {
x &= x - 1;
cnt++;
}
ans[i] = cnt;
}
return ans;
}解法 3：动态规划（最低设置位） 时间 O(n)，空间 O(1)
i & (i - 1) 是把 i 最低的一个 1 清零后的数，它比 i 小，结果已经算好。所以 ans[i] = ans[i & (i - 1)] + 1。
和主解法一样是 O(n) 的动态规划，只是转移来源不同。它把 Brian Kernighan 的一步操作变成了状态转移。
class Solution:
def countBits(self, n: int) -> List[int]:
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i & (i - 1)] + 1
return ansclass Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = 1; i <= n; i++)
ans[i] = ans[i & (i - 1)] + 1;
return ans;
}
}class Solution {
public:
vector<int> countBits(int n) {
vector<int> ans(n + 1, 0);
for (int i = 1; i <= n; i++)
ans[i] = ans[i & (i - 1)] + 1;
return ans;
}
};func countBits(n int) []int {
ans := make([]int, n+1)
for i := 1; i <= n; i++ {
ans[i] = ans[i&(i-1)] + 1
}
return ans
}var countBits = function(n) {
const ans = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++)
ans[i] = ans[i & (i - 1)] + 1;
return ans;
};function countBits(n: number): number[] {
const ans: number[] = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++)
ans[i] = ans[i & (i - 1)] + 1;
return ans;
}