C++ solution using bitwise operators


  • 0
    Z
    class Solution 
    {
    public:
        int hammingWeight(uint32_t n) 
        {
            // Assume that bit index starts from 0.
            // Add odd bits to even bits.
            n = ((n & 0xaaaaaaaa) >> 1) + (n & 0x55555555);    
            // Add 2*odd bits to 2*even bits.
            n = ((n & 0xcccccccc) >> 2) + (n & 0x33333333);
            // Add 4*odd bits to 4*even bits.
            n = ((n & 0xf0f0f0f0) >> 4) + (n & 0x0f0f0f0f);
            // Add 8*odd bits to 8*even bits.
            n = ((n & 0xff00ff00) >> 8) + (n & 0x00ff00ff);
            // Add 16*odd bits to 16*even bits, i.e., add 
            // the left half of bits to the right half.
            n = ((n & 0xffff0000) >> 16) + (n & 0x0000ffff);
            
            return n;
        }
    };
    

    Take the number "01100100001000100100100010001011" as an example.

    1. After "n = ((n & 0xaaaaaaaa) >> 1) + (n & 0x55555555);"

    01 01 01 00 00 01 00 01 01 00 01 00 01 00 01 10

    1. After "n = ((n & 0xcccccccc) >> 2) + (n & 0x33333333);"

    0010 0001 0001 0001 0001 0001 0001 0011

    1. After "n = ((n & 0xf0f0f0f0) >> 4) + (n & 0x0f0f0f0f);"

    00000011 00000010 00000010 00000100

    1. After "n = ((n & 0xff00ff00) >> 8) + (n & 0x00ff00ff);"

    0000000000000101 0000000000000110

    1. After "n = ((n & 0xffff0000) >> 16) + (n & 0x0000ffff);"

    00000000000000000000000000001011


Log in to reply
 

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