# A table lookup approach

• 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];
}``````

• 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;
}``````

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