This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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\n

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

\n\n

'
\n

** Algorithm**

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.

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

\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

\nAnd so on.

\n**Java**

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

**Complexity Analysis**

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 .

\nThe space complexity is , since no additional space is allocated.

\n\n

**Algorithm**

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.

\nThe 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.*

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.

\nUsing this trick, the code becomes very simple.

\n**Java**

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

**Complexity Analysis**

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 .

\nThe space complexity is , since no additional space is allocated.

\nAnalysis written by: @noran.

\n