338.比特位计数

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

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 –> 0
1 –> 1
2 –> 10

示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 –> 0
1 –> 1
2 –> 10
3 –> 11
4 –> 100
5 –> 101

提示：

• 0 <= n <= 105

题解：

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        // 偶数的二进制数，1的个数一定和该数除以2以后的那个数一样多
        // 2 = 10 4 = 100 8 = 1000
        // 因为除以2就是右移一位，就是把0抹掉而已，1的个数是不变的
        // 而奇数，在二进制表示中，奇数一定比前面的那个偶数多一个1
        for (int i = 1; i <= n; i++) {
            if (i % 2 != 0) {
                res[i] = res[i - 1] + 1;
            } else {
                res [i] = res[i >> 1];
            }
        }
        return res;
    }
}