如果一个数i%2=1，即为奇数，即二进制中的最低位为1。我们将这个过程循环直至i为0，每一次i%2=1我们将该数的‘1’数加一。
上面的方法不能做到复杂度O(n)完成所有数的的遍历。我们换成动态规划。i%2=1,则有 dp[i]=dp[i/2]+1;每次将一个数向右移一位，看被移动的数的一的数目再加上当前一个1。如果i%2!=1则说明该数最后一位不为1，所以我们将该数直接移位 即 dp[i]=dp[i/2];
以上就是递推思路，开始着手代码
class Solution { public: vector<int> countBits(int num) { vector<int> res(num+1,0); for(int i=1;i<=num;i++) { if(i%2==1) { res[i]=res[i/2]+1; } else res[i]=res[i/2]; } return res; } };
还是菜啊，水货一只。
原文：https://www.cnblogs.com/biubiuWham/p/10449389.html