easy Number of 1 Bits

Number of 1 Bits (Hamming Weight)

Given a 32-bit integer n, return how many of its bits are set to 1. This count is the Hamming weight, or the population count (“popcount”). For n = 11, whose binary is 1011, the answer is 3.

It looks trivial — and it is, until the interviewer asks “can you do better than looking at all 32 bits?” The interesting content here is not the loop; it is why the clever loop is allowed to skip the zero bits, and whether “clever” is even the right call.

The naive baseline — inspect all 32 positions

The mechanical solution walks every bit position i from 0 to 31, shifts bit i down to position 0, and masks it: (n >> i) & 1. Sum those and you have the count.

int count = 0;
for (int i = 0; i < 32; i++) {
    count += (n >> i) & 1;   // isolate bit i, add 0 or 1
}

This always performs exactly 32 iterations, regardless of the input. For a fixed 32-bit word that is O(1) — but it is a constant 32, and it does the same work on n = 0 (no bits set) as on n = -1 (all 32 set). Note that (n >> i) & 1 is safe even when n is negative: an arithmetic right shift copies the sign bit into the top, but we only ever read the bottom bit after masking, so the sign fill never reaches us.

The bit insight — Kernighan skips the zeros

The key identity is n & (n - 1) clears the lowest set bit of n, and nothing else. Prove it by looking at what borrow does. Say the lowest set bit of n sits at position k, so n ends in 1 followed by k zeros: ...1​000. Subtracting 1 must borrow through those k trailing zeros, turning them into 1s, and it flips the bit at position k from 1 to 0: n - 1 = ...0​111. Now AND them, column by column:

• Above position k: both numbers are identical (subtraction never touched them) → those bits survive unchanged.
• At position k: n has 1, n-1 has 0 → result 0. The lowest set bit is gone.
• Below position k: n has 0, n-1 has 1 → result 0.

So one n &= n - 1 removes exactly one set bit. Repeat until n becomes 0, and the number of iterations is the number of set bits. Brian Kernighan popularized this; it never visits a zero bit at all.

Traced example — n = 11 (binary 1011)

Three iterations for three set bits — the naive loop would have taken 32. Each step visibly erases one 1: bit 0, then bit 1, then bit 3.

Java: Kernighan popcount

public class Solution {
    // Loops once per set bit, not once per bit position.
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);   // erase the lowest set bit
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().hammingWeight(11));  // 3
        System.out.println(new Solution().hammingWeight(0));   // 0
        System.out.println(new Solution().hammingWeight(-1));  // 32  (0xFFFFFFFF)
        System.out.println(Integer.bitCount(11));              // 3  (the JDK builtin)
    }
}

Go: Kernighan popcount

package main

import (
	"fmt"
	"math/bits"
)

// n is unsigned: shifts are logical and there is no sign bit to worry about.
func hammingWeight(n uint32) int {
	count := 0
	for n != 0 {
		n &= n - 1 // erase the lowest set bit
		count++
	}
	return count
}

func main() {
	fmt.Println(hammingWeight(11))              // 3
	fmt.Println(hammingWeight(0))               // 0
	fmt.Println(hammingWeight(0xFFFFFFFF))      // 32
	fmt.Println(bits.OnesCount32(11))           // 3  (the stdlib builtin)
}

Why the Java version needs no >>>

Signed right shift is the classic trap in this problem — but the Kernighan loop sidesteps it. A naive while (n != 0) n >>= 1; in Java would never terminate on a negative n, because arithmetic >> keeps shifting in copies of the sign bit, so -1 stays -1 forever. You would have to write n >>>= 1 (the unsigned/logical shift) to feed zeros in from the top. Kernighan avoids the issue entirely: n &= n - 1 strictly removes set bits, so even -1 (all 32 bits set) reaches 0 in exactly 32 steps. Go has no >>> operator at all; it encodes signedness in the type, so we take a uint32 and its >> is already logical.

Complexity

• Naive: always 32 iterations → Θ(32) = O(1) for a fixed word, but the constant is fixed at the word width.
• Kernighan: iterations = number of set bits = popcount(n), between 0 and 32 → O(popcount), still O(1) for a 32-bit word but data-dependent and never worse than the naive loop.
• Space: a single counter → O(1) for both.

Judgment layer — which one, and when

• Reach for the builtin first, honestly. Integer.bitCount(n) / bits.OnesCount32(n) compile to a single hardware POPCNT instruction on modern CPUs — nothing you hand-write beats it. In real code, use it. In an interview, name it, then implement one by hand because that is what is being tested.
• Kernighan vs. the naive 32-loop. Kernighan wins when inputs are sparse (few set bits) — it does popcount iterations instead of 32. It is the answer that shows you understand n & (n-1), so it is the stronger interview response.
• When the naive fixed loop is actually better. Its running time is independent of the data. Kernighan's iteration count leaks the popcount through timing — in constant-time cryptographic code (where a timing side-channel can expose secret bits) you deliberately avoid the data-dependent loop and either use the fixed 32-iteration form or a branch-free SWAR popcount. This is the staff-level nuance: the “clever” solution is the wrong one when timing must not depend on the value.
• vs. a lookup table. Precomputing popcounts for all 8-bit (or 16-bit) chunks and summing 4 (or 2) table hits is a classic constant-factor win when you call popcount in a hot loop and lack a hardware instruction — but it costs table memory and only pays off at high call volume.

Edge cases & traps

• Treat n as an unsigned 32-bit pattern. The problem is about the bits, not the signed value. In Java the input arrives as an int; do not sign-extend it when shifting (use >>>, or avoid shifting via Kernighan). In Go the signature is uint32, which makes this explicit and safe.
• n = 0 returns 0 — the loop body never runs.
• n = -1 (all bits set) returns 32, not −1; you are counting bits, not interpreting the two's-complement value.
• Don't confuse it with counting zeros or trailing zeros — those use ~n or n & -n respectively, not this loop.

Takeaways

• n & (n - 1) clears the lowest set bit; looping it counts set bits in popcount steps, not 32.
• The proof is a borrow argument: n-1 flips the lowest 1 to 0 and the trailing zeros to 1s, so the AND zeroes exactly that bit and below.
• Kernighan's data-dependent timing is a feature for sparse inputs but a liability for constant-time code — know when not to be clever.
• In production, the language builtin (single POPCNT instruction) beats every hand-rolled variant.