AND, OR, XOR & Shifts
In short: an integer is a row of bits, and four operators act on the whole row at
once: & keeps a bit only where both sides have it, | keeps a bit where either side
has it, ^ keeps a bit where the sides differ, and ~ flips every bit. << and >>
slide the whole row left or right, which multiplies or floor-divides by a power of two.
Python ints have no fixed width, so any trick that depends on a register's bits running
out (wraparound, overflow) needs an explicit mask.
Meet Quarry
For six sections you built Tunebox, a music app. From here the course builds something harder: Quarry, a search-and-storage engine. Think of the part of a database that nobody sees. It takes records in, stores them compactly, finds them again quickly and keeps them safe as they change. Over the coming sections Quarry gets a record encoder, a hash kernel, range analytics, a query planner, a text index and a diff engine. Each one is a real subsystem of a real engine, and each needs an algorithm you haven't met yet.
It starts at the bottom, with the record header. Every record Quarry stores carries four small facts: its id, the shard it lives on, its type, and the epoch (a version counter) it was written in. Held as a Python dict, that costs about two hundred bytes per record. Packed into a single 32-bit word, it costs four:
Across a hundred million records that is the difference between 20 GB and 400 MB. The
line that builds word uses two operators this lesson is about: << and |. By the
end of the section you'll have written the whole encoder yourself. You'll pack and
unpack the fields, check them, and index them with bitsets.
A number is a row of switches
An integer is stored in binary, one switch per power of two. Python shows you the
switches with bin or a format spec, and reads them back with int(text, 2):
Bit positions count from the right, starting at 0. Bit 0 is worth 1, bit 5 is worth 32, and 45 = 32 + 8 + 4 + 1. Everything below is about flipping, testing and moving those switches, many at once, in a single machine instruction.
Four operators that work on every bit at once
| Operator | Name | A result bit is 1 when… |
|---|---|---|
a & b |
AND | both bits are 1 |
a | b |
OR | at least one bit is 1 |
a ^ b |
XOR | exactly one bit is 1 (the bits differ) |
~a |
NOT | the bit was 0 |
The first three line two numbers up by bit position and decide each column on its own. No column affects another, so there are no carries like there are in addition. Step through the columns:
Each column is decided on its own. AND wants both bits, OR wants either, XOR wants exactly one.
Bit 7: x has 1 and y has 0. AND gives 0, OR gives 1, and XOR gives 1 because they differ. 5 by 8 table. 19 of 40 cells filled.
print(12 & 10, 12 | 10, 12 ^ 10)❓ Cross-question — "Aren't
and/orthe same as&/|?" No.andandortreat each whole value as one true or false and return one of the operands:12 and 10is10.&and|work on each of the bits separately. Mixing them up is a classic bug.if flags & DIRTYtests one bit, butif flags and DIRTYis true wheneverflagsis non-zero.
XOR undoes itself
XOR has a property the others don't: applying the same value twice cancels out.
a ^ b ^ b == a, because every bit of b flips the matching bit of a, then flips it
back. XOR is also commutative and associative, so the order of a long chain of XORs
doesn't matter. Put those facts together and pairs vanish:
Interview corner — the lost write
Quarry replicates every write, so its replication log should mention each record id exactly twice: once from the primary and once from the replica. One write was lost on one side, so its id appears only once. Find that id in one pass, O(n) time and O(1) extra memory. A set or a counter would also take O(n) time, but O(n) memory too.
XOR every id together. Each id that appears twice cancels itself out, and the one left standing is the lost write:
Look at the explanation, not the code. "Pairs cancel under XOR" is the fact that lets you solve the variants too, like the boss exercise below, where every id appears three times.
Shifts move the whole row
x << k slides every bit k places left and feeds zeros in on the right. That
multiplies by 2**k. x >> k slides right and drops the bits that fall off, which is
floor division by 2**k. Watch 13 shift left in an 8-bit register, the size of one
byte on a real machine:
A left shift doubles the number, until the top bit has nowhere left to go.
13 is 00001101. Bits 3, 2 and 0 are on, and 8 + 4 + 1 = 13. 8 cells. At index 4.
print(-9 >> 1, -9 // 2)Python has no fixed width, so you add it
A C uint8_t holds 8 bits, a Java int holds 32. A Python int holds as many as
it needs. That's why the last step above says 416 and the register says 160. It's
also why ~ looks strange in Python:
print(~5, ~5 & 0xFF)The fix is always the same: decide the width, and mask to it. A mask of w ones is
(1 << w) - 1. That's 0xFF for 8 bits and 0xFFFFFFFF for 32. x & mask keeps the
low w bits and throws the rest away. Quarry's headers are 32-bit words, so any
arithmetic on one that could spill past bit 31 gets masked back, just as the hardware
would. This helper was meant to model an 8-bit register, but it forgot:
It prints 104 416 4080. Python's << never loses a bit, so bits pushed past b7 are still there. Make shl8 behave like the register.
How wide does a field have to be? A w-bit field holds 2**w different values,
0 to 2**w - 1. Store anything bigger and it wraps. Only the low bits survive, so
the stored value is x % 2**w:
A Quarry segment holds up to 3,000 record ids. With 11 bits, id 2048 is stored as 0 and collides with the first record. Twelve bits hold 0 to 4,095 and cover them all. That's why the header gives the id 12 bits, and why a segment is capped at 4,096 records.
Counting the bits two words disagree on
XOR finds the differences between two words, and a loop that tests & 1 and shifts
right counts them. Step through it and watch diff lose one bit per pass:
Now read bits off the bottom yourself. This to_bits fills an 8-cell row from the
right. Each pass takes x & 1 (the lowest bit) and then shifts it away. Change 45 to
another number, or change the width, and watch your own loop fill the row:
Your loop reads the lowest bit with & 1 and shifts it away, so the row fills from b0 upward.
Coming from Java/JS: Java's
intis a 32-bit signed word, so1 << 31is negative there. It also has>>>, an unsigned right shift. JavaScript turns numbers into 32-bit integers for bitwise operators, so2**32 | 0is0. Python has neither problem and no>>>. Its ints never overflow, so you pick the width yourself with a mask.
Quick practice
print(6 ^ 6, 6 ^ 0)It wrongly prints "compressed". Bit 3 was never set. Fix the test.
🎯 Your turn
Every Quarry record has a status word where each bit is a flag: bit 0 means dirty (changed since the last flush), bit 1 means pinned in cache, bit 2 means deleted, and so on. When a write lands, the change log wants to know which flags it switched on and which it switched off.
Write changed_flags(old, new) returning {"set": [...], "cleared": [...]}. Each list
holds bit positions in increasing order.
changed_flags(0b0101, 0b0110)→{"set": [1], "cleared": [0]}changed_flags(9, 9)→{"set": [], "cleared": []}
Hint — old ^ new marks every bit that changed. Of those, the ones that are on in
new were set, and the ones on in old were cleared.
Then press ▶ Run, try the Live App chips, and hit ✓ Check. Green = the first piece of Quarry is built. ✅