Introduction

Brian Kernighan’s bit-counting algorithm is a classic way to count how many set bits, or 1 bits, appear in an integer. Its key advantage is that it loops once per set bit rather than once per bit position, which makes it especially efficient when the value has relatively few 1 bits.

Core Sections

The key identity behind the algorithm

The algorithm relies on one observation:

• 'n & (n - 1) clears the lowest set bit in n'

For example, if n = 22, its binary form is 10110.

• 'n - 1 is 10101'
• 'n & (n - 1) becomes 10100'

Only the rightmost 1 bit disappears. Repeating that operation until the number becomes zero tells you how many set bits there were.

A direct implementation

1def count_bits(n: int) -> int:
2    count = 0
3    while n:
4        n &= n - 1
5        count += 1
6    return count
7
8
9print(count_bits(23))
10print(count_bits(0))
11print(count_bits(54))

For 23, which is 10111 in binary, the algorithm runs four times because there are four set bits.

Step-by-step example

Take n = 23.

Binary form: 10111

Iteration sequence:

• '10111'
• '10110'
• '10100'
• '10000'
• '00000'

Each iteration removes exactly one 1, so the total number of iterations is the answer.

That is what makes the algorithm elegant: the loop count and the bit count are the same thing.

Time complexity is O(k), not O(word_size)

If k is the number of set bits, Brian Kernighan’s algorithm runs in O(k) time. That is better than a naive bit-by-bit scan when the integer is sparse.

A naive approach checks every bit position.

1def count_bits_naive(n: int) -> int:
2    count = 0
3    while n:
4        count += n & 1
5        n >>= 1
6    return count

This naive loop takes one iteration per bit position until the value becomes zero. Brian Kernighan’s version takes one iteration per set bit only.

So:

• dense bit patterns narrow the advantage
• sparse bit patterns make the algorithm especially attractive

Negative numbers require width awareness

In languages with fixed-width integers such as C, Java, or C#, the meaning of bit operations is tied to the integer width. In Python, integers are arbitrary precision, so negative values behave differently unless you apply a mask.

If you want an 8-bit interpretation, make the width explicit.

1def count_bits_8bit(n: int) -> int:
2    n &= 0xFF
3    count = 0
4    while n:
5        n &= n - 1
6        count += 1
7    return count
8
9
10print(count_bits_8bit(-1))

Without width control, talking about the set bits of a negative integer becomes ambiguous in Python.

Built-in popcount can be even better

Many modern languages and CPUs provide built-in bit-counting support. In Python, int.bit_count() already exists.

print((23).bit_count())

In production code, a built-in is often the better choice because it is clear, tested, and potentially mapped to efficient machine instructions. Brian Kernighan’s algorithm is still worth knowing because it explains the underlying idea and appears frequently in interviews and low-level code discussions.

Common Pitfalls

• Forgetting that n & (n - 1) removes only the lowest set bit makes the algorithm look magical instead of understandable.
• Claiming the complexity is always O(log n) misses the sharper fact that it is O(k), where k is the number of set bits.
• Applying the algorithm to negative Python integers without a width mask creates ambiguity about what bit pattern is being counted.
• Reimplementing the algorithm in production code when a clear built-in popcount exists may reduce readability for little gain.
• Using bit tricks without test cases makes off-by-one reasoning and width assumptions harder to catch.

Summary

• Brian Kernighan’s algorithm counts set bits by repeatedly applying n &= n - 1.
• Each loop iteration removes one 1 bit, so the runtime is O(k) where k is the number of set bits.
• It is often faster than scanning every bit position when the value is sparse.
• In Python, negative numbers need explicit width masking if you want a fixed-width interpretation.
• Built-in popcount methods are often preferable in production, but the algorithm remains an important bit-manipulation technique to understand.