image.png
线性时间求解0 - num的每个数的二进制有几个1组成。
对于一个数n，可以通过从n >>> 1递归而得，即n = n >>> 1 + (n & 1)
稍微解释一下，如果n是5的话，那么n的二进制形式就是101，n >>> 1就是2，二进制形式就是10，因为我们是自底向上计算的，所以上述的等式就是通过已经计算出来的高2位的值再加上最后一位的值的1的个数，当做n中一共有多少个1
public int[] countBits(int num) {
int[] res = new int[num + 1];
for (int i = 0; i < res.length; i++) res[i] = res[i >>> 1] + (i & 1);
return res;
}
