Very simple c++ dp solution count[i] = count[i & (i-1)]


  • 3
    D

    First of all we should know what higher bits is.
    The higher bit is the bit without being carried, and i & (i - 1) is the higher bit of (i -1), such as:
    0x10011 & 0x10100 = 0x10000, the higher bit is 0x10000
    0x10011 & 0x10010 = 0x10010, the higher bit is 0x10010
    the bits count of i is the bit count of higher bit of (i - 1) plus one bit carry, so
    count[i] = count[i - 1] + 1

    vector<int> countBits(int num) {
        vector<int> count(num + 1, 0);
        for (int i = 1; i <= num; ++i) {
            count[i] = count[i & (i - 1)] + 1;
        }
        return count;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.