Introduction

Kernighan's bit counting algorithm counts how many 1 bits are present in an integer. Its power comes from one short identity: n & (n - 1) clears the lowest set bit of n.

That means the algorithm does not loop over every bit position. It loops only once per set bit, which is why it is elegant and often faster than the naive bit-by-bit approach.

The Core Trick

Suppose n is a positive integer. If you subtract 1, the rightmost 1 bit becomes 0, and every 0 to its right becomes 1.

Example with n = 12:

n      = 1100
n - 1  = 1011
n&(n-1)= 1000

The lowest set bit in 1100 was the second bit from the right. After the AND, that bit is gone.

This is the whole idea behind the algorithm: each application of n = n & (n - 1) removes exactly one 1 bit.

The Algorithm

A direct implementation looks like this:

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

Each loop removes one set bit and increments the counter. When the number becomes 0, there are no set bits left.

Why It Works

The key property is that n - 1 changes the bit pattern in a very predictable way:

• bits to the left of the lowest 1 stay the same
• the lowest 1 becomes 0
• bits to the right become 1

When you then AND the original value with n - 1, the only guaranteed bit removed is that lowest set bit. No other set bit to the left is disturbed.

So one iteration equals one removed 1, which means one iteration equals one counted set bit.

Walk Through an Example

Take n = 29, which is 11101 in binary.

1start: 11101
2step1: 11101 & 11100 = 11100
3step2: 11100 & 11011 = 11000
4step3: 11000 & 10111 = 10000
5step4: 10000 & 01111 = 00000

That took four iterations, so the number contains four set bits.

You can verify that directly: 11101 has four 1s.

Compare It with the Naive Approach

The naive method shifts through every bit position.

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

This checks every bit until the number becomes zero. Its running time depends on the number of bit positions examined.

Kernighan's method depends only on how many bits are set. If a number is sparse, it can do much less work.

Complexity

Kernighan's algorithm runs in O(k) time, where k is the number of set bits. The space complexity is O(1).

That is a nice improvement over approaches that inspect every bit position, especially for large integers with relatively few 1s.

Practical Context

This trick shows up in:

• population count implementations
• bitmask-based dynamic programming
• set-representation code using integers
• low-level performance-sensitive code

Modern languages may also provide built-in population count operations, but Kernighan's algorithm remains important because it explains the underlying bit logic so clearly.

Common Pitfalls

• Memorizing the formula without understanding that it clears the lowest set bit.
• Assuming it runs once per bit position rather than once per set bit.
• Forgetting that binary examples are the easiest way to see why it works.
• Using it on signed values without understanding the language's integer representation rules.
• Treating it as magical when the real trick is just subtraction plus bitwise AND.

Summary

• The identity n & (n - 1) clears the lowest set bit of n.
• Kernighan's algorithm counts bits by repeating that operation until the value becomes 0.
• The loop runs once per set bit, not once per bit position.
• Its time complexity is O(k), where k is the number of 1 bits.
• The algorithm is a classic because it turns a small bit trick into a clean counting method.