338. 比特位计数

示例 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

 class Solution {
        public int[] countBits(int n) {
            int[] dp = new int[n + 1];
            dp[0] = 0;
            // 如果当前数字i为奇数,则前一个数是偶数(最后一个数字为0),那前一个数字加1,就是二进制末位的0变成了1而已,1的数量加了1
            // 如果当前数字i为偶数,那么其比特位计数和其i/2的值是一样的,为一个数是偶数那么他的二进制比他的一半的二进制只是多了一个0而已
            for (int i = 1; i <= n; i++) {
                //如果是奇数
                if ((i&1)==1){
                    dp[i]=dp[i-1]+1;
                }else{
                    dp[i]=dp[i/2];
                }
            }
            return dp;
        }
    }