Counting Set Bits: Brian Kernighan's Trick and Counting Bits

"Count the 1 bits in an integer" sounds like a warm-up, and the obvious loop does solve it. The question exists for the follow-up: can you do it in fewer steps than there are bits? The answer is one expression, x & (x - 1), and explaining why that expression removes exactly one bit is what separates a memorised trick from an understood one. The same expression then gives a clean answer to the counting bits table problem.

The problem it solves

The number of 1 bits in a value is called its population count, or Hamming weight. 44 is 0b101100, so its count is 3. You need it whenever a bitmap stands for a set: how many rows matched a bitmap index, how many permissions a mask grants, how many positions two codes differ in.

The first answer most people write shifts through the value one lane at a time, adding the lowest bit. That touches every bit up to the highest 1, so a 32-bit value with a single high bit set takes 32 iterations to find one 1.

The intuition

Look at what subtracting 1 does in binary. It finds the lowest 1, turns it into a 0, and turns every 0 below it into a 1. Everything above the lowest 1 is untouched:

• x = 0b101100
• x - 1 = 0b101011

Now AND the two. Above the lowest 1 the two values are identical, so those bits survive. At the lowest 1 and below it, the two values are exact opposites, so the AND gives zeros there. The result is x with its lowest 1 cleared and nothing else changed: 0b101000.

Repeat until the value is zero and count the repetitions. Each pass removes exactly one 1, so the loop runs once per set bit, and the zeros are never visited. For sparse values, such as bitmaps where most lanes are empty, that is a large saving over checking all 64 lanes of every word.

The same expression answers another common question: x & (x - 1) == 0 for a positive x means it had exactly one 1, which is the test for a power of two.

Watch it run

The animation starts with 44 in eight lanes: three 1s among them, so checking every lane would visit five zeros for nothing. Subtracting 1 flips the lowest 1 off and turns every 0 beneath it on, while nothing above moves. AND the two rows and that whole tail is wiped: 44 becomes 40, one 1 lighter, and the count is 1. It starts again from 40, because the trick does not care which lanes are empty. Same move, one lane further left: 40 becomes 32, and the count is now 2. 32 has a single 1 left, so 31 is all ones below it, and the AND empties the row entirely. x is now 0 and the loop stops. Three iterations for three set bits, and the five empty lanes were never looked at once.

The code

The lesson's loop:

def popcount(x):
    count = 0
    while x:
        x &= x - 1                  # wipes the lowest set bit, nothing else
        count += 1
    return count                    # one pass per 1, not per bit

print(popcount(44), popcount(255), popcount(8))   # 3 8 1

The three passes on 44, printed as the animation's rows, x, x - 1 and their AND:

x = 44
while x:
    print(format(x, "08b"), format(x - 1, "08b"), "->", format(x & (x - 1), "08b"))
    x &= x - 1
# 00101100 00101011 -> 00101000
# 00101000 00100111 -> 00100000
# 00100000 00011111 -> 00000000

The shift loop for comparison, and the iteration counts on a value with only its top bit set:

def popcount_shift(x):
    count = 0
    while x:
        count += x & 1              # look at every lane, zeros included
        x >>= 1
    return count

def loops(x, step):
    n = 0
    while x:
        x = step(x)
        n += 1
    return n

print(loops(1 << 31, lambda v: v & (v - 1)))      # 1
print(loops(1 << 31, lambda v: v >> 1))           # 32

Python integers have no fixed width, so a negative value has infinitely many leading 1s and while x would never end. Mask to the width the question means first:

def popcount32(x):
    return popcount(x & 0xFFFFFFFF)                # two's complement view of a negative

print(popcount32(-1), popcount32(-8))              # 32 29

The counting bits problem asks for the count of every number from 0 to n. Removing the lowest 1 gives a smaller number whose count is already in the table, so each entry is that entry plus one:

def count_bits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i & (i - 1)] + 1            # i with its lowest 1 removed, plus that 1
    return bits

print(count_bits(8))        # [0, 1, 1, 2, 1, 2, 2, 3, 1]

def hamming_distance(a, b):
    return popcount(a ^ b)                          # the lanes where they differ

print(hamming_distance(1, 4))                       # 2

Everything against bin(v).count("1") on 20,000 random values up to 64 bits, random negatives in 32 bits, and a table of 5,001 entries:

import random

random.seed(19)
ok = True
for _ in range(20000):
    v = random.getrandbits(random.randint(0, 64))
    ok &= popcount(v) == popcount_shift(v) == bin(v).count("1")
    ok &= loops(v, lambda y: y & (y - 1)) == bin(v).count("1")
    neg = -random.randint(1, 2**31)
    ok &= popcount32(neg) == format(neg & 0xFFFFFFFF, "032b").count("1")
table = count_bits(5000)
ok &= all(table[i] == bin(i).count("1") for i in range(5001))
print(ok)                                           # True

The complexity

• Kernighan's loop: O(k) iterations for k set bits, at most the word width. Space O(1).
• The shift loop: O(b), where b is the position of the highest 1, so up to 32 or 64 for a fixed-width word.
• Counting bits for 0 to n: O(n) time for the whole table, one lookup per entry, instead of O(n·b) for counting each number separately.
• In practice: most CPUs have a population count instruction, and languages expose it, for example int.bit_count() since Python 3.10. In an interview, name it, then show the loop you were asked for.

Where it goes wrong

• Negative numbers in Python. -1 has no end to its 1s. Mask with 0xFFFFFFFF or the width the problem states.
• Negative numbers in other languages. An arithmetic right shift copies the sign bit in, so the shift loop can run forever; use an unsigned shift or Kernighan's loop.
• Writing x & x - 1 without thinking about precedence. In Python it works, because - binds tighter than &. In C-family languages it also works, but x & (x - 1) == 0 does not: == binds tighter than & there. Use parentheses everywhere.
• Using the power-of-two test on zero. 0 & -1 is 0, so zero passes unless you also check x > 0.

When it shows up in interviews

"Number of 1 bits", "counting bits" and "Hamming distance" are standard easy questions, and "is this a power of two?" often comes first. The follow-ups test understanding: why the loop is proportional to the number of 1s, how to handle negatives, and how the counting bits table reuses smaller answers, which makes it a tiny dynamic programming problem. More mask tricks are in bit masks and powers of two and XOR tricks.

How to say it in an interview

"Subtracting 1 clears the lowest set bit and sets every bit below it, and nothing above changes. So x & (x - 1) is x with exactly its lowest 1 removed. I repeat that until x is zero and count the steps, which is one iteration per set bit instead of one per bit position. For negatives I mask to 32 bits first. For the counting bits table I reuse the same idea: i & (i - 1) is smaller than i and has one fewer 1, so bits[i] is bits[i & (i - 1)] + 1, which fills the whole table in linear time."