二进制中1的个数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

解法一：两重循环直接计算

public int[] countBits(int num) {
    int[] ans = new int[num+1];
    if(num == 0) ans[0] = 0;
    for(int i = 1; i <= num; i++){
        int size = 0;
        int temp = i;
        while(temp > 0){
            if(temp%2 == 1){
                size++;
            }
            temp /= 2;
        }
        ans[i] = size;
    }
    return ans;
}

• 时间复杂度：O(k*num);

• 空间复杂度：O(1),除了返回的数组以外，空间复杂度为常数。

解法二：动态规划，最低有效位

public int[] countBits(int num) {
    int[] bits = new int[num+1];

    for(int i = 1; i <= num; i++){
        bits[i] = bits[i >> 1] + (i&1);
    }

    return bits;
}