LeetCode338.比特位计数

先以2，3为例，它们的二进制分别是10、11，可以看到，忽略其二进制中最高位的1之后，这组数中二进制位为1的数量分别和数字0，1中二进制位为1的数量相同，再以4，5，6，7为例，他们的二进制分别是100、101、110、111，忽略其二进制中最高位的1之后，这组数中二进制位为1的数量分别和数字0，1，2，3中二进制位为1的数量相同，至此可以得出规律：

res[i+j]=res[j]+1;其中i为2的幂次数（2，4，8等等），j的取值范围是[0,i);

class Solution {
    public int[] countBits(int n) {
        if(n==0) return new int[]{0};
        if(n==1) return new int[]{0,1};
        int[] res = new int[n+1];
        res[0]=0;res[1]=1;
        for(int i=2;i<=n;){
            for(int j=0;j<i;j++){
                if(i+j<=n){
                    res[i+j]=res[j]+1;
                }else{
                    break;
                }
            }
            i=2*i;
        }
        return res;
    }
}