1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int countB(int i) {
        int cnt = 0;
        while (i) {
            cnt += i & 1;
            i  = i >> 1;
        }
        return cnt;
    }

    vector<int> countBits(int n) {
        vector<int> res;
        for (int i = 0; i <= n; i ++) {
            res.push_back(countB(i));
        }
        return res;
    }

};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res;
        res.push_back(0);
        for (int i = 1; i <= n; i ++) {
            res.push_back(res[i >> 1] + (i & 1));
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> bits(n + 1);
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    }
};