# Solutions for both O(log(32)) and O(32), your choice

• ``````//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&=(n-1);
}
return ret;
}
};``````

• could you please give a brief explain on how does the first solution work?

• 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:

``````   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)``````

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