比特位计数

试题来源：力扣（英文），力扣（中文）

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

Input:n = 5
Output: [0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

问题分析：

如果一个数字 i 的二进制中 1 的个数是 m ，当我们把这个数字往左移一位（乘以 2 ）的时候，他的二进制中 1 的个数还是 m 。如果在加上 1 ，那么他的二进制中 1 的个数一定比 i 的二进制中 1 的个数多 1，所以我们可以得到 f[i] = f[i>>1] + (i &1) 。

public int[] countBits(int num) {
    int[] res = new int[num + 1];
    for (int i = 1; i <= num; i++)
        res[i] = res[i >> 1] + (i & 1);
    return res;
}

在前面我们讲位运算的时候，说过 i & (i-1) 可以消去数字 i 的二进制中最右边的 1 ，所以 i & (i-1) 的二进制中 1 的个数一定比 i （i 不等于0）的二进制中 1 的个数少 1 。

public int[] countBits(int num) {
    int[] res = new int[num + 1];
    for (int i = 1; i <= num; ++i)
        res[i] = res[i & (i - 1)] + 1;
    return res;
}