Bit Tricks That Earn Their Keep
In short: subtracting 1 turns a number's trailing zeros into ones and clears its
lowest set bit, and that one fact powers a handful of O(1) one-liners: x & (x-1)
clears the lowest set bit, x & -x isolates it, and ~x & (x+1) isolates the lowest
zero bit instead. Clearing one set bit per pass (Kernighan's loop) counts the 1s in
O(popcount) time instead of O(width), which matters once a bitmap is mostly zeros.
Quarry stores records in fixed-size pages inside one big file, and it has to know which pages are free. Its answer is an allocation bitmap: one bit per page, 1 for used and 0 for free. A file with a million pages needs a bitmap of just 125 KB. But to allocate a page, Quarry has to find a 0 bit quickly, and to report usage it has to count the 1s. A loop over every bit can do both, but it's slow.
This lesson covers the handful of one-line tricks that make those questions cheap. Each works because of how subtracting 1, and negating in two's complement, change the lowest bits of a number. Once you see why, you won't need to memorise any of them.
What x - 1 does to the bits
Subtracting 1 borrows. Starting at bit 0, every trailing 0 becomes a 1 as the borrow passes through it, until the borrow reaches the lowest 1, which becomes 0. Above that, nothing changes:
x = 0 0 1 0 1 1 0 0 (44)
x - 1 = 0 0 1 0 1 0 1 1 (43)So x & (x - 1) keeps every bit above the lowest 1 and clears the lowest 1 and
everything below it. The net effect is that the lowest set bit is switched off.
print(40 & -40, 40 & 39)x & -x: the lowest set bit on its own
In two's complement, -x is ~x + 1. Flipping every bit turns the trailing 0s of x
into 1s, and adding 1 carries through all of them. The carry stops at the first 0 of
~x, which is exactly where x had its lowest 1. Above that, -x is still the
flipped x, so an AND with x gives 0 there. Only one bit survives. Step through it
for 44 in an 8-bit view:
Adding 1 to ~x carries through the flipped trailing zeros and stops at x's lowest 1, the only bit that x and -x share.
Flip every bit. x's two trailing 0s are now 1s, and its lowest 1, at bit 2, is now a 0. 4 by 8 table. 16 of 32 cells filled.
This trick is called lowbit. It's the engine of the Fenwick tree in the ranges
section, where i += i & -i hops from one node to the next.
A catalogue of one-liners
| Question | Expression | Cost |
|---|---|---|
| Lowest set bit, isolated | x & -x |
O(1) |
| Clear the lowest set bit | x & (x - 1) |
O(1) |
| Is x a power of two? | x > 0 and x & (x - 1) == 0 |
O(1) |
| Lowest zero bit, isolated | ~x & (x + 1) |
O(1) |
| Position of the highest set bit | x.bit_length() - 1 |
O(1) |
| Smallest power of two ≥ x (x ≥ 1) | 1 << (x - 1).bit_length() |
O(1) |
| Number of set bits | x.bit_count() (3.10+), or Kernighan's loop |
O(1) / O(set bits) |
The "lowest zero" line is the lowbit trick applied to ~x. Adding 1 to x carries
through its trailing 1s and stops at its lowest 0. Trace it on a bitmap where pages 0,
1, 2 and 4 are used:
Page 3 is the first free one, and finding it took no loop at all.
The power-of-two test looks simple, but it's easy to get wrong. This version accepts a number it shouldn't:
It prints [0, 1, 2, 4, 8, 16]. 0 has no set bit to clear, so x & (x - 1) is 0, and the test says yes.
Counting set bits: Kernighan's loop
Counting 1s by testing every position costs one pass per bit of width. Clearing the lowest set bit instead costs one pass per set bit, because each pass removes exactly one 1 and the loop stops when none are left:
x = 0b1011000
n = 0
while x:
x &= x - 1
n += 1
print(n)For a sparse bitmap, such as a mostly empty file where each 64-bit word has two or three
used pages, that's a 20× saving over testing all 64 positions. Python 3.10+ has
int.bit_count(), written in C, and you should use it in real code. But Kernighan's
loop is the one to know, because the same "clear the lowest bit" step drives the
subset loops in the next lesson.
Here is the loop with a picture. Each frame shows x just before its lowest set bit is
cleared, with the cursor on that bit. Change the starting value, or replace
x &= x - 1 with x >>= 1, and count how many frames each version takes:
Your popcount clears one set bit per pass, so the number of frames is the number of 1s, not the width.
How much does a bitmap save over keeping a list of free page numbers? A bitmap for
P pages costs P/8 bytes, however many pages are free. A free list costs 8 bytes per
free page. Suppose a file typically has 1,000 free pages, so its free list costs 8,000
bytes:
pages P |
bitmap bytes | free list bytes (1,000 free) |
|---|---|---|
| 8,000 | 1,000 | 8,000 |
| 64,000 | 8,000 | 8,000 |
| 200,000 | 25,000 | 8,000 |
They break even at 64,000 pages. The bitmap's cost is fixed, while the free list grows by 8 bytes per free page, so a bitmap wins whenever more than 1 page in 64 is free, which is almost always true in a live store. It also answers "is page k free?" in O(1), where a free list needs a scan.
Interview corner — two lost writes
Go back to lesson 1's replication log, where every id should appear twice. This time two different ids appear only once each. Find both in one pass with O(1) extra memory.
XORing everything gives a ^ b, not a and b separately. But a ^ b isn't zero,
because the two ids differ. Its lowbit marks a position where they differ: one has a 1
there and the other has a 0. Split every id by that bit, and XOR each half separately.
The pairs still cancel within each half, and a and b end up in different halves:
The general lesson is that when one XOR mixes two unknowns together, use a bit where they differ to separate them.
Quick practice
print(24 & -24, 24 & (24 - 1))It prints -1. ~bitmap & bitmap is always 0, since no bit can be both 0 and 1 at once. Fix the expression.
🎯 Your turn
Write claim_page(bitmap, pages). The file has pages pages, and bit i of bitmap is
1 when page i is used. Claim the lowest free page and return
[page, new_bitmap]. If every page is taken, return [-1, bitmap] unchanged.
claim_page(0b10111, 8)→[3, 0b11111], which is[3, 31]claim_page(0b1111, 4)→[-1, 15]
Hint — ~bitmap & (bitmap + 1) isolates the lowest 0 bit. Its position is
bit_length() - 1, and if that position is >= pages the file is full.
Then press ▶ Run, try the Live App chips, and hit ✓ Check. ✅