Bit Hacks Catalog, in depth: lowest-bit tricks, SWAR popcount, De Bruijn, Gosper's hack and a test harness

Ground rules: width, signedness and preconditions

Fix the width. Every trick assumes 32 or 64 bits. Python integers are unbounded, so the Python versions here mask with M32 = (1 << 32) - 1 where C wraps silently; JavaScript bitwise operators use signed 32-bit.

Use unsigned arithmetic. In C, signed overflow is undefined behaviour and right-shifting a negative value is implementation-defined, so compute on unsigned types.

Respect preconditions. Many entries are undefined for zero; __builtin_ctz(0) is undefined in GCC and Clang, and shifting by the full width is undefined in C and masked on x86, so 1u << 32 is not zero there.

The lowest-set-bit family

Subtracting 1 flips the lowest set bit to 0 and every zero below it to 1. Two's-complement negation, ~x + 1, inverts every bit above the lowest set bit and keeps the rest. Those two facts generate the family:

Visiting every set bit then costs one iteration per set bit, not per position:

def set_bits(x):
    while x:
        low = x & -x
        yield low.bit_length() - 1    # index of the lowest set bit
        x &= x - 1                    # clear it

The Fenwick tree is built on x & -x: updates add the lowest set bit to the index, prefix queries subtract it.

Counting bits: SWAR popcount and parity

SWAR treats the word as many small counters and adds neighbours in parallel: sixteen 2-bit counts, eight 4-bit counts, four byte counts. Each field can hold its maximum, so no carry crosses into a neighbour.

M32 = (1 << 32) - 1

def popcount32(v):
    v = v - ((v >> 1) & 0x55555555)                    # 2-bit counts
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333)     # 4-bit counts
    v = (v + (v >> 4)) & 0x0F0F0F0F                    # byte counts
    return ((v * 0x01010101) & M32) >> 24              # sum of bytes lands in top byte

The first line works because a 2-bit field holding 2a + b minus its high bit a leaves a + b. The final multiply adds the four bytes into the top byte. Parity is the same idea with XOR: fold with v ^= v >> 16, then 8, 4, 2, 1, and read bit 0.

In practice, use the instruction: x86 POPCNT, ARM CNT, reached through C++20 std::popcount, __builtin_popcount, Rust count_ones or Java Integer.bitCount. A binary built for generic x86-64 may not emit POPCNT at all and falls back to code like the above, so check your flags.

Finding bit positions: De Bruijn and intrinsics

Counting trailing zeros has a portable answer. Isolate the lowest bit with x & -x and multiply by a De Bruijn constant, a 32-bit sequence whose 5-bit windows are all distinct; the top five bits of the product identify the shift, and a table maps them back. Build the table from the constant rather than copying one:

DB = 0x077CB531
CTZ_TABLE = [0] * 32
for i in range(32):
    CTZ_TABLE[((DB << i) & M32) >> 27] = i

def ctz32(v):                      # precondition: v != 0
    return CTZ_TABLE[(((v & -v) * DB) & M32) >> 27]

Hardware does this directly: x86 TZCNT and LZCNT, ARM CLZ (with RBIT for trailing zeros). C++20 std::countr_zero, std::countl_zero and std::bit_width are defined for zero, so they are the better default.

Rounding, averaging and branchless arithmetic

Round up to a power of two. Subtract one, smear the highest set bit into every lower position, then add one. Each shift doubles the run of ones, so five steps cover 32 bits:

def next_pow2_32(v):               # precondition: 0 < v <= 2**31
    v -= 1
    v |= v >> 1;  v |= v >> 2;  v |= v >> 4
    v |= v >> 8;  v |= v >> 16
    return v + 1                   # an exact power of two maps to itself

C++20 calls this std::bit_ceil.

Average without overflow. (a & b) + ((a ^ b) >> 1) counts shared bits fully and differing bits half, giving the floor average of unsigned values without the overflow in (a + b) / 2, the classic binary-search midpoint bug.

Branchless minimum. y ^ ((x ^ y) & -(x < y)) turns the comparison into an all-ones or all-zeros mask. Compilers already emit conditional moves for x < y ? x : y, so keep this for constant-time code such as cryptography.

Sign extension. For a b-bit field in the low bits of x, (x ^ m) - m with m = 1 << (b - 1) flips the sign bit, and the subtraction borrows through the upper bits exactly when it was set.

Rearranging bits: reversal and Morton codes

Bit reversal swaps adjacent bits, then pairs, nibbles, bytes and halves: five masked shift pairs for 32 bits, using the same 0x5555, 0x3333 and 0x0F0F masks as popcount. Morton (Z-order) codes interleave coordinate bits so points close in 2-D stay close in 1-D order, which is why spatial indexes and texture layouts use them:

def spread16(x):                   # bits 0..15 move to even positions 0, 2, ..., 30
    x = (x | (x << 8)) & 0x00FF00FF
    x = (x | (x << 4)) & 0x0F0F0F0F
    x = (x | (x << 2)) & 0x33333333
    return (x | (x << 1)) & 0x55555555

def morton2d(x, y):                # interleave two 16-bit coordinates
    return spread16(x) | (spread16(y) << 1)

Each step moves half of each group outward and masks off the copy. On x86 with BMI2, PDEP does the spread in one instruction, but it is slow on AMD processors before Zen 3, a reminder to measure before replacing a portable hack.

Combinations and subsets: Gosper's hack

Gosper's hack steps to the next larger integer with the same number of set bits. Iterate it from (1 << k) - 1 and you enumerate every k-element subset of n items in increasing numeric order, with no recursion:

def next_same_popcount(x):         # precondition: x > 0
    c = x & -x                     # lowest set bit
    r = x + c                      # carry ripples through the lowest run of ones
    return (((r ^ x) >> 2) // c) | r   # put the remaining ones back at the bottom

def k_subsets(n, k):
    x = (1 << k) - 1
    while x < (1 << n):
        yield x
        x = next_same_popcount(x)

def submasks(mask):                # every non-empty subset of mask, descending
    s = mask
    while s:
        yield s
        s = (s - 1) & mask

Adding c carries the lowest run of ones into the next zero; the XOR recovers that run, and dividing and shifting repacks the leftover ones at the bottom. For x = 0b0111: r is 0b1000, the XOR 0b1111, and the result 0b1011.

The submask loop drives subset dynamic programming: all submasks of all n-bit masks cost 3 to the n steps, not 4 to the n.

Byte-parallel tests: finding a zero byte

Word-at-a-time strlen implementations ask whether any byte is zero:

def has_zero_byte32(v):
    return ((v - 0x01010101) & ~v & 0x80808080) != 0

Subtracting 1 sets a byte's high bit if it was 0 or above 0x80; & ~v removes the second case. The yes-or-no answer is exact, but a borrow can flag the byte above a real zero, so find the first zero with a trailing-zero count, never the last. XOR the word with the byte broadcast first to search for any value; SIMD compares do the same over 16 to 64 bytes.

Worked example: a 64-slot bitmap allocator

A slab allocator tracks 64 fixed-size slots with one 64-bit word: bit i is 1 when slot i is in use. Allocation must find the lowest free slot, which is the lowest zero bit:

M64 = (1 << 64) - 1

def alloc(word):
    free = ~word & M64             # in C: ~word on a uint64_t
    if free == 0:
        return None, word          # slab full
    low = free & -free
    return low.bit_length() - 1, word | low

def release(word, slot):
    return word & ~(1 << slot) & M64

Trace it on the low byte. With word = 0b10110111, free ends 0b01001000, the lowest free bit is 0b00001000, so slot 3 is returned and the word becomes 0b10111111. The next call returns slot 6. No loop over slots.

In C++20 the lookup is std::countr_one(word), defined for every input and 64 when full. For many slabs, add a second-level word whose bit j says slab j has space: two lookups find a free slot among 4,096, the hierarchical idea behind Roaring bitmaps.

Verify every hack: an exhaustive harness

Bit hacks fail at the edges, so compare each against a slow, obvious reference over every 16-bit input plus random 32-bit ones:

import random
from itertools import combinations

def check(fn, ref, xs):
    for x in xs:
        assert fn(x) == ref(x), (fn.__name__, x)

xs = list(range(1, 1 << 16)) + [random.getrandbits(32) or 1 for _ in range(200_000)]
xs += [1 << i for i in range(32)] + [M32]
check(popcount32, lambda x: bin(x).count("1"), xs)
check(ctz32, lambda x: (x & -x).bit_length() - 1, xs)
check(next_pow2_32, lambda x: 1 << (x - 1).bit_length(), [x for x in xs if x <= 1 << 31])
check(has_zero_byte32, lambda x: 0 in x.to_bytes(4, "little"), xs)
for n in range(1, 11):
    for k in range(1, n + 1):
        want = sorted(sum(1 << i for i in s) for s in combinations(range(n), k))
        assert list(k_subsets(n, k)) == want
print("all bit hacks agree with their references")

Port the C versions into the same structure with a property-testing library, and run them under UBSan (-fsanitize=undefined), which catches shifts by the full width and signed overflow that a plain test run can pass by luck.

Failure modes

• Zero input. Lowest-bit, trailing-zero and logarithm hacks are undefined or wrong for 0. Guard the call or use the C++20 functions that define it.
• Signed types in C. Overflow in abs, averaging or a shifted 1 into the sign bit is undefined behaviour; the optimiser may remove the code that relied on it.
• Shift counts at or above the width. Undefined in C, masked on x86, so code that works on one target fails on another.
• Language width surprises. JavaScript truncates to signed 32-bit; Java has no unsigned types but provides >>>; Python never overflows, so a test in Python can hide a C overflow.
• Assuming the hack is faster. A loop the compiler recognises may already become one instruction, and a hack can block that. Read the assembly, then benchmark.

Trade-offs: hack, builtin or library

What to do next

1. Paste every function and the harness above into one file and run it; then break one mask constant and confirm the harness fails.
2. Rewrite the allocator in C with std::countr_one and compare the assembly with and without -mbmi or -march=native.
3. Benchmark SWAR popcount against the builtin on a 100-million-word array; check whether your build flags emit POPCNT.
4. Use Gosper's hack to enumerate 3-subsets of 20 items, and the submask loop to solve a small subset dynamic programming problem.
5. Read Gray codes for another family built from XOR and shifts, and apply the same reference-harness habit there.