基础解法：
时间复杂度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;
}
};
