Masks, Flags & Packed Fields

In short: a mask is a number whose bits mark the positions you care about. x | (1<<k) sets bit k, x & ~(1<<k) clears it, x ^ (1<<k) toggles it, and (x>>k) & 1 tests it. Shift a mask of w ones, (1<<w) - 1, to cover any run of bits and you can pack several fields side by side in one word: shift a value up by its field's position to pack it, shift and mask to unpack it. A field that's too wide for its lane spills silently into the lane next door, so a packer has to check widths, not just trust them.

Lesson 1 packed a Quarry record header into one 32-bit word with a line that looked like magic: (3071 << 20) | (17 << 14) | (2 << 11) | 1500. This lesson takes that line apart. It covers the four things you do to a single bit, then masks, the patterns of 1s that pick out several bits at once. Then it packs whole fields side by side in one word. Most binary formats you'll meet work this way: file headers, network packets, pixel formats, CPU instructions and database pages.

One bit at a time: set, clear, toggle, test

Build a word with a single 1 at position k with 1 << k, and combine it with the three operators from lesson 1:

Quarry's status word gives each flag a name, so no one has to remember which bit is which:

~DIRTY is negative in Python, because it has infinitely many 1s on the left. That's exactly what you want in a clear mask: every bit except bit 0 survives the AND, however wide status is.

❓ Cross-question — "Isn't there a library for this?" Yes. enum.IntFlag gives named flags that combine with | and print readably. Use it in application code. The operators underneath are the same ones shown here, and a storage engine that packs millions of headers uses them directly.

Precedence: where bit code goes wrong

Shifts bind more loosely than + and -, and &, ^, | bind more loosely still (in that order). Comparisons come after all of them. So x & 4 == 4 means (x & 4) == 4 in Python, unlike in C, where it means x & (4 == 4). But arithmetic can still surprise you:

Masks select many bits at once

A mask of w ones, (1 << w) - 1, selects the low w bits. Shift it to cover any field, meaning any run of adjacent bits. Quarry's header has four fields, packed from the top:

A field's shift is the number of bits below it. To pack a value, move it up by its shift and OR it in. To unpack, shift it back down and mask off everything above it. Step through packing record 2740 on shard 37, type 5, epoch 1234. Then watch what happens when someone stores a shard of 64 in a 6-bit field:

That last step is the bug that matters. Nothing crashed, and the word is still 32 bits, but it describes a different record. A packer has to either mask every value to its width or refuse values that don't fit. For a storage engine, refusing is the right answer. That's the task at the end of this lesson.

Order matters in unpacking. Mask after the shift, with the mask at the bottom, or mask before it with the mask shifted up. Mixing the two drops the field:

Changing one field in place

To overwrite a single field, clear its lane with an inverted mask, then OR in the new value. Every other field is left alone:

The trace moves the record to shard 12, and id 2740 and epoch 1234 come through unchanged. That's the reason for masks: you change one field without unpacking the rest.

Now pack a header with your own code and watch each field land in its lane. Change the values, or leave out the & mask and give the shard 64, and see the spill for yourself:

How wide should each field be?

The id and the epoch share 23 bits between them, and the shard and type take the other 9. Give the id w bits and the epoch gets 23 - w. A segment needs up to 4,000 distinct ids, and a record must survive 2,000 rewrites before its epoch wraps:

Only w = 12 meets both targets. One bit fewer and ids collide, one bit more and epochs wrap after 1,024 rewrites. A fixed-width layout is always a trade like this between fields.

Interview corner — two masks, one pass

You're given a list of status words and two masks. need holds the flags a record must have, and forbid holds the flags it must not have. Count the matching records. You need two ANDs per word and nothing else. "All of need" means w & need == need. It's a common mistake to test w & need != 0, which only checks for any of the flags. "None of forbid" means w & forbid == 0:

The query engine builds these two masks once per query, and then each record costs O(1) time — two machine instructions — to check, however many flags the query mentions, so scanning n records is O(n) time and O(1) extra space.

Coming from C: C gives you bit-fields in structs, struct { unsigned id:12; … }, but their layout is implementation-defined, so you can't trust them for data that goes to disk. Portable code uses shifts and masks, exactly as here.

Quick practice

🎯 Your turn

Write pack_fields(values, widths). The first field goes in the most significant bits and each later field sits below it. Return the packed integer, or None if any value is negative or doesn't fit its width. Quarry refuses to store a header it would corrupt.

• pack_fields([5, 3, 1], [4, 2, 1]) → 47 (1011 11 1)
• pack_fields([2740, 37, 5, 1234], [12, 6, 3, 11]) → 2873715922
• pack_fields([64], [6]) → None

Hint — loop over the fields in order, shifting the word left by each width and ORing the value in. That way the first field ends up on top without computing any shifts up front.

Then press ▶ Run, try the Live App chips, and hit ✓ Check. ✅