338. Counting Bits

基础解法：
时间复杂度O(n*sizeof(int))

class Solution {
public:
    int calOne(unsigned n)
    {
        int result = 0;
        while(n)
        {
            if(n&1)
                result++;
            n = n >> 1;
        }
        return result;
    }
    vector<int> countBits(int num) {
        vector<int> result;
        if(num < 0) return result;
        for(int i = 0; i <= num; i++)
            result.push_back(calOne(i));
        return result;
        
        
    }
};

使用内置函数_builtin_popcount()

class Solution {
public:  
    vector<int> countBits(int num) {
        vector<int> result;
        if(num < 0) return result;
        for(int i = 0; i <= num; i++)
            result.push_back(__builtin_popcount(i));
        return result; 
    }
};

考虑二进制加法运算过程可以得到，只有当末位为0时 加1时才会导致1的个数增加。
时间复杂度O(n)

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