方法一：pop count
利用 191. The number of 1 bits 中的方法，算是bit manipulation 中的巧妙操作，每次 n = n&(n-1) 把最低位的 1 置为 0 。
时间复杂度 O(nk)，k表示数字中1的位数。
class Solution { public: vector<int> countBits(int num) { vector<int> res; for (int i=0;i<=num;++i){ res.push_back(popcount(i)); } return res; } int popcount(int n){ int cnt=0; while (n!=0){ ++cnt; n = n&(n-1); } return cnt; } };
方法二：DP
DP方法有很多，如 dp[i] = dp[i/2] + i%2， dp[i] = dp[i & (i-1)] +1 ...
时间复杂度 O(n)
注意的是，所有位操作的优先级都比普通运算符低，因此别忘了加括号！
class Solution { public: vector<int> countBits(int num) { vector<int> dp(num+1); dp[0] = 0; for (int i=1;i<=num;++i){ dp[i] = dp[i>>1] + (i&1); } return dp; } };
class Solution { public: vector<int> countBits(int num) { vector<int> dp(num+1); dp[0] = 0; for (int i=1;i<=num;++i){ dp[i] = dp[i&(i-1)] + 1; } return dp; } };
原文：https://www.cnblogs.com/hankunyan/p/9532838.html