Counting Bits and Popcount

Why Counting Bits Matters

Counting the number of 1 bits in an integer sounds tiny, but it shows up everywhere. Permission masks need to know how many capabilities are enabled. Hamming distance compares binary strings by counting differing bits. Compression, chess engines, bloom filters, scheduling, and CPU instructions all rely on popcount in some form. In interviews, the topic appears both as a direct question and as a building block inside larger dynamic-programming or bitmask problems. The important lesson is that you do not always need to inspect every bit one by one if the binary structure already tells you where the work is.

There are three levels of sophistication worth knowing. The first is the straightforward loop that shifts through every position. The second is Brian Kernighan’s algorithm, which removes one set bit per iteration. The third is dynamic programming for computing popcounts for every number from 0 through n. Those three methods answer slightly different questions. One is great for a single value, one is great when the number has few set bits, and one is great when you need answers for an entire range.

From Naive Scanning to Brian Kernighan’s Algorithm

The naive method is conceptually clean: inspect the least-significant bit with n & 1, add it to the answer, then shift n right. Repeat until the number becomes zero. This works because the rightmost bit fully tells you whether the current number is odd or even. After you count that bit, shifting right discards it and exposes the next one. If you are learning the topic for the first time, this is the method you should be able to explain before moving to the faster identity.

Brian Kernighan’s algorithm asks a smarter question: instead of checking every position, can we jump directly from one set bit to the next? The answer is yes because n & (n - 1) removes the lowest set bit. If you apply that operation repeatedly, the number loses one 1 at a time. Therefore the number of loop iterations equals the number of set bits, not the width of the integer. For sparse numbers with only a few ones, that can be much cheaper than scanning all 32 or 64 positions.

44 = 101100
43 = 101011
----------------
44 & 43 = 101000

40 = 101000
39 = 100111
----------------
40 & 39 = 100000

32 = 100000
31 = 011111
----------------
32 & 31 = 000000

Worked Example: Counting Bits from 0 Through 8

Now consider the range problem: for every i from 0 to 8, compute how many set bits it contains. Doing an independent popcount for each value works, but it repeats structure. Notice what happens when you shift a number right by one. You drop the least-significant bit, which means i >> 1 is simply i without its last binary digit. That gives a recurrence: bits[i] = bits[i >> 1] + (i & 1). The last term is 1 when i is odd and 0 when i is even.

Walk the recurrence slowly. bits[0] = 0. For 1, bits[1] = bits[0] + 1 = 1. For 2, bits[2] = bits[1] + 0 = 1 because 2 is 10 in binary. For 3, bits[3] = bits[1] + 1 = 2 because 3 is 11. For 4, bits[4] = bits[2] + 0 = 1. Each answer reuses a smaller answer that you already computed. That is why this is dynamic programming: build a table where every new state borrows from a simpler, previously solved state.

A second recurrence is also common: bits[i] = bits[i & (i - 1)] + 1. It says “remove one set bit, count the rest recursively, then add one back.” This version mirrors Brian Kernighan’s algorithm and sometimes feels more intuitive if that identity is already in your head. Both recurrences are valid. The shift-based one is especially easy to derive, while the remove-one-bit version emphasizes the same structural shortcut from the single-value popcount loop.

This is a good example of a wider DP pattern: if you can describe how one tiny structural edit transforms a state into a smaller solved state, you can often tabulate the answers in increasing order. Here the edit is either “drop the last bit” or “remove one set bit.” In other topics the edit might be “remove the last character” or “take one item from the prefix.” Popcount is small enough that you can see the recurrence immediately, which makes it excellent practice for building DP instincts.

Go Implementation

The code below includes both a direct popcount and the range dynamic-programming version. In production Go you may also use the standard-library bit utilities, but being able to derive the logic yourself is what helps in interviews and in low-level debugging.

Practical Notes and Common Misconceptions

A common misconception is that “bit counting” always means raw bit-twiddling by hand. In real systems code, using a CPU-accelerated builtin is often the right engineering choice. The value of learning these algorithms is not to avoid standard libraries forever; it is to understand what those libraries are doing and to recognize problems where you can reuse the same structure in a custom way. Interviews especially care that you can reason from representation to algorithm.

Another practical consideration is whether the work is query-heavy or preprocessing-heavy. If you only need one popcount, a direct loop is enough. If you need popcount for every mask in a subset-DP problem, precomputing once may save substantial repeated work later. That kind of trade-off shows up constantly in algorithms: one-off queries favor simple local logic, while many related queries often justify a table or cache built in advance.

The DP recurrence also teaches a bigger lesson that appears all over algorithms: if a state can be reduced to a slightly smaller state by removing one local feature, a table may be possible. Here the local feature is the least-significant bit. In other topics it might be the last character of a string, the last row of a grid, or one edge in a graph. Popcount is a small but powerful example of how representation can reveal a recurrence.

Practice Problems

Quiz

Summary

• Naive popcount inspects every bit position.
• Brian Kernighan’s algorithm removes one set bit per loop, so it runs in O(popcount).
• Range counting uses a recurrence because each number is a slightly larger version of a smaller number.
• bits[i] = bits[i>>1] + (i&1) is one of the cleanest DP recurrences in the entire DSA toolbox.
• Popcount often combines with XOR to measure differences between values.