## 191. Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation `00000000000000000000000000001011`, so the function should return 3.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

b'
\n

## Solution

\n
\n

#### Approach #1 (Loop and Flip) [Accepted]

\n

Algorithm

\n

The solution is straight-forward. We check each of the bits of the number. If the bit is , we add one to the number of -bits.

\n

We can check the bit of a number using a bit mask. We start with a mask , because the binary representation of is,

\n

\n\nClearly, a logical AND between any number and the mask gives us the least significant bit of this number. To check the next bit, we shift the mask to the left by one.

\n

\n\n

\n

And so on.

\n

Java

\n
`public int hammingWeight(int n) {\n    int bits = 0;\n    int mask = 1;\n    for (int i = 0; i < 32; i++) {\n        if ((n & mask) != 0) {\n            bits++;\n        }\n        mask <<= 1;\n    }\n    return bits;\n}\n`
\n

Complexity Analysis

\n

The run time depends on the number of bits in . Because in this piece of code is a 32-bit integer, the time complexity is .

\n

The space complexity is , since no additional space is allocated.

\n
\n

#### Approach #2 (Bit Manipulation Trick) [Accepted]

\n

Algorithm

\n

We can make the previous algorithm simpler and a little faster. Instead of checking every bit of the number, we repeatedly flip the least-significant -bit of the number to , and add to the sum. As soon as the number becomes , we know that it does not have any more -bits, and we return the sum.

\n

The key idea here is to realize that for any number , doing a bit-wise AND of and flips the least-significant -bit in to . Why? Consider the binary representations of and .

\n \n

Figure 1. AND-ing and flips the least-significant -bit to 0.

\n

In the binary representation, the least significant -bit in always corresponds to a -bit in . Therefore, anding the two numbers and always flips the least significant -bit in to , and keeps all other bits the same.

\n

Using this trick, the code becomes very simple.

\n

Java

\n
`public int hammingWeight(int n) {\n    int sum = 0;\n    while (n != 0) {\n        sum++;\n        n &= (n - 1);\n    }\n    return sum;\n}\n`
\n

Complexity Analysis

\n

The run time depends on the number of -bits in . In the worst case, all bits in are -bits. In case of a 32-bit integer, the run time is .

\n

The space complexity is , since no additional space is allocated.

\n

Analysis written by: @noran.

\n
'