//worst time O(log(32)), space O(1)
class Solution {
public:
int hammingWeight(uint32_t n) {
n = ((n>>(1<<0)) & 0x55555555) + (n & 0x55555555); //count 1bit of adjacent 2 bits
n = ((n>>(1<<1)) & 0x33333333) + (n & 0x33333333); //count 1bit of adjacent 4 bits
n = ((n>>(1<<2)) & 0x0F0F0F0F) + (n & 0x0F0F0F0F); //count 1bit of adjacent 8 bits
n = ((n>>(1<<3)) & 0x00FF00FF) + (n & 0x00FF00FF); //count 1bit of adjacent 16 bits
return ((n>>(1<<4)) & 0x0000FFFF) + (n & 0x0000FFFF); //count 1bit of adjacent 32 bits
}
};
//worst time O(32), space O(1)
class Solution {
public:
int hammingWeight(uint32_t n) {
int ret=0;
while(n)
{
++ret;
n&=(n1);
}
return ret;
}
};
Solutions for both O(log(32)) and O(32), your choice


It's a divide and conquer method.
First we compute “number of 1bits” in adjacent 2 bits, then 4bits, 8bits, 16bits, finally 32 bits.Let's take an 8 bit unsigned number as example:
The original 8 bit number n is 90, which is '01011010' in binary format. There are 3 steps:0  0  1  0  1  1  0  1  0  1  01 01 01 01 2  0010 0010 3  00000100
Line 0 is the original number.
Line 1: we add up every two adjacent bits, so the result is "number of 1s in every 2 bits".
Line 2: Every four adjacent bits, 01 + 01 = 10, 01 + 01 = 10.
Line 3: 8bits, 0010 + 0010 = 0100, so the final answer is 4.The computation of Line 1:
Compute adjacent 2 bits, we use a mask number '01010101' (0x55)01 01 10 10 & 01 01 01 01 = 01 01 00 00  (1)
right shift n by 1 bit, so we can deal with the adjacent bit
00 10 11 01 & 01 01 01 01 = 00 00 01 01  (2)
then we add up (1) and (2):
n = 01 01 01 01
Line 2 and 3 are similar, but they have different mask numbers and shift values.
for 8 bit number, the mask numbers are:01010101 (0x55) 00110011 (0x33) 00001111 (0x0f)