描述 Description

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

• It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
• Space complexity should be O(n).
• Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

[Counting Bits]

分析 Analysis

方法1

利用“number of 1 bits”中的方法，从0到num分别求0 ≤ i ≤ num时i对应的bit位为1的个数。

时间复杂度 O(n*sizeof(integer))。

方法2

当二进制位数多1位的时候，高位为1，剩下的和之前的是一样的。

list[i] = list[i%n]+1 //n = floor(log(i))

list[2] = list[2%2]+1

list[5] = list[5%4]+1

list[12] =list[12%8]+1

方法3（推荐）

从“number of 1 bits”中我们知道i&(i-1) 将最低位的1去掉了。如果ret[i]表示数i对应的位1的个数，则结果ret[i] = ret[i&(i-1)] + 1，因为i&(i-1)比i少了一个bit 1嘛，而且因为是去掉了一个1，所以一定有i&(i-1)<i，也就是说从0到num计算位1的个数时，当计算ret[i]时，ret[i&(i-1)]已经计算出来了。如计算i = 14的位1个数时，i&(i-1) = 12只比14少一个1，且12的个数一定已经计算出来了，这样就直接计算14了。

这应该就是动态规划算法。大问题最优解ret[i]包含子问题ret[i&(i-1)]+1的最优解，且这些子问题是重叠的（如110（6）和101（5）的最优解都包含子问题100（4）的最优解）。

时间复杂度 O(n)。

方法4

同方法2可知，去掉最后一个1对于奇数来说就是减1；而对于偶数来说，并不需要减1，直接右移一位，位1的个数不会变，但是数变小为一半，其最优解已经计算出来，这样只需要保存最大数一半大小的数组就可以了。但是算法时间比方法2变大了。

方法5

类似方法2，只是移走的是最后一位，不管是不是1。

f[i] = f[i/2] + i%2

不看最低位，直接右移1位，这个数在数组中肯定已经存在了，然后加上移走那位是0还是1（i%2 或者 i & 1）。

代码 Code

方法2

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ones(num+1,0);
        int base = 1;
        for(int i = 1; i <= num; i++)
        {
            if(i < base * 2)
                ones[i] = ones[i%base]+1;
            else{
                base *= 2;
                ones[i] = ones[i%base]+1;
            }
        }
        return ones;
    }
};

方法3

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ret(num+1, 0);
        for (int i = 1; i <= num; ++i)
            ret[i] = ret[i&(i-1)] + 1;
        return ret;
    }
};

方法5

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