Number of 1 Bits — The Brian Kernighan Popcount Trick

Problem Statement#

Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight). Return the popcount of the input integer.

Constraints:

• 1 <= n <= 2^31 - 1
• The input is a 32-bit unsigned integer in some languages.

Example 1:

Input:  n = 11 (binary: 1011)
Output: 3
Explanation: Bits set at positions 0, 1, 3.

Example 2:

Input:  n = 128 (binary: 10000000)
Output: 1

Example 3:

Input:  n = 2147483645 (binary: 1111111111111111111111111111101)
Output: 30

Why This Problem Matters#

Popcount — counting the number of set bits — is one of the most fundamental primitives in low-level programming. It appears in compression algorithms, cryptographic hash distance, error-correcting codes, chess engines (counting attacked squares), database bitmap indexes, and every modern CPU has a dedicated POPCNT instruction because the operation is so common.

In interviews, this problem is a litmus test. A candidate who only knows the naive shift-and-test loop reveals they have not studied bit manipulation in depth. A candidate who reaches for Brian Kernighan's trick immediately demonstrates fluency with the algebraic identities of two's complement arithmetic. FAANG companies (Apple, Amazon, Microsoft, Bloomberg) use this question as a warm-up specifically to gauge bitwise comfort before harder follow-ups like Counting Bits (LC 338) or Hamming Distance (LC 461).

The Core Insight#

Brian Kernighan's observation: n & (n - 1) clears the lowest set bit of n.

Why? Subtracting 1 from n flips all trailing zeros up to and including the lowest set bit. AND-ing with the original n keeps every bit higher than that lowest set bit unchanged and zeros out everything from the lowest set bit downward.

Example with n = 0b11010100:

n        = 1101 0100
n - 1    = 1101 0011
n & n-1  = 1101 0000   <- lowest set bit (position 2) cleared

This means we can count set bits by repeatedly applying n &= n - 1 until n == 0. The loop runs exactly popcount(n) times, which is at most 32 for 32-bit integers — but typically far fewer for sparse numbers.

The naive approach checks all 32 bits regardless of how many are set. Kernighan's trick scales with the number of set bits, making it asymptotically optimal for sparse inputs.

Visual Dry Run#

Input: n = 11 (binary 1011)

Loop ends when n = 0. Total set bits: 3.

Notice how each iteration peels off exactly one set bit. The loop body is two operations and runs popcount(n) times — for n = 128 (one bit set) it runs once, while a naive 32-bit shift loop would run 32 times.

Solution (Optimal)#

Python#

class Solution:
    def hammingWeight(self, n: int) -> int:
        # Brian Kernighan: clear the lowest set bit each iteration
        count = 0
        while n:
            n &= n - 1   # erase the lowest set bit
            count += 1   # count one bit cleared
        return count

For production code, Python provides bin(n).count('1') and n.bit_count() (Python 3.10+) which compile to native popcount instructions.

JavaScript#

var hammingWeight = function(n) {
    // JS bitwise ops are 32-bit; the n-1 trick still applies
    let count = 0;
    while (n !== 0) {
        n &= n - 1;   // remove the lowest set bit
        count++;
    }
    return count;
};

Complexity: Time O(k) where k is the popcount (at most 32 for 32-bit ints), Space O(1).

Common Mistakes#

1. Looping 32 times unconditionally. The naive approach for i in range(32): count += (n >> i) & 1 always does 32 iterations. Kernighan's trick stops as soon as no bits remain.

2. Forgetting unsigned semantics in fixed-width languages. In Java, int n is signed; right-shifting a negative number with >> performs arithmetic shift (sign extension), causing infinite loops. Use >>> (logical shift) or treat n as unsigned.

3. Confusing n & (n - 1) with n & -n. The first clears the lowest set bit; the second isolates the lowest set bit. Both are essential popcount-related identities — interviewers may probe whether you mix them up.

4. Using string conversion in tight loops. bin(n).count('1') is concise but allocates a string. For hot paths, the bit-arithmetic loop is faster.

5. Off-by-one when n == 0. The loop correctly returns 0 because the body never executes — but candidates sometimes write do { ... } while (n) which counts a phantom bit on zero input.

Interview Tips#

• State the core identity in one sentence: "n & (n - 1) clears the lowest set bit." That alone signals seniority.
• Walk through the dry run on a small example before coding. Interviewers value the explanation more than the code.
• Mention hardware popcount as the production answer (__builtin_popcount in GCC, Integer.bitCount in Java, POPCNT SSE4.2 instruction). This shows real-world awareness.
• If asked for an alternative without conditionals, mention the SWAR (SIMD-within-a-register) parallel popcount that uses masked additions to count bits in parallel.

Follow-up Questions#

Q: What if the input could be a 64-bit integer? The same algorithm works with no changes; the loop still runs at most 64 iterations.

Q: Can you compute popcount without any branches? Yes. The SWAR approach uses constant-width masks like 0x55555555, 0x33333333 and does a hierarchical sum-of-bits in O(log word_size) operations with no branches.

Q: How would you compute popcount for a long stream of integers? Use vectorized SIMD popcount or a precomputed 8-bit / 16-bit lookup table that maps a byte to its bit count, then sum the per-byte counts.

Q: How does this relate to LeetCode 338 Counting Bits? Counting Bits asks for popcount of every integer in [0, n]. There you can use the recurrence bits[i] = bits[i >> 1] + (i & 1) or bits[i] = bits[i & (i-1)] + 1 — the latter directly leverages Kernighan's trick.

Key Takeaways#

• Brian Kernighan's identity n & (n - 1) clears the lowest set bit; iterate until n == 0.
• Time complexity is O(popcount(n)), strictly better than the naive O(word_size) shift loop for sparse inputs.
• Popcount is a hardware primitive on every modern CPU — production code should use built-ins like __builtin_popcount, Integer.bitCount, or n.bit_count().
• Distinguish n & (n-1) (clears lowest bit) from n & -n (isolates lowest bit). Both are essential bit-manipulation idioms.
• Watch out for arithmetic vs logical right shift in signed-integer languages.
• This problem unlocks downstream patterns: Counting Bits, Hamming Distance, and bitset-based set operations.