338.md

记下来两个解答 ret[i] = ret[i&(i-1)] + 1; f[i] = f[i >> 1] + (i & 1);

只想到与上一个数比，我还是有点zz啊

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ans(1,0);
        map<int, int> help;
        int tmp = 0x7fffffff, tmp1 = 29;
        while(tmp){
            help[tmp] = tmp1;
            tmp = tmp >> 1;
            tmp1--;
        }
        for(int i = 1; i <= num; ++i){
            if(i%2)
                ans.push_back(ans.back()+1);
            else
                ans.push_back(ans.back()-help[(i-1)^i]);
        }
        return ans;
    }
};