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; } }