intermediate8 min read·Updated October 8, 2026

Counting Bits (n & (n-1)) Explained: Popcount of 0..5 & Kernighan

Master bit manipulation with a full walkthrough of popcount for 0..5 and Brian Kernighan's algorithm on 7 and 8. Build a mental model and trace edge cases.

By Learnisim AI·Published October 8, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Basic bitwise operations (AND, shift)
  • Binary number representation
Counting Bits & Kernighan's Algorithm: n & (n - 1) Popcount table for 0..5, plus bit-destruction tracing on n = 7 (0b111) and n = 8 (0b1000) Phase 1: Popcount Array [0..5] Index to set-bit count mapping i: 0 0 i: 1 1 i: 2 1 i: 3 2 i: 4 1 i: 5 2 DP Formula: ans[i] = ans[i & (i - 1)] + 1 Phase 2: Anatomy of n & (n - 1) Clears the lowest set bit in one atomic operation n = 12 (0b1100) n - 1 = 11 (0b1011) n&(n-1)= 8 (0b1000) Trailing zeros flip Lowest set bit dies Skips empty slots! Phase 3: Kernighan Tracing (n = 7 vs n = 8) Loop drops exactly one set bit per iteration until 0 n = 7 (0b111) Iter 1: 7 & 6 = 0b110 (2) Iter 2: 6 & 5 = 0b100 (4) Iter 3: 4 & 3 = 0b000 (0) Drop Count = 3 Iterations n = 8 (0b1000) Iter 1: 8 & 7 = 0b000 (0) (Single set bit at MSB) (Zero intermediate checks) Drop Count = 1 Iteration Phase 4: Practice & Transfer Predicting drop counts & vectorization Predict for n = 15 & n = 16 n=15 (0b1111) → 4 | n=16 (0b10000) → 1 Range Popcount Vectorizer O(set_bits) per lookup vs O(bits) naive Scales efficiently in cryptography & sparse arrays
Popcount of 0..5, and Kernighan on n = 7 and n = 8 overview diagram
Why

Why Counting Bits the Naive Way Fails at Scale

Phase 1: The Cost of Counting 1-Bits

Imagine you need to compute the popcount (the number of set bits) for every integer from 0 to 5, and then efficiently find how many bits are active in and . This task—known as population counting—appears everywhere from sparse matrix compression to cryptography and low-level system profiling.
The most intuitive way to count set bits in a number is to inspect every single bit position one by one. You shift the number right or check a bitmask across all 32 or 64 bits of the register:
python
def naive_popcount(n):
    count = 0
    while n > 0:
        count += (n & 1)
        n >>= 1
    return count
Consider what happens with our working example. For (0b1000), the loop checks the least significant bit, shifts right four times, and processes zeros even though there is only a single 1 bit in the entire number. As integers grow larger, or when you need to compute counts for a massive range like 0..5 and beyond, checking every bit position wastes precious CPU cycles on zero-bits that tell us nothing new.
We need an operation that ignores the trailing zeros and jumps straight from one set bit to the next without inspecting every empty slot in between.
Why Counting Bits the Naive Way Fails at Scale — Popcount & Kernighan's Trick Population Count (0 to 5) Int Binary (8-bit) Popcount (1-bits) 0 0000 0000 0 1 0000 0001 1 2 0000 0010 1 3 (0b11 : 2) | 4 (0b100 : 1) | 5 (0b101 : 2) Naive Way Fails: n = 8 (0b1000) Loop inspects ALL 8 or 32 bits one by one: 0 chk 1 0 chk 2 0 chk 3 1 chk 4 0000 (remaining) Wastes CPU cycles on zeros! Problem: Scales with data-type width (32/64 steps), not set bits. Brian Kernighan’s Algorithm: n & (n - 1) clears the lowest set bit instantly Step-by-Step on n = 7 (Binary: 0b111) Iter 1: n = 7 (111) n-1 = 6 (110) n&(n-1) = 6 (110) Iter 2: n = 6 (110) n-1 = 5 (101) n&(n-1) = 4 (100) Iter 3: n = 4 (100) n-1 = 3 (011) n&(n-1) = 0 (000) Total iterations = 3 (Exact number of set bits!) Step-by-Step on n = 8 (Binary: 0b1000) Iter 1: n = 8 (1000) n-1 = 7 (0111) n&(n-1) = 0 Total iterations = 1 (Skips 3 trailing zeros instantly!)
Why Counting Bits the Naive Way Fails at Scale diagram
Model

The Anatomy of $n \&(n-1)$

Phase 2: The Model of Bit Destruction

To understand why counting bits efficiently relies on , we have to examine what happens to the binary representation of a number when we subtract 1. When you subtract 1 from any integer, all the trailing zeros flip to ones, and the lowest set bit (the rightmost 1) flips to a zero. All bits to the left of that lowest set bit remain completely untouched.
When you perform a bitwise AND between and , that rightmost 1 and all the trailing flipped zeros collide with their inverted selves and vanish. This is not just a clever trick; it is a surgical tool that erases exactly one set bit per operation without disturbing any other bits higher up in the binary sequence.
Let us map this back to our locked example. For (binary 0b111), subtracting 1 gives 6 (binary 0b110). When we compute , the lowest set bit is cleared, leaving 0b110. For (binary 0b1000), subtracting 1 gives 7 (binary 0b0111). When we compute , the single set bit at position 3 is cleared entirely, instantly collapsing the value to 0.
Alternatively, when we build up the entire range from 0 to 5 using dynamic programming, our model shifts from destruction to inheritance. Any number shares its population count with plus whatever remainder it picked up at the lowest bit (). This means ans[i] = ans[i >> 1] + (i & 1) lets us compute the entire array in a single linear sweep without ever looping through individual bits.
The Anatomy of n & (n-1): Brian Kernighan's Bit Destruction Clears exactly one rightmost set bit per operation without disturbing higher bits Popcount Range (0 to 5) i Binary Bits 0 0000 0 1 0001 1 2 0010 1 3 0011 2 4 0100 1 5 0101 2 DP: ans[i] = ans[i & (i-1)] + 1 Kernighan on n = 7 (0b111) n = 7 0 1 1 1 n - 1 = 6 0 1 1 0 n & (n-1) 0 1 1 0 (6) Kernighan on n = 8 (0b1000) n = 8 1 0 0 0 n - 1 = 7 0 1 1 1 n & (n-1) 0 0 0 0 (0) The Model of Bit Destruction 1. Subtract 1 Trailing zeros flip to 1s, lowest set bit (rightmost 1) flips to 0. Left bits untouched. 2. Bitwise AND n & (n-1) forces the rightmost set bit and all flipped zeros to vanish entirely! 3. Surgical Erases exactly one bit per operation.
The Anatomy of $n \&(n-1)$ diagram
Worked example

Tracing Kernighan's Algorithm on $n = 7$ and $n = 8$

Phase 3:

Now that we understand how clearing the lowest set bit works, let us execute the procedure end-to-end on our working numbers: (0b0111) and (0b1000). Kernighan's algorithm counts the number of set bits by repeatedly applying the operation until reaches 0, incrementing a counter at each successful drop.

Given

- Input numbers: and
- State variables: count = 0

Steps for (0b0111):

1. count = 0, n = 7 (0b0111). Since , compute (0b0111 & 0b0110 = 0b0110, which is 6). Increment count to 1.
2. n = 6 (0b0110). Compute (0b0110 & 0b0101 = 0b0100, which is 4). Increment count to 2.
3. n = 4 (0b0100). Compute (0b0100 & 0b0011 = 0b0000, which is 0). Increment count to 3.
4. n = 0. Loop terminates.

Steps for (0b1000):

1. count = 0, n = 8 (0b1000). Since , compute (0b1000 & 0b0111 = 0b0000, which is 0). Increment count to 1.
2. n = 0. Loop terminates immediately because a power of two has only a single set bit.

Result

- For , the loop executed 3 iterations, yielding a popcount of 3.
- For , the loop executed 1 iteration, yielding a popcount of 1.
python
def count_bits_kernighan(n):
    c = 0
    while n:
        n &= n - 1
        c += 1
    return c
python
def trace_kernighan(n):
    # Trace n & (n-1) step by step
    pass
Kernighan's Algorithm Trace: n = 7 (3 bits) vs n = 8 (1 bit) n = 7 (0b0111) — 3 iterations Step 1: n = 7 (0b0111) 7 & 6 = 0b0110 (Val: 6) count = 1 Step 2: n = 6 (0b0110) 6 & 5 = 0b0100 (Val: 4) count = 2 Step 3: n = 4 (0b0100) 4 & 3 = 0b0000 (Val: 0) count = 3 Result: Popcount = 3 (3 Iterations) n = 8 (0b1000) — 1 iteration (Power of 2) Step 1: n = 8 (0b1000) 8 & 7 = 0b0000 (Val: 0) Single bit cleared instantly! count = 1 Why loop terminates immediately: • Powers of two have exactly ONE set bit. • n & (n-1) wipes that single bit instantly. • Skips all zero-bits (no wasted checks)! Result: Popcount = 1 (1 Iteration) Key takeaway: Loop iterations in Kernighan's algorithm always equal the exact popcount of n.
Tracing Kernighan's Algorithm on $n = 7$ and $n = 8$ diagram
Practice

Practice: Predict the Kernighan Drop Count for $n = 15$ and $n = 16$

Phase 4: Practice

Now that you have seen how Kernighan's algorithm drops the lowest set bit one by one—taking three drops for (0b111) and just one drop for (0b1000)—let us test your mental model on two new numbers.
Take a moment to trace the execution of n &= (n - 1) for and without writing full code. Think about their binary representations: 15 is just before a power of two, while 16 is a pure power of two.
The Exercise:
Predict the exact number of bit-clearing iterations (drops) the Kernighan loop requires for:
1.
2.
Write down your intermediate values of for each step, just like we did for in the previous phase.
Try this: Given n = 15 and n = 16:
•For n = 15: trace each step of n &= (n
•1) until n becomes 0.
•For n = 16: trace each step of n &= (n
•1) until n becomes 0.
•Compare your iteration counts.
Apply

Transfer: Designing a Range Popcount Vectorizer from Kernighan's Principle

Phase 5: Apply

We have seen how efficiently strips the lowest set bit, dropping the loop count down to the exact population count (3 drops for 7 and 1 drop for 8). We also used dynamic programming (ans[i] = ans[i >> 1] + (i & 1)) to build our base range 0..5 into [0, 1, 1, 2, 1, 2]. Now, let us apply this dual perspective—subtraction/clearing versus shifting/lookup—to a novel scenario where both techniques converge.
Imagine you are building a telemetry monitor that must log the population count of every active CPU core mask from 0 up to 255. If you ran Kernighan's algorithm independently for every single integer from 0 to 255, you would execute dozens of redundant bit inspections. Instead, you can merge our working example's lessons: use the recurrence relation to populate the array in time, while utilizing the identity to validate bit sparseness or detect exact powers of two on the fly.
python
def count_bits_range(n):
    ans = [0] * (n + 1)
    for i in range(1, n + 1):
        ans[i] = ans[i & (i - 1)] + 1
    return ans

# For n = 5: ans = [0, 1, 1, 2, 1, 2]
print(count_bits_range(5))
By leveraging ans[i & (i - 1)] + 1, each lookup references a previously solved subproblem where the lowest set bit was already stripped. This bridges single-number bit-clearing directly into full-range vector generation.
python
def verify_power_of_two(n):
    # Using n & (n-1), write a one-line boolean check
    # to see if n is a strictly positive power of two.
    pass

FAQ

What happens when you apply n & (n-1) to n = 7 and n = 8?
For n = 7 (0b111), n & (n-1) drops the lowest set bit three times to reach 0. For n = 8 (0b1000), since it's a power of two, it takes only 1 drop to reach 0.
Why is Brian Kernighan's algorithm faster than checking every bit?
Instead of checking all 32 or 64 bits in an integer, Kernighan's algorithm loops only as many times as there are set (1) bits, making its time complexity O(set bits) rather than O(total bits).
What is the time complexity of counting bits for numbers 0 to n?
Using Kernighan's algorithm across a range takes O(n log k) time where k is the number of set bits. However, dynamic programming can achieve O(n) using the relation popcount(i) = popcount(i & (i-1)) + 1.
Does n & (n-1) work for negative numbers?
Negative numbers in two's complement have an infinite sign-extension of leading 1-bits, causing infinite loops with standard bit-counting algorithms unless handled specifically.

Keep learning