Blind 75Easy

Number of 1 Bits — Brian Kernighan’s Trick

Clear the lowest set bit repeatedly by applying n & (n - 1) until the number becomes zero.

Bit Manipulation

View problem on LeetCode

Problem Statement

Count the number of set bits (Hamming weight) in a 32-bit unsigned integer.

Why This Problem Matters

Showcases a canonical bit trick that appears in many problems.
Encourages reasoning about while loops and bit patterns.
Serves as a building block for popcount operations and integer bitset tasks.

Thought Process

Use n & (n - 1)

Each application removes the lowest set bit, making the loop run exactly number-of-1s times.

Increment count per removal

Keep a counter that increments whenever a bit is cleared.

Handle unsigned shift alternative

If not using Kernighan’s trick, emphasise using >>> to avoid sign extension.

Step-by-Step Reasoning

Initialise count = 0.
While n != 0, set n = n & (n - 1) and increment count.
Return count.

Dry Run

n = 11 (1011₂)

Loop runs three times, clearing bits 0, 1, and 3.

n = 0

Loop does not execute; count remains 0.

Complexity Analysis

Time

O(k)

Space

O(1)

Why

Loop runs once per set bit (k), not per bit position.

Annotated Solution

JAVA

public class NumberOf1Bits {
  public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
      n &= (n - 1);
      count += 1;
    }
    return count;
  }
}

Each iteration drops the lowest set bit, so the loop executes exactly as many times as there are ones.

Common Pitfalls

Using arithmetic shift >> with negative numbers retains leading ones, causing infinite loops.
Incrementing count before updating n counts an extra bit.
Forgetting to handle the zero case explicitly is fine but worth calling out in interviews.

Follow-Up Questions

How would you compute popcount for all numbers 0..n efficiently?
Can you vectorise this operation using bitset libraries?

Key Takeaways

Brian Kernighan’s trick is indispensable; memorise it.

Focus on describing why the loop terminates quickly.

Bit manipulation answers sound stronger when you mention follow-up optimisations.