Data Structures & AlgorithmsPower of Two & Counting Bits

Power of Two & Counting Bits

LevelIntermediate

Duration50 mins

TopicPower of Two & Counting Bits

3 / 4

Brian Kernighan's Algorithm

An Algorithm Born from Elegance

In 1988, Brian Kernighan—co-creator of the C programming language and co-author of the legendary "K&R C" book—published a deceptively simple algorithm for counting set bits. The algorithm appears in his work on the AWK programming language and has since become a cornerstone of bit manipulation education.

What makes Kernighan's algorithm remarkable isn't just that it works—it's that it reveals a fundamental insight about binary arithmetic. The algorithm directly exploits the n & (n-1) operation we studied in Page 1, demonstrating how foundational bit manipulation patterns combine into powerful algorithms.

Where naive bit counting always examines every bit position, Kernighan's algorithm's running time depends only on how many bits are actually set. For sparse bit patterns, this means dramatic speedups. More importantly, understanding why this works deepens your mastery of binary representation.

What You Will Master

By the end of this page, you will understand how Kernighan's algorithm works, why it achieves O(b) complexity where b is the number of set bits, how it connects to the n & (n-1) pattern, and when to choose it over other popcount methods.

The Algorithm: Simple Yet Profound

Brian Kernighan's algorithm counts set bits by repeatedly clearing the rightmost set bit until the number becomes zero. Each iteration clears exactly one bit, so the number of iterations equals the number of set bits.

The Core Insight:

We already know from Page 1 that n & (n-1) clears the rightmost set bit of n. Kernighan's algorithm simply applies this operation repeatedly:

count = 0
while n != 0:
    n = n & (n-1)   // Clear the rightmost set bit
    count += 1       // Count the bit we just cleared
return count

Why It Works:

Each iteration removes exactly one bit from n. After b iterations (where b is the original bit count), n becomes zero and the loop terminates. We've counted exactly b iterations, which equals the bit count.

Visualization:

For n = 0b11010100 (popcount = 4):

Iteration	n (binary)	n & (n-1)	Bit Cleared	Count
Initial	11010100	—	—	0
1	11010100	11010000	bit 2	1
2	11010000	11000000	bit 4	2
3	11000000	10000000	bit 6	3
4	10000000	00000000	bit 7	4
Done	00000000	—	—	4 ✓

kernighan_algorithm.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def popcount_kernighan(n: int) -> int:
    """
    Brian Kernighan's algorithm for counting set bits.
    
    Time Complexity: O(b) where b = number of set bits
    Space Complexity: O(1)
    
    The algorithm clears the rightmost set bit in each iteration,
    so it runs exactly b times where b is the bit count.
    
    Args:
        n: Non-negative integer to count bits in
        
    Returns:
        Number of 1 bits in the binary representation of n
    """
    count = 0
    
    while n:
        n = n & (n - 1)  # Clear the rightmost set bit
        count += 1        # One more bit cleared
    
    return count
 
 
# Detailed trace for understanding:
def popcount_kernighan_traced(n: int) -> int:
    """
    Same algorithm with step-by-step output for learning.
    """
    print(f"Counting bits in {n} = {bin(n)}")
    count = 0
    iteration = 1
    
    while n:
        old_n = n
        n = n & (n - 1)
        count += 1
        print(f"  Iteration {iteration}: {bin(old_n)} & {bin(old_n - 1)} = {bin(n)}, count = {count}")
        iteration += 1
    
    print(f"Result: {count} bits")
    return count
 
 
# Test it:
# popcount_kernighan_traced(0b11010100)
# Output:
# Counting bits in 212 = 0b11010100
#   Iteration 1: 0b11010100 & 0b11010011 = 0b11010000, count = 1
#   Iteration 2: 0b11010000 & 0b11001111 = 0b11000000, count = 2
#   Iteration 3: 0b11000000 & 0b10111111 = 0b10000000, count = 3
#   Iteration 4: 0b10000000 & 0b1111111 = 0b0, count = 4
# Result: 4 bits

Formal Correctness Proof

Let's rigorously prove that Kernighan's algorithm correctly counts set bits. This requires proving two properties:

Loop Invariant: After k iterations, exactly k bits have been cleared from the original n, and count = k.
Termination: The loop terminates after exactly b iterations, where b is the original bit count.

Proof of Loop Invariant:

We prove by induction that after iteration k, count = k and the new n has exactly (original_popcount - k) bits set.

Base case (k=0): Before the loop, count = 0 and n has its original bit count. ✓

Inductive step: Assume after iteration k, count = k and n has (b - k) bits set where b is the original count.

In iteration k+1:

We compute n' = n & (n-1)
From Page 1, we know this clears exactly one bit (the rightmost)
So n' has (b - k - 1) = (b - (k+1)) bits set
We increment count to k + 1

After iteration k+1: count = k+1 and n has b - (k+1) bits. ✓

Proof of Termination:

After iteration b (original bit count), the new n has b - b = 0 bits set. So n = 0, and the while condition becomes false. The loop terminates with count = b. ✓

Why Formal Proofs Matter

In interviews and critical systems, being able to articulate WHY an algorithm works—not just THAT it works—demonstrates deep understanding. The ability to prove loop invariants and termination conditions distinguishes engineers who truly comprehend algorithms from those who merely memorize them.

Invariant at Each Step:

State	count	popcount(n)	count + popcount(n)
Initial	0	b	b
After 1st iteration	1	b-1	b
After 2nd iteration	2	b-2	b
After kth iteration	k	b-k	b
After bth iteration	b	0	b ✓

The invariant count + popcount(n) = original_popcount holds throughout. When n becomes 0 (popcount = 0), count equals the original popcount.

Complexity Analysis: When Kernighan Shines

Kernighan's algorithm has a fascinating complexity profile that differs from naive approaches.

Time Complexity:

Best case: O(1) when n = 0 (no iterations needed)
Worst case: O(k) when all k bits are set (e.g., 0xFFFFFFFF for 32-bit)
Average case: O(b) where b is the number of set bits
General bound: O(min(b, k)) where k is the word size

Space Complexity: O(1) — only a counter variable needed.

Comparison with Naive:

Kernighan vs Naive: Performance by Bit Pattern
Scenario	n (example)	Naive Iterations	Kernighan Iterations
Zero	0x00000000	32	0
Power of two	0x00000100	32	1
Very sparse	0x80000001	32	2
Half bits set	0xAAAAAAAA	32	16
Dense pattern	0xFFFFFFF0	32	28
All bits set	0xFFFFFFFF	32	32

When Kernighan Wins:

Kernighan's algorithm outperforms naive approaches when the bit pattern is sparse. Consider these scenarios:

Flags and bitmasks: Applications often use sparse bitmasks where only a few features are enabled. Kernighan processes these in O(b) instead of O(32).
Powers of two: Any power of two has exactly one bit set, so Kernighan completes in one iteration. This is common in hash tables, buffer sizes, and alignment checks.
Trailing zeros detection: Numbers with many trailing zeros (e.g., page addresses, aligned pointers) have few set bits.

When Kernighan Loses:

Dense patterns (many bits set): When most bits are 1, Kernighan does nearly as many iterations as naive while having slightly higher per-iteration overhead.
Uniform random distribution: Random 32-bit numbers average 16 set bits. Kernighan averages 16 iterations vs naive's 32, only 2x improvement.
Compared to SWAR or hardware: Kernighan's O(b) with 3 operations per iteration often loses to SWAR's fixed 12 operations or hardware POPCNT's 1-3 cycles.

The Per-Iteration Cost Matters

Kernighan does ~3 operations per iteration (AND, subtract, compare). For 16 iterations, that's 48 operations. SWAR does ~12 operations total. Hardware POPCNT is 1 instruction. So Kernighan's O(b) theoretical advantage often doesn't translate to wall-clock superiority except for very sparse patterns (b ≤ 3 or so).

The Deep Connection to n & (n-1)

Kernighan's algorithm beautifully illustrates how the fundamental n & (n-1) operation serves as a building block for more complex techniques. Let's explore this connection deeply.

Three Faces of n & (n-1):

Power of Two Test: n & (n-1) == 0 checks if n has exactly one bit set.
Clear Rightmost Bit: n & (n-1) removes the lowest set bit from n.
Kernighan's Popcount: Repeatedly applying #2 and counting iterations gives the total bit count.

The Unifying Principle:

All three uses stem from the same underlying truth: subtracting 1 from n creates a number that differs from n in exactly the low-order bits from the rightmost 1 onward. The AND operation exploits this difference.

n       = ...XXXXX1000...000
n - 1   = ...XXXXX0111...111
n & n-1 = ...XXXXX0000...000

The rightmost 1 and all bits to its right are cleared. Bits to the left (marked X) are preserved.

Power of Two (from Page 1):

def is_power_of_two(n):
    return n > 0 and n & (n-1) == 0

If n has exactly one bit, clearing it leaves zero.

Kernighan insight: This is equivalent to asking "does Kernighan's algorithm terminate after exactly 1 iteration?"

Kernighan's Popcount:

def popcount(n):
    count = 0
    while n:
        n = n & (n-1)
        count += 1
    return count

Count how many times we can clear a bit before reaching zero.

Building Block Thinking

This pattern exemplifies how mastering fundamental operations enables solving complex problems. The n & (n-1) operation is a building block that appears in power-of-two checks, bit counting, rounding down to power-of-two, and more. Once you deeply understand the building block, the applications become obvious extensions.

Variations and Extensions

The Kernighan technique extends to several related problems. Understanding these variations deepens your bit manipulation toolkit.

Problem: Instead of just counting, find the positions of all set bits.

Approach: Use Kernighan's iteration pattern but extract each bit's position before clearing it.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def find_set_bit_positions(n: int) -> list[int]:
    """
    Return the positions (0-indexed from right) of all set bits.
    
    Uses Kernighan's pattern with bit position extraction via log2.
    
    Time: O(b) where b = number of set bits
    """
    positions = []
    
    while n:
        # Extract the rightmost set bit
        rightmost_bit = n & (-n)  # Isolate lowest set bit
        
        # Find its position using bit_length
        position = rightmost_bit.bit_length() - 1
        positions.append(position)
        
        # Clear this bit (Kernighan's step)
        n = n & (n - 1)
    
    return positions
 
 
# Example:
print(find_set_bit_positions(0b11010100))
# Output: [2, 4, 6, 7]  (positions of the 1s)

Historical Context and Attribution

Brian Kernighan:

Brian Wilson Kernighan (born 1942) is a Canadian computer scientist who worked at Bell Labs and is now a professor at Princeton University. He's perhaps best known for:

Co-authoring "The C Programming Language" with Dennis Ritchie (the "K&R" book)
Co-creating the AWK programming language with Alfred Aho and Peter Weinberger
Contributing to Unix and numerous fundamental programming tools

The algorithm we call "Kernighan's" appeared in his work on AWK in the 1988 book "The AWK Programming Language." However, the technique of using n & (n-1) to clear bits has earlier origins.

Prior Art:

The n & (n-1) operation and its properties were known to computer pioneers in the 1960s. Variations appear in:

MIT's "HAKMEM" memo (1972) - a legendary collection of bit twiddling hacks
Peter Wegner's published the loop-based variant in 1960
Various assembly language tricks from the PDP and IBM mainframe eras

Kernighan's name became attached to the algorithm because his presentation in "The AWK Programming Language" made it widely accessible to programmers outside systems/hardware circles.

The Naming Tradition

Many algorithms bear the names of those who popularized or clearly explained them, rather than their original inventors. Kernighan's algorithm, Boyer-Moore voting algorithm, and others follow this pattern. The key contribution is often clear communication that makes the technique accessible.

When to Use Kernighan's Algorithm

Knowing when Kernighan's algorithm is the right choice requires understanding its strengths and weaknesses relative to alternatives.

Use Kernighan When

•Sparse bit patterns expected — Few bits set relative to word size
•Variable-width integers — Python's arbitrary precision integers
•Code simplicity matters — Easy to implement, remember, and verify
•No hardware popcount — Embedded systems without POPCNT
•Interview settings — Demonstrates understanding of bit manipulation
•Teaching/learning — Clear connection between n & (n-1) and popcount
•Need to process each bit — When you're doing more than just counting

Avoid Kernighan When

•Dense bit patterns expected — Many bits set; SWAR or hardware wins
•Performance critical loops — Hardware POPCNT or SWAR is faster
•Bulk operations — Counting millions of values; use vectorized approaches
•Hardware support available — Modern x86/ARM have POPCNT instruction
•Uniform random distribution — Average case not much better than naive
•Fixed-width with table space — Lookup tables may be faster

choosing_popcount.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# Decision guide in code:
 
def choose_popcount_method(context: str) -> str:
    """
    Guide for choosing the right popcount implementation.
    """
    
    recommendations = {
        "interview": "Kernighan - Shows understanding, easy to derive",
        "production_python": "n.bit_count() - Built-in, optimized",
        "embedded_no_space": "Kernighan - No lookup table needed",
        "performance_critical": "Check if POPCNT available; else SWAR",
        "arbitrary_precision": "Kernighan - Works for any size integer",
        "educational": "Start naive, evolve to Kernighan, then SWAR",
        "counting_sparse_flags": "Kernighan - O(b) where b is small",
    }
    
    return recommendations.get(context, "Use language built-in if available")
 
 
# Practical example: Feature flag checking
# Kernighan shines here because flags are typically sparse
 
class FeatureFlags:
    """Feature flags with efficient bit counting."""
    
    READ = 1 << 0
    WRITE = 1 << 1
    DELETE = 1 << 2
    ADMIN = 1 << 3
    # ... up to 64 possible flags
    
    @staticmethod
    def count_enabled(flags: int) -> int:
        """
        Count enabled features.
        
        Typically very few flags are set (3-5 out of 64),
        so Kernighan's O(b) is optimal here.
        """
        count = 0
        while flags:
            flags &= flags - 1
            count += 1
        return count

Summary and Key Takeaways

Brian Kernighan's algorithm elegantly connects the fundamental n & (n-1) operation to the practical problem of counting set bits. Let's consolidate the key insights:

Key Takeaways

•The algorithm is beautifully simple — Clear rightmost bit, increment counter, repeat until zero.
•Complexity is O(b) — Runtime depends on bit count, not word size, giving advantage for sparse patterns.
•It builds on n & (n-1) — The same operation that detects powers of two enables efficient counting.
•Formal proof is straightforward — Loop invariant and termination follow directly from the bit-clearing property.
•Best for sparse patterns — Shines when few bits are set; loses to SWAR/hardware for dense patterns.
•Extensions are natural — Finding positions, iterating bits, computing parity, Hamming distance all follow the same pattern.
•Interview favorite — Easy to remember, derive, and explain; demonstrates bit manipulation mastery.

What's Next:

In the final page of this module, we'll explore built-in functions for counting bits across different programming languages. We'll see how modern hardware and language libraries optimize these operations, and understand when to use built-ins versus implementing your own.

Page Complete

You've mastered Brian Kernighan's elegant algorithm for counting set bits. This technique beautifully demonstrates how fundamental bit operations combine into powerful algorithms. Next, we'll explore the landscape of built-in popcount functions and hardware support.

3 / 4

Loading learning content...

Data Structures & AlgorithmsPower of Two & Counting Bits

Power of Two & Counting Bits

LevelIntermediate

Duration50 mins

TopicPower of Two & Counting Bits

3 / 4

Brian Kernighan's Algorithm

An Algorithm Born from Elegance

What You Will Master

The Algorithm: Simple Yet Profound

The Core Insight:

We already know from Page 1 that n & (n-1) clears the rightmost set bit of n. Kernighan's algorithm simply applies this operation repeatedly:

count = 0
while n != 0:
    n = n & (n-1)   // Clear the rightmost set bit
    count += 1       // Count the bit we just cleared
return count

Why It Works:

Visualization:

For n = 0b11010100 (popcount = 4):

Iteration	n (binary)	n & (n-1)	Bit Cleared	Count
Initial	11010100	—	—	0
1	11010100	11010000	bit 2	1
2	11010000	11000000	bit 4	2
3	11000000	10000000	bit 6	3
4	10000000	00000000	bit 7	4
Done	00000000	—	—	4 ✓

kernighan_algorithm.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def popcount_kernighan(n: int) -> int:
    """
    Brian Kernighan's algorithm for counting set bits.
    
    Time Complexity: O(b) where b = number of set bits
    Space Complexity: O(1)
    
    The algorithm clears the rightmost set bit in each iteration,
    so it runs exactly b times where b is the bit count.
    
    Args:
        n: Non-negative integer to count bits in
        
    Returns:
        Number of 1 bits in the binary representation of n
    """
    count = 0
    
    while n:
        n = n & (n - 1)  # Clear the rightmost set bit
        count += 1        # One more bit cleared
    
    return count
 
 
# Detailed trace for understanding:
def popcount_kernighan_traced(n: int) -> int:
    """
    Same algorithm with step-by-step output for learning.
    """
    print(f"Counting bits in {n} = {bin(n)}")
    count = 0
    iteration = 1
    
    while n:
        old_n = n
        n = n & (n - 1)
        count += 1
        print(f"  Iteration {iteration}: {bin(old_n)} & {bin(old_n - 1)} = {bin(n)}, count = {count}")
        iteration += 1
    
    print(f"Result: {count} bits")
    return count
 
 
# Test it:
# popcount_kernighan_traced(0b11010100)
# Output:
# Counting bits in 212 = 0b11010100
#   Iteration 1: 0b11010100 & 0b11010011 = 0b11010000, count = 1
#   Iteration 2: 0b11010000 & 0b11001111 = 0b11000000, count = 2
#   Iteration 3: 0b11000000 & 0b10111111 = 0b10000000, count = 3
#   Iteration 4: 0b10000000 & 0b1111111 = 0b0, count = 4
# Result: 4 bits

Formal Correctness Proof

Let's rigorously prove that Kernighan's algorithm correctly counts set bits. This requires proving two properties:

Loop Invariant: After k iterations, exactly k bits have been cleared from the original n, and count = k.
Termination: The loop terminates after exactly b iterations, where b is the original bit count.

Proof of Loop Invariant:

We prove by induction that after iteration k, count = k and the new n has exactly (original_popcount - k) bits set.

Base case (k=0): Before the loop, count = 0 and n has its original bit count. ✓

Inductive step: Assume after iteration k, count = k and n has (b - k) bits set where b is the original count.

In iteration k+1:

We compute n' = n & (n-1)
From Page 1, we know this clears exactly one bit (the rightmost)
So n' has (b - k - 1) = (b - (k+1)) bits set
We increment count to k + 1

After iteration k+1: count = k+1 and n has b - (k+1) bits. ✓

Proof of Termination:

After iteration b (original bit count), the new n has b - b = 0 bits set. So n = 0, and the while condition becomes false. The loop terminates with count = b. ✓

Why Formal Proofs Matter

Invariant at Each Step:

State	count	popcount(n)	count + popcount(n)
Initial	0	b	b
After 1st iteration	1	b-1	b
After 2nd iteration	2	b-2	b
After kth iteration	k	b-k	b
After bth iteration	b	0	b ✓

The invariant count + popcount(n) = original_popcount holds throughout. When n becomes 0 (popcount = 0), count equals the original popcount.

Complexity Analysis: When Kernighan Shines

Kernighan's algorithm has a fascinating complexity profile that differs from naive approaches.

Time Complexity:

Best case: O(1) when n = 0 (no iterations needed)
Worst case: O(k) when all k bits are set (e.g., 0xFFFFFFFF for 32-bit)
Average case: O(b) where b is the number of set bits
General bound: O(min(b, k)) where k is the word size

Space Complexity: O(1) — only a counter variable needed.

Comparison with Naive:

Kernighan vs Naive: Performance by Bit Pattern
Scenario	n (example)	Naive Iterations	Kernighan Iterations
Zero	0x00000000	32	0
Power of two	0x00000100	32	1
Very sparse	0x80000001	32	2
Half bits set	0xAAAAAAAA	32	16
Dense pattern	0xFFFFFFF0	32	28
All bits set	0xFFFFFFFF	32	32

When Kernighan Wins:

Kernighan's algorithm outperforms naive approaches when the bit pattern is sparse. Consider these scenarios:

Flags and bitmasks: Applications often use sparse bitmasks where only a few features are enabled. Kernighan processes these in O(b) instead of O(32).
Powers of two: Any power of two has exactly one bit set, so Kernighan completes in one iteration. This is common in hash tables, buffer sizes, and alignment checks.
Trailing zeros detection: Numbers with many trailing zeros (e.g., page addresses, aligned pointers) have few set bits.

When Kernighan Loses:

Dense patterns (many bits set): When most bits are 1, Kernighan does nearly as many iterations as naive while having slightly higher per-iteration overhead.
Uniform random distribution: Random 32-bit numbers average 16 set bits. Kernighan averages 16 iterations vs naive's 32, only 2x improvement.
Compared to SWAR or hardware: Kernighan's O(b) with 3 operations per iteration often loses to SWAR's fixed 12 operations or hardware POPCNT's 1-3 cycles.

The Per-Iteration Cost Matters

The Deep Connection to n & (n-1)

Kernighan's algorithm beautifully illustrates how the fundamental n & (n-1) operation serves as a building block for more complex techniques. Let's explore this connection deeply.

Three Faces of n & (n-1):

Power of Two Test: n & (n-1) == 0 checks if n has exactly one bit set.
Clear Rightmost Bit: n & (n-1) removes the lowest set bit from n.
Kernighan's Popcount: Repeatedly applying #2 and counting iterations gives the total bit count.

The Unifying Principle:

n       = ...XXXXX1000...000
n - 1   = ...XXXXX0111...111
n & n-1 = ...XXXXX0000...000

The rightmost 1 and all bits to its right are cleared. Bits to the left (marked X) are preserved.

Power of Two (from Page 1):

def is_power_of_two(n):
    return n > 0 and n & (n-1) == 0

If n has exactly one bit, clearing it leaves zero.

Kernighan insight: This is equivalent to asking "does Kernighan's algorithm terminate after exactly 1 iteration?"

Kernighan's Popcount:

def popcount(n):
    count = 0
    while n:
        n = n & (n-1)
        count += 1
    return count

Count how many times we can clear a bit before reaching zero.

Building Block Thinking

Variations and Extensions

The Kernighan technique extends to several related problems. Understanding these variations deepens your bit manipulation toolkit.

Problem: Instead of just counting, find the positions of all set bits.

Approach: Use Kernighan's iteration pattern but extract each bit's position before clearing it.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def find_set_bit_positions(n: int) -> list[int]:
    """
    Return the positions (0-indexed from right) of all set bits.
    
    Uses Kernighan's pattern with bit position extraction via log2.
    
    Time: O(b) where b = number of set bits
    """
    positions = []
    
    while n:
        # Extract the rightmost set bit
        rightmost_bit = n & (-n)  # Isolate lowest set bit
        
        # Find its position using bit_length
        position = rightmost_bit.bit_length() - 1
        positions.append(position)
        
        # Clear this bit (Kernighan's step)
        n = n & (n - 1)
    
    return positions
 
 
# Example:
print(find_set_bit_positions(0b11010100))
# Output: [2, 4, 6, 7]  (positions of the 1s)

Historical Context and Attribution

Brian Kernighan:

Brian Wilson Kernighan (born 1942) is a Canadian computer scientist who worked at Bell Labs and is now a professor at Princeton University. He's perhaps best known for:

Co-authoring "The C Programming Language" with Dennis Ritchie (the "K&R" book)
Co-creating the AWK programming language with Alfred Aho and Peter Weinberger
Contributing to Unix and numerous fundamental programming tools

The algorithm we call "Kernighan's" appeared in his work on AWK in the 1988 book "The AWK Programming Language." However, the technique of using n & (n-1) to clear bits has earlier origins.

Prior Art:

The n & (n-1) operation and its properties were known to computer pioneers in the 1960s. Variations appear in:

MIT's "HAKMEM" memo (1972) - a legendary collection of bit twiddling hacks
Peter Wegner's published the loop-based variant in 1960
Various assembly language tricks from the PDP and IBM mainframe eras

Kernighan's name became attached to the algorithm because his presentation in "The AWK Programming Language" made it widely accessible to programmers outside systems/hardware circles.

The Naming Tradition

When to Use Kernighan's Algorithm

Knowing when Kernighan's algorithm is the right choice requires understanding its strengths and weaknesses relative to alternatives.

Use Kernighan When

•Sparse bit patterns expected — Few bits set relative to word size
•Variable-width integers — Python's arbitrary precision integers
•Code simplicity matters — Easy to implement, remember, and verify
•No hardware popcount — Embedded systems without POPCNT
•Interview settings — Demonstrates understanding of bit manipulation
•Teaching/learning — Clear connection between n & (n-1) and popcount
•Need to process each bit — When you're doing more than just counting

Avoid Kernighan When

•Dense bit patterns expected — Many bits set; SWAR or hardware wins
•Performance critical loops — Hardware POPCNT or SWAR is faster
•Bulk operations — Counting millions of values; use vectorized approaches
•Hardware support available — Modern x86/ARM have POPCNT instruction
•Uniform random distribution — Average case not much better than naive
•Fixed-width with table space — Lookup tables may be faster

choosing_popcount.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# Decision guide in code:
 
def choose_popcount_method(context: str) -> str:
    """
    Guide for choosing the right popcount implementation.
    """
    
    recommendations = {
        "interview": "Kernighan - Shows understanding, easy to derive",
        "production_python": "n.bit_count() - Built-in, optimized",
        "embedded_no_space": "Kernighan - No lookup table needed",
        "performance_critical": "Check if POPCNT available; else SWAR",
        "arbitrary_precision": "Kernighan - Works for any size integer",
        "educational": "Start naive, evolve to Kernighan, then SWAR",
        "counting_sparse_flags": "Kernighan - O(b) where b is small",
    }
    
    return recommendations.get(context, "Use language built-in if available")
 
 
# Practical example: Feature flag checking
# Kernighan shines here because flags are typically sparse
 
class FeatureFlags:
    """Feature flags with efficient bit counting."""
    
    READ = 1 << 0
    WRITE = 1 << 1
    DELETE = 1 << 2
    ADMIN = 1 << 3
    # ... up to 64 possible flags
    
    @staticmethod
    def count_enabled(flags: int) -> int:
        """
        Count enabled features.
        
        Typically very few flags are set (3-5 out of 64),
        so Kernighan's O(b) is optimal here.
        """
        count = 0
        while flags:
            flags &= flags - 1
            count += 1
        return count

Summary and Key Takeaways

Brian Kernighan's algorithm elegantly connects the fundamental n & (n-1) operation to the practical problem of counting set bits. Let's consolidate the key insights:

Key Takeaways

•The algorithm is beautifully simple — Clear rightmost bit, increment counter, repeat until zero.
•Complexity is O(b) — Runtime depends on bit count, not word size, giving advantage for sparse patterns.
•It builds on n & (n-1) — The same operation that detects powers of two enables efficient counting.
•Formal proof is straightforward — Loop invariant and termination follow directly from the bit-clearing property.
•Best for sparse patterns — Shines when few bits are set; loses to SWAR/hardware for dense patterns.
•Extensions are natural — Finding positions, iterating bits, computing parity, Hamming distance all follow the same pattern.
•Interview favorite — Easy to remember, derive, and explain; demonstrates bit manipulation mastery.

What's Next:

Page Complete

3 / 4