Number of 1 Bits: Counting Set Bits

You are given a positive integer. How many of its bits are 1? That is the entire problem. LeetCode 191, also known as the Hamming weight, asks you to count the number of 1 bits in the binary representation of a number.

For example, 11 in binary is 1011. Three of those bits are 1, so the answer is 3.

The problem is easy to state, but it introduces a fundamental bit manipulation technique that shows up in dozens of harder problems. Let's look at two approaches and understand why the second one is particularly elegant.

Approach 1: Check each bit with right shift

The most natural approach is to examine every bit one at a time. You can isolate the last bit of any integer by ANDing it with 1 (n & 1). If the result is 1, the last bit is set. Then right-shift n by one position to move the next bit into the last spot.

Repeat until n becomes 0.

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

This checks every bit from right to left. For a 32-bit integer, it runs at most 32 iterations. Simple, correct, and predictable.

Why it works

n & 1 extracts the least significant bit. If that bit is 1, you add it to the count. n >>= 1 shifts all bits one position to the right, dropping the bit you just checked and bringing the next bit into position. When n reaches 0, there are no more bits to check.

Approach 2: The n & (n-1) trick (Brian Kernighan's algorithm)

There is a faster approach when the number of set bits is small. Instead of checking every bit position, you can clear one set bit per iteration and count how many times you do it.

The key insight: n & (n - 1) clears the lowest set bit of n.

Why does this work? When you subtract 1 from a number, all the bits below the lowest set bit flip (the lowest set bit becomes 0, and all the 0s below it become 1s). When you AND n with n - 1, the lowest set bit and everything below it gets zeroed out. Everything above it stays the same.

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

This loop runs exactly k times, where k is the number of set bits. If only 2 out of 32 bits are set, you do 2 iterations instead of 32.

Step-by-step walkthrough

Let's trace through n = 11 (binary 1011) using the n & (n-1) approach. Watch how one bit disappears each step.

Each iteration clears exactly one set bit. After three iterations, all bits are gone and the count is 3. The loop never touches the zero bits at all.

Complexity analysis

Both approaches are technically O(1) for fixed-width integers (32 bits). The practical difference is that Brian Kernighan's algorithm skips zero bits entirely, making it faster when the number has few set bits.

Building blocks

This problem decomposes into one core reusable piece that CodeBricks drills independently:

Bit manipulation fundamentals

The ability to isolate, check, and clear individual bits using AND, OR, XOR, and shift operators. These operations are the foundation of every bit manipulation problem.

The patterns you need:

• Isolate the last bit: n & 1 gives you the least significant bit.
• Right shift: n >>= 1 moves all bits one position right, dropping the last bit.
• Clear the lowest set bit: n & (n - 1) removes exactly one 1-bit.
• Check if power of two: n & (n - 1) == 0 (only one bit is set).

# Core pattern: clear lowest set bit
n &= n - 1

Once you can fluently apply these bit primitives, problems like Number of 1 Bits, Power of Two, and Reverse Bits become variations on the same theme. You stop thinking about the mechanics of bit manipulation and start recognizing which primitive fits the problem.

Edge cases

n = 0: Zero has no set bits. Both approaches return 0 immediately since the while loop condition fails on the first check.

n = 1: Binary 1. One set bit. The loop runs once and returns 1.

All bits set (n = 2^31 - 1 for 32-bit): Every bit is 1. The right-shift approach runs 31 times. Brian Kernighan's runs 31 times too, since every bit needs clearing. This is the worst case where both approaches perform identically.

Powers of two: Only one bit is set. Brian Kernighan's algorithm finishes in a single iteration. This is its best case.

From understanding to recall

Counting set bits is simple enough to understand in one reading. But understanding and recalling under pressure are different skills. In an interview, you do not want to re-derive the n & (n-1) trick from scratch. You want it in muscle memory.

That is what spaced repetition does. You type n &= n - 1 from scratch today, then again in two days, then four, then a week. Each time you practice, the retrieval gets faster and the pattern locks deeper into long-term memory. By the time you see this technique in a harder problem (like counting the total number of set bits across a range), the building block is already automatic.

Related posts

• XOR Cancellation Pattern - Another fundamental bit manipulation technique. XOR uses the "same bits cancel" property, while n & (n-1) uses the "subtract flips trailing bits" property. Learning both gives you a solid foundation for all bit manipulation problems.