统计从 0 ~ n 每个数的二进制表示中1的个数

统计从 0 ~ n 每个数的二进制表示中1的个数

问题

给定一个非负整数num。每一个数字我范围在0≤≤num计算1的二进制表示的数量和返回一个数组。

Input: 5
Output: [0,1,1,2,1,2]

代码

对于数字 6(110)，它可以看成是 4(100) 再加一个 2(10)，因此 dp[i] = dp[i&(i-1)] + 1;

public int[] countBits(int num) {
    int[] ret = new int[num + 1];
    for(int i = 1; i <= num; i++){
        ret[i] = ret[i&(i-1)] + 1;
    }
    return ret;
}