Counting bits

How many 1 bits does a number have? The count is called the population count, or popcount. It answers questions such as “how many items are in this subset?” and “in how many places do these two numbers differ?”. This lesson counts bits in four ways, from the plain loop to counting every number up to n at once.

Counting the 1 bits

The plain way looks at every place: add the last bit, shift it off, and repeat until nothing is left. That is one step per place, so O(B) for a number of B bits, even if it has only a few 1s.

def ones_plain(x):           # x >= 0
    count = 0
    while x:
        count += x & 1
        x >>= 1
    return count

def ones_drop(x):            # x >= 0
    count = 0
    while x:
        x &= x - 1           # drop the lowest 1 bit
        count += 1
    return count

The second version uses the method from lesson 3. x &= x - 1 removes one 1 bit each time, so the loop runs once per 1 bit, not once per place. This is often called Kernighan’s method. The first version of the figure steps through it.

In practice, call Python’s own method: x.bit_count() (Python 3.10 and later) counts in C, and most processors have a single instruction for it, called POPCNT. bin(x).count("1") also works and is fast. For a negative number, both count the 1s of its size, not of its endless two’s complement pattern: (-6).bit_count() is 2.

Counting in parallel

How do libraries and processors count without a loop? They count in many small groups at once. Take 180, 10 11 01 00, split into pairs of bits.

1. Count each pair. A pair ab holds the value 2a + b, and its count is a + b, so subtracting a gives the count. One subtraction does this for every pair at once: the pairs become 01 10 01 00, that is, counts 1, 2, 1, 0.
2. Add neighbouring pairs into fours. This gives 0011 0001: counts 3 and 1.
3. Add the two fours. This gives 4.

x = 0b10110100                # 180
m1, m2 = 0b01010101, 0b00110011
y = x - (x >> 1 & m1)         # 01 10 01 00
z = (y & m2) + (y >> 2 & m2)  # 0011 0001
(z + (z >> 4)) & 0b1111       # 4

Each step halves the number of groups, so a 64-bit word needs only 6 steps, with no loop over its bits. The masks 0x5555…, 0x3333… and 0x0F0F… in C popcount code come from exactly these steps. In Python, use bit_count(); this is how it can be done in a few machine steps.

Counts for every number

Sometimes you need the count for every number from 0 to n, for example to sort subsets by size. Each count can be built from a smaller one. i >> 1 is i with its last bit removed, and that last bit is i & 1:

Since i >> 1 is smaller than i, its count is already in the table when the loop reaches i. This is a small dynamic programming table (DYNP-3): one addition per number, O(n) in all. The second version of the figure fills it for 0 to 15. Another rule that works is ones[i] = ones[i & (i - 1)] + 1: drop the lowest 1 and add one.

The pattern in each place

What if n is as large as 10¹⁸ (a 1 followed by 18 zeros, a billion billion)? A table, or a count for each number, is far too slow. Look at one place at a time instead. Write 0, 1, 2, 3, … in binary, one under another, and read down a single place:

Place 0 goes 0, 1, 0, 1, …. Place 1 goes 0, 0, 1, 1, and repeats. Place 2 has four 0s, then four 1s. In general, place k repeats a cycle of 2ᵏ⁺¹ numbers: 2ᵏ zeros, then 2ᵏ ones. So the numbers 0 to n hold some whole cycles, each with exactly 2ᵏ ones in place k, plus part of one more cycle at the end. Counting place by place takes one step per place of n: O(log n) steps, about 60 for 10¹⁸, instead of 10¹⁸. BITS-P4 asks you to work out both parts.

A quick check: 0 to 2ᵏ − 1 is every pattern of k bits, and each place is 1 in exactly half of them. So together they have k · 2ᵏ⁻¹ ones. For k = 3 (0 to 7) that is 3 · 4 = 12.

Parity, distance and other counts

• Parity is whether the count of 1s is odd: x.bit_count() & 1. A parity bit added to stored or sent data catches any single flipped bit, because the flip changes the parity.
• Hamming distance is the number of places where two numbers differ: (x ^ y).bit_count(). It measures how far apart two codes are, and error-correcting codes keep their codes far apart.
• The length x.bit_length() is the position of the highest 1 plus one. For a power of 2, it gives the exact log₂: (1024).bit_length() - 1 is 10.
• 0s at the bottom (lesson 3): (x & -x).bit_length() - 1. This tells how many times 2 divides x.

Now try BITS-P4, All the 1 bits up to n.