Number of 1 Bits

PracticeNeetCode ↗LeetCode ↗

Given a positive integer n, return the number of set bits (1s) in its binary representation — the Hamming weight.

Example

Key Pointers

• n & (n - 1) clears exactly the lowest set bit of n — a trick worth memorizing on its own.
• Each application of that trick removes one 1-bit, so the number of times you can apply it before hitting zero is the answer.
• This runs proportional to the number of set bits, not the bit width, which is faster than checking all 32 positions when few bits are set.

Step-by-Step Analysis

1. Initialize count = 0.
2. While n is nonzero: set n = n & (n - 1), clearing its lowest 1-bit, and increment count.
3. Once n reaches 0, every set bit has been cleared and counted.
4. Return count.

Complexity

Time: O(k) where k is the number of set bits — Space: O(1)

Code

def hammingWeight(n: int) -> int:
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

Code Explanation

How the solution above works, piece by piece.

1. n - 1 flips the lowest set bit to 0 and every bit below it to 1.
2. So n &= n - 1 clears exactly the lowest set bit.
3. Count how many times that can happen before n becomes 0: that's the number of 1 bits.
4. The loop runs once per set bit, not once per bit position.

Visual Walkthrough

Running it on n = 11 (binary 1011):

Video Explanation

NeetCode — LeetCode 191