LeetCode 191: Number of 1 Bits

Problem Restatement

We are given a positive integer n.

We need to return the number of 1 bits in its binary representation. This count is also called the Hamming weight. The official problem asks for the number of set bits in the binary representation of n.

A set bit means a bit whose value is 1.

For example:

n = 11
binary = 1011

There are three 1 bits, so the answer is:

3

Input and Output

Example function shape:

def hammingWeight(n: int) -> int:
    ...

Examples

Example 1:

n = 11

Binary:

1011

The 1 bits are:

1 0 1 1
^   ^ ^

There are 3 set bits.

Output:

3

Example 2:

n = 128

Binary:

10000000

There is only one 1 bit.

Output:

1

Example 3:

n = 2147483645

This number has 30 set bits.

Output:

30

First Thought: Check Every Bit

A simple way is to repeatedly check the last bit.

The expression:

n & 1

returns 1 if the last bit is 1, otherwise it returns 0.

Then we shift n right by one bit:

n >>= 1

This removes the last bit and moves the next bit into place.

That approach works.

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0

        while n:
            count += n & 1
            n >>= 1

        return count

This checks every bit position until n becomes zero.

Key Insight

There is a faster bit trick.

The expression:

n & (n - 1)

removes the rightmost 1 bit from n.

Example:

n       = 1100
n - 1   = 1011
n&(n-1) = 1000

The rightmost 1 in 1100 was removed.

So instead of checking every bit, we can remove one set bit at a time and count how many removals happen.

For example:

n = 1011

First removal:

1011 & 1010 = 1010

Second removal:

1010 & 1001 = 1000

Third removal:

1000 & 0111 = 0000

We removed three 1 bits, so the answer is 3.

Algorithm

1. Set count = 0.
2. While n is not zero:
   • Replace n with n & (n - 1).
   • Increase count by 1.
3. Return count.

Each loop removes exactly one set bit.

Correctness

At every iteration, n & (n - 1) removes the lowest set bit of n.

So each iteration reduces the number of 1 bits by exactly one.

The loop stops when n becomes zero.

A number is zero exactly when it has no 1 bits left.

Therefore, the number of iterations is exactly the number of original set bits in n.

Since count increases once per removed set bit, the final count equals the Hamming weight of the original number.

Complexity

Here, b is the number of 1 bits in n.

For a 32-bit integer, this is also O(1) because there are at most 32 bits.

Implementation

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0

        while n:
            n &= n - 1
            count += 1

        return count

Code Explanation

We start with zero counted bits:

count = 0

The loop continues while some set bit still exists:

while n:

This line removes the rightmost set bit:

n &= n - 1

After removing one set bit, we count it:

count += 1

When n becomes zero, all set bits have been removed, so we return:

return count

Alternative Implementation: Fixed 32-Bit Scan

This version checks all 32 bit positions.

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0

        for _ in range(32):
            count += n & 1
            n >>= 1

        return count

This is also valid for a 32-bit input. It always performs exactly 32 iterations.

The n & (n - 1) version can use fewer iterations when the number has only a few set bits.

Testing

def run_tests():
    s = Solution()

    assert s.hammingWeight(11) == 3
    assert s.hammingWeight(128) == 1
    assert s.hammingWeight(2147483645) == 30
    assert s.hammingWeight(1) == 1
    assert s.hammingWeight(0) == 0
    assert s.hammingWeight(15) == 4

    print("all tests passed")

run_tests()

Test meaning: