Counting BitsCounting bits

01Why it exists

Reach for it when you see:Count the 1s, popcount, set bits, Hamming distance, how many bits differ, n & (n − 1), clear the lowest set bit, powers of two, the bit count of every value from 0 to n.

02The core idea

"How many bits of an integer are 1" is the population count (popcount, also called the Hamming weight). The most direct approach is to go bit by bit: add the lowest bit n & 1 to a counter, then n >>= 1, until n reaches 0. The loop runs once per bit of width, regardless of how many 1s are actually in there. Brian Kernighan's method stops only where the 1s are: each n &= n - 1 clears exactly the lowest set bit, so however many times it takes to reach 0 is however many 1s there were.

Why n & (n - 1) clears only the lowest set bit: say n's lowest 1 sits at bit j, so bits 0 through j − 1 are all 0. Subtracting 1 has to borrow, which turns bit j into 0 and bits 0 through j − 1 into 1s, while everything above bit j is untouched. AND that with the original n: bit j gives 1 & 0 = 0, the lower bits give 0 & 1 = 0, and the higher bits give x & x = x — precisely "n with its lowest 1 removed". The loop's invariant is that count + popcount(n) always equals the original number of 1s: each round adds 1 to count and takes one 1 away from n, so when n reaches 0, count is the answer. The same expression also tests for a power of two: n > 0 together with n & (n - 1) == 0 means n has exactly one 1 bit.

Let k be the number of 1s and w the bit width. Kernighan is O(k) and the bit-by-bit scan is O(bit length); both are O(w) in the worst case (identical when all 32 bits are 1), but the sparser the 1s, the more Kernighan saves. Both need only O(1) space. To count the 1s in every value from 0 to n (LeetCode 338), running Kernighan once per value costs O(n log n) in total; the recurrence bits[i] = bits[i & (i - 1)] + 1 does better, because i & (i - 1) is smaller than i, has exactly one 1 fewer, and was filled in long ago — the whole table is O(n), with no extra space beyond the answer array itself (bits[i >> 1] + (i & 1) has the same effect). The Hamming distance is popcount(a ^ b); to total the Hamming distance over every pair in an array, there is no need to compare all O(n²) pairs — work bit by bit instead: a position with c ones and n − c zeros contributes c × (n − c), for O(32n) altogether.

The most common trap is negative numbers. Python integers have no fixed width, so −1 behaves as though it had infinitely many 1s: n &= n - 1 just walks through −2, −4, −8 and never reaches 0, and the bit-by-bit n >>= 1 gets stuck at −1 too. Mask it into 32 bits first with n &= 0xFFFFFFFF. In C++, use std::uint32_t, because shifting a signed negative right normally fills with 1s and that loop will not stop either. In real code, reach for the built-ins: int.bit_count() from Python 3.10 onward, std::bitset<32>(n).count() in C++, GCC/Clang's __builtin_popcount, C++20's std::popcount — these usually compile straight down to the CPU's POPCNT instruction. The value of being able to write Kernighan yourself is the move underneath it, clearing the lowest set bit: (sub - 1) & mask in subset enumeration borrows the same way, while diff & -diff from XOR tricks and i & -i from a Fenwick tree are its siblings (they extract the lowest 1 rather than clearing it), and in bitmask DP, popcount(mask) is simply the size of the subset.

03The algorithm

1. 1Settle the width and the sign first: when the input can be negative, mask with n &= 0xFFFFFFFF in Python or switch to std::uint32_t in C++, or the loop will never end.
2. 2count = 0; while n != 0: n &= n - 1 (clear the lowest set bit), count += 1. When the loop ends, count is the number of 1s.
3. 3To find how many bits two numbers differ in (the Hamming distance), compute x = a ^ b and run step 2 on x.
4. 4For the answer for every value from 0 to n: allocate bits = [0] * (n + 1) and fill i from 1 to n with bits[i] = bits[i & (i - 1)] + 1, O(1) per cell.
5. 5For the total Hamming distance over every pair: at each bit position, count the c numbers that have a 1 there and add c × (n − c). Do not pair the numbers up.
6. 6In production code, call the built-in (bit_count(), __builtin_popcount, std::bitset::count); to test for a power of two write n > 0 and n & (n - 1) == 0, and remember the parentheses in C++.

04Interactive demo

n = 181 = 10110101₂, five 1s among eight bits. The first half is Brian Kernighan: each step stacks the three rows n, n − 1 and n & (n − 1), with yellow marking the position of the lowest set bit this round will clear, and green in the n − 1 row marking the bits below it that the borrow turned into 1s (181 is odd, so the first step shows no green yet). The second half is the bit-by-bit scan: in the "original n" row, the bit under inspection is green when it is 1 and yellow when it is 0, and bits already checked turn grey. The counter below always shows count and the number of iterations so far, and at the end the two totals are compared: 5 for Kernighan, 8 for the bit-by-bit scan.

05Code

The bit-by-bit version and Kernighan sit side by side for comparison, followed by two extensions: filling the whole table from 0 to n in O(n) with bits[i & (i - 1)] + 1 (LeetCode 338), and totalling the Hamming distance over every pair by counting per bit (LeetCode 477). The examples in main cover subnet masks, negative numbers and powers of two, and the built-in functions come at the end.

def popcount_naive(n):
    """Bit by bit: look at the lowest bit, then shift right. Iterations = the bit length"""
    n &= 0xFFFFFFFF                     # treat it as 32-bit unsigned, so negatives do not loop forever
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count


def popcount(n):
    """Brian Kernighan: clear the lowest set bit each time. Iterations = the number of 1s"""
    n &= 0xFFFFFFFF
    count = 0
    while n:
        n &= n - 1                      # clears the lowest set bit, higher bits untouched
        count += 1
    return count


def count_bits(n):
    """The number of 1s in every value from 0 to n (LeetCode 338). O(n)"""
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i & (i - 1)] + 1  # i & (i-1) is smaller and has one 1 fewer, so it is already filled in
        # another recurrence: bits[i] = bits[i >> 1] + (i & 1)
    return bits


def total_hamming_distance(nums):
    """Total Hamming distance over every pair (LeetCode 477). Count per bit, O(32n)"""
    n, total = len(nums), 0
    for b in range(32):
        ones = sum((x >> b) & 1 for x in nums)
        total += ones * (n - ones)      # on this bit, every 1 pairs with every 0
    return total


if __name__ == "__main__":
    print(popcount(181))                # 5 (10110101)
    print(popcount_naive(181))          # 5, but the loop ran 8 times
    print(popcount(0xFFFFFFC0))         # 26: the mask 255.255.255.192 is /26
    print(popcount(-1))                 # 32 (-1 is all 1s in 32-bit two's complement)
    print(popcount(1 ^ 4))              # 2: the Hamming distance between 1 and 4
    print(64 & 63 == 0)                 # True: a single 1 bit, so a power of two (in Python & binds tighter than ==)
    print(count_bits(8))                # [0, 1, 1, 2, 1, 2, 2, 3, 1]
    print(total_hamming_distance([4, 14, 2]))  # 6
    print((181).bit_count())            # 5 (built in since Python 3.10; before that, bin(181).count("1"))

06Practice

• LeetCode 191Number of 1 Bits (the archetypal Kernighan problem)Easy
• LeetCode 461Hamming Distance (XOR first, then count the 1s)Easy
• LeetCode 231Power of Two (n & (n − 1) == 0)Easy
• LeetCode 338Counting Bits (the O(n) recurrence)Easy
• LeetCode 477Total Hamming Distance (count per bit)Medium
• LeetCode 2429Minimize XOR (with the number of 1s fixed, greedily choose where they go)Medium