Counting Bits

leetcode

so the intuition here is, we use the DP array to store the number of 1s for each number from 0 to n.

for any value, x, in the [0,n] range, suppose its number of 1 bits is dp[x], then

1. if the x is even, then x + 1 is odd number, and the number of 1 bits for x + 1 is dp[x] + 1 (last bit change to 1)
2. if the x is odd, then x + 1 is even number, and the number of 1 bits for x + 1 is dp[x + 1 >> 1] (right shift by 1)
3. Note, x + 1 >> 1 is equivalent to (x + 1) / 2, which means we are removing the last bit (which is 0 for even number)

code C++

        vector<int> countBits(int n){
        vector<int> cnt(n+1);
        cnt[0] = 0;
        for (int i = 1 ; i  <= n ; i ++) {
            if ((i & 1) == 0) {
                cnt[i] = cnt[i >> 1] ;
            } else {
                cnt[i] = cnt[i - 1] + 1;
            }
        }
        return cnt;
    }

even more concise code C++

    vector<int> countBits(int n) {
        vector<int> dp(n+1,0);
        for(int i=0;i<dp.size();i++){
            dp[i]=dp[i/2]+i%2;
        }
        return dp;
    }