Core Bit Tricks

Count Set Bits (Hamming Weight)

Repeatedly apply n = n & (n−1) — each application clears one set bit. Count how many times until n becomes 0. This runs in O(number of set bits), not O(32). Known as Kernighan's trick.

O(log n)

O(1)

How It Works

Kernighan's trick counts set bits by repeatedly executing n = n & (n-1), which removes exactly one set bit per iteration, and counting iterations until n reaches zero. A number with k set bits finishes in k steps, so the loop runs in O(k) rather than O(32) — a sparse value like 0x80000000 needs a single iteration instead of thirty-two shift-and-test rounds.

A naive loop inspects every bit position regardless of how many are set; Kernighan's version does work proportional only to the answer. For bulk counting, the DP used by Counting Bits goes further: bits[i] = bits[i & (i-1)] + 1 (or bits[i >> 1] + (i & 1)) computes popcounts for all numbers 0..n in O(n) total by reusing previously computed answers. Real hardware also exposes a popcount instruction, but interviews expect the bit-clearing derivation.

Step-by-Step Visualization

Count set bits in 1011 (decimal 11)

Binary1011

1/3

Code

Java

static int hammingWeight(int n) {
  int count = 0;
  while (n != 0) {
    n &= n - 1; // Clear lowest set bit
    count++;
  }
  return count;
}
// hammingWeight(11) → 3 (1011 has three 1-bits)

Tips & Gotchas

1Use n & (n-1) to clear the lowest set bit

2Count how many times you can do this before n becomes 0

3Also called Hamming Weight or popcount

Practice Problems

1Number of 1 Bits
2Counting Bits
3Hamming Distance
4Binary Watch

About the Core Bit Tricks Pattern

Fundamental bit operations that appear in many problems. These are building blocks — memorize them.

Key insight

Key tricks: n & (n−1) clears lowest set bit (power-of-2 check). XOR of all elements cancels pairs. Bit masks can represent subsets for DP. These are often O(1) space solutions.

Common Bit Manipulation Interview Problems

Single Number
Number of 1 Bits
Counting Bits
Missing Number
Reverse Bits
Power of Two

Frequently Asked Questions

When is Kernighan's method actually faster than checking all 32 bits?

Whenever the value is sparse — the loop runs once per set bit, so a number with three set bits finishes in three iterations versus thirty-two. In the worst case (all bits set) the two approaches tie, so Kernighan's trick is never slower asymptotically.

How does the Counting Bits DP relate to this trick?

It memoizes the same insight: since i & (i-1) removes one set bit, its popcount is exactly one less than i's, giving bits[i] = bits[i & (i-1)] + 1. Filling the table in increasing order guarantees the smaller index is already computed, yielding all answers in O(n).

How do I count set bits in a negative number safely?

Treat the value as its unsigned bit pattern. In Java, use the unsigned right shift (>>>) or rely on n & (n-1), which terminates correctly on two's-complement values; in Python, mask first with n & 0xFFFFFFFF because Python integers are unbounded and negatives carry infinite sign bits.