动态规划
1.奇数中1的个数，是它上一个数1个个数+1，如2（10），3（11），4（100），5（101）
2.偶数中1的个数，是它除以2后的那个数的1的个数，如2（10），4（100），8（1000），6（110），12（1100）
3.因此，dp[i]=i&1?dp[i-1]+1:dp[i>>1]
class Solution {
public:
vector<int> countBits(int n) {
vector<int>dp(n+1,0);
for(int i=1;i<n+1;++i){
if(i&1) dp[i] = dp[i-1]+1;
else dp[i] = dp[i>>1];
}
return dp;
}
};