leetcode338

对于0-7

000-----ve[0]=0

001 ----1的个数取决于1%2+ve[0]

010-----1的个数取决于2%2+ve[1]

011-----1的个数取决于3%2+ve[1]

100-----1的个数取决于4%2+ve[2]

101-----1的个数取决于5%2+ve[2]

110-----1的个数取决于6%2+ve[3]

111-----1的个数取决于7%2+ve[3]

从低位考虑的话，除了最低位外的1的个数位ve[i>>1],其中i>>1可以提前算出来，再加上最低位的1的个数就可以得出i的二进制1的个数了

代码如下:

 1 class Solution {
 2 public:
 3     vector<int> countBits(int num) {
 4         int i;
 5         vector<int>ve(num+1,0);
 6       for(i=0;i<=num;i++)
 7       ve[i]=ve[i>>1]+i%2;
 8       return ve;
 9     }
10 };

leetcode338

原文：http://www.cnblogs.com/thefirstfeeling/p/5688287.html