A table lookup approach


  • 0
    H

    I like the solution "x & (x-1)" described in the classic "K&R". However, it's not so straightforward.
    Table lookup can always offer constant time cost. I use a small table to look up the 4-bit mapping,
    of course , 32 bit number need to be split into 8 slices, each 4-bit.
    Well, 8-bit lookup may be get better performance but the 256 elements array looks ugly.

    Here is the code:

    int hammingWeight(uint32_t n) {
        	uint32_t maps[16] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
    
        	return maps[n >> 28] +
        		maps[(n & 0x0F000000) >> 24] +
        		maps[(n & 0x00F00000) >> 20] +
        		maps[(n & 0x000F0000) >> 16] +
        		maps[(n & 0x0000F000) >> 12] +
        		maps[(n & 0x00000F00) >> 8] +
        		maps[(n & 0x000000F0) >> 4] +
        		maps[n & 0x0000000F];
        }

  • 1
    W

    Well, the idea of bitwise operation is cool.
    But the array is ugly.

    I'd like to share my code with you. Your inspire me a lot.

    int hammingWeight(uint32_t n)
    {
        n=((n&0xAAAAAAAA)>>1)+(n&0x55555555);
        n=((n&0xCCCCCCCC)>>2)+(n&0x33333333);
        n=((n&0xF0F0F0F0)>>4)+(n&0x0F0F0F0F);
        n=((n&0xFF00FF00)>>8)+(n&0x00FF00FF);
        n=((n&0xFFFF0000)>>16)+(n&0x0000ffff);
        return n;
    }

Log in to reply
 

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