338. 比特位计数

题目

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

思路

对于所有的数字，只有两类：
**奇数：**二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。
举例：
0 = 0 1 = 1
2 = 10 3 = 11
偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。
举例：
2 = 10 4 = 100 8 = 1000
3 = 11 6 = 110 12 = 1100
初始化 dp[0] = 0;

代码

class Solution {
    
    public int[] countBits(int n) {
    
        int[] res = new int[n+1];
        res[0] = 0;
        for(int i = 1; i <= n; i++){
    
            if((i & 1) != 0) //奇数
                res[i] = res[i-1] + 1;
            else
                res[i] = res[i/2];
        }
        return res;
    }
}