Sets and Bitmasks — Brief ☧
Deep version → | Lab → | Back to Big-O →
Q: The twelve sons of Jacob: Reuben, Simeon, Levi, Judah, Dan,
Naphtali, Gad, Asher, Issachar, Zebulun, Joseph, Benjamin.
Imagine a roll call at a gathering of the tribes. How would you
record who showed up?
A: You could write a list of names — but a list takes time to
search. Instead, picture twelve oil lamps in a row, one for each son.
Light the lamp for every son who is present. A lit lamp means "here,"
an unlit lamp means "absent."
Q: So each lamp is either on or off — a simple yes or no?
A: Exactly. In computer terms, each lamp is a single bit — a
boolean value, 1 (present) or
0 (absent). Line up twelve of these bits and you have a
bitmask: one compact number that
represents the entire gathering.
Give each son a position (0 through 11). Bit N is 1 if son N is
present, 0 if absent:
All present: 111111111111 (= 4095) Only Judah (3): 000000001000 (= 8) Only Joseph (10) and Benjamin (11): 110000000000 (= 3072)Q: Now two messengers arrive. One says "Reuben, Levi, and Judah
are in the north camp." Another says "Levi, Judah, and Dan are
in the east camp." How do we figure out who is in both camps?
A: Think of it this way: hold the two rows of lamps side by side.
Wherever both lamps are lit, that son is in both camps. In
computer terms, this is the bitwise AND operation — it keeps only the
positions where both bitmasks have a 1:
North: 000000001101 (Reuben=0, Levi=2, Judah=3) East: 000000011100 (Levi=2, Judah=3, Dan=4) AND: 000000001100 (Levi=2, Judah=3)Levi and Judah are in both camps. And here is the remarkable part: the
computer performs this entire calculation in a single instruction —
O(1). It does not matter
whether there are 12 sons or 12,000; the hardware compares all the
bits simultaneously. Compare that to the alternative: writing out two
lists of names and scanning one against the other, checking each name
individually. That would take time proportional to the size of the
lists. The bitmask approach collapses all of that work into one
instantaneous operation.
Q: What about finding everyone who is in either camp? Or
everyone who is not in a camp?
A: Those are the OR and NOT operations. OR lights a lamp if
either input has it lit (union). NOT flips every lamp — lit becomes
unlit and vice versa (complement). These operations are just as fast:
one instruction each. That's what makes bitmasks so powerful — all
the basic set operations happen in
The Key Operations
| Operation | Meaning | Bit Operation | Example | |
|---|---|---|---|---|
| Intersection | "Who is in both?" | AND | 1101 & 1110 = 1100 | |
| Union | "Who is in either?" | OR | `1101 \ | 1110 = 1111` |
| Complement | "Who is NOT here?" | NOT | ~1101 = 0010 | |
| Empty check | "Is anyone here?" | == 0 | 0000 == 0 → empty | |
| Count | "How many?" | popcount | popcount(1101) = 3 |
The table above is worth internalizing, because these five operations are the vocabulary for everything that follows. Intersection (AND) is by far the most important — it is how constraints narrow down possibilities. When two pieces of evidence agree on some values and disagree on others, AND keeps only the agreement. Union (OR) is how we combine alternatives. And the empty check is how we detect failure: if no bits survive an AND, the constraints are contradictory and there is no valid answer.
Notice that every one of these operations takes the same amount of time regardless of how many bits are involved. This is unusual and powerful. Most data operations get slower as the data grows, but bitmask operations stay constant — which is why they are the foundation of our hardware design.
This is the foundation of your entire system. Every domain is a bitmask.
Every constraint is an AND. Every failure is an empty bitmask.
Now that you have a feel for how sets map to bits and how set operations map to single instructions, the deep version will show you how to scale this idea beyond 64 bits, how the FPGA pipelines these operations, and how bitmask intersection is the engine behind constraint propagation.
Learn more in the deep version
Related: Big-O Notation | Hash Tables
Domains Unification
Soli Deo Gloria