How Do You Count the Number of Set Bits in an Integer Efficiently?
Learn Brian Kernighan’s bit-counting trick, its O(k) complexity, and how to answer this bit manipulation interview question.
Expected Interview Answer
The fastest general technique counts set bits in O(k) time, where k is the number of set bits, using Brian Kernighan’s trick: repeatedly apply n = n & (n - 1), which clears the lowest set bit on each iteration, and count how many iterations run until n becomes zero.
Subtracting 1 from n flips every bit from the lowest set bit down to bit 0: the lowest set bit becomes 0 and all bits below it (which were 0) become 1. ANDing n with (n - 1) then cancels out that flipped low region and clears exactly the lowest set bit, leaving every higher bit untouched. Looping this operation until n reaches zero takes exactly as many iterations as there are set bits, which beats the naive approach of checking all 32 or 64 bit positions one by one when the number is sparse. For repeated queries over many numbers, a precomputed popcount table or a DP recurrence (bits[n] = bits[n >> 1] + (n & 1)) amortizes the cost to O(1) per query after O(n) preprocessing, and most languages also expose a hardware popcount intrinsic (bin(n).count("1") in Python, or __builtin_popcount in C) that is fastest of all since it runs in a handful of CPU cycles.
- O(k) time where k is the count of set bits, faster than checking every bit
- Uses only one bitwise AND and one subtraction per iteration
- Extends naturally to a DP table for O(1) repeated queries
- Maps directly onto hardware popcount instructions for maximum speed
AI Mentor Explanation
Imagine a scoreboard represented as a row of lit and unlit bulbs for each fielding position that has been filled this over. Instead of checking every bulb on the board one at a time, a groundskeeper can repeatedly find the rightmost lit bulb and switch it off in a single motion, counting how many times they do this until the whole row is dark. Each single motion clears exactly one lit bulb no matter how many unlit bulbs sit below it, so a sparse row with just 3 lit bulbs takes only 3 motions, not a full sweep of the board. This is exactly Brian Kernighan’s trick: n & (n - 1) clears the lowest lit bit in one step, so the loop count equals the number of lit bulbs, not the board size.
Step-by-Step Explanation
Step 1
Start with the number and a counter at zero
Loop while n is nonzero.
Step 2
Clear the lowest set bit
n = n & (n - 1) removes exactly one set bit per iteration, regardless of its position.
Step 3
Increment the counter
Each successful clear corresponds to exactly one set bit found.
Step 4
Stop when n is zero
The counter now equals the total number of set bits; total iterations equal that count, not the bit width.
What Interviewer Expects
- Explain why n & (n - 1) clears the lowest set bit, not an arbitrary one
- State the O(k) complexity where k is the number of set bits, versus O(bit-width) for the naive loop
- Mention at least one faster alternative: DP table, lookup table, or hardware popcount
- Trace through a concrete example (e.g. n = 12 = 0b1100) correctly
Common Mistakes
- Believing n & (n - 1) always runs a fixed number of times regardless of how many bits are set
- Confusing this with clearing the highest set bit instead of the lowest
- Not knowing built-in popcount functions exist and are usually the fastest option in practice
- Off-by-one errors when translating the loop into working code
Best Answer (HR Friendly)
“To count how many bits are turned on in a number, I use a trick where n & (n - 1) always clears exactly the lowest turned-on bit, so I loop that operation and count how many times it takes to reach zero. That count is exactly the number of set bits, and it is faster than checking every single bit position, especially when the number is sparse.”
Code Example
def count_set_bits(n):
count = 0
while n:
n &= (n - 1) # clears the lowest set bit
count += 1
return count
print(count_set_bits(12)) # 0b1100 -> 2
# Python's built-in, backed by an efficient C implementation
print(bin(12).count("1")) # 2
print((12).bit_count()) # 2, Python 3.10+Follow-up Questions
- How would you build a DP table to answer set-bit-count queries in O(1) after preprocessing?
- How does n & (n - 1) differ from n & -n, and what does the latter isolate?
- How would you count set bits across a huge stream of numbers efficiently?
- How is popcount used in real systems like Hamming distance or bitmask DP?
MCQ Practice
1. What does the expression n & (n - 1) do to the binary representation of n?
Subtracting 1 flips the lowest set bit and everything below it; ANDing with the original cancels that region and clears just the lowest set bit.
2. What is the time complexity of counting set bits using Brian Kernighan’s trick?
Each loop iteration clears exactly one set bit, so the loop runs exactly k times for k set bits, independent of the bit width.
3. For n = 0b1100 (decimal 12), how many iterations does the Kernighan loop take?
12 has exactly two set bits (positions 2 and 3), so the loop clears one each iteration and finishes in 2 iterations.
Flash Cards
What does n & (n - 1) do? — Clears the lowest set bit of n, leaving all higher bits unchanged.
What is the time complexity of Kernighan’s popcount loop? — O(k), where k is the number of set bits in n.
Name a faster alternative for many repeated popcount queries. — A precomputed DP table (bits[n] = bits[n >> 1] + (n & 1)) or hardware popcount intrinsic.
What Python method directly gives the set-bit count (3.10+)? — (n).bit_count()