Four elements: A, B, C, D. How many distinct subsets can you form?

Each element is either in the subset or out — two choices per element, four elements, so 2^4 = 16 possible subsets (including the empty set and the full set). Some are obvious: the empty set {}, the full set {A, B, C, D}, and all four singletons {A}, {B}, {C}, {D}. But the pairs and triples add up fast — there are six 2-element subsets and four 3-element subsets, and it's surprisingly easy to miss one when listing them by hand.

That's a small enough number to enumerate by hand, but large enough to feel tedious. Build a few subsets manually and add them to the grid below. Notice how quickly the collection grows — and how awkward it is to represent each subset as an array of strings.

Sixteen subsets from four elements. With five elements it's 32. With ten, it's 1,024. With twenty, over a million. The combinatorial explosion is real:

The clunky array-of-arrays representation will not scale. There has to be a more compact encoding.

Before we find the better way, feel the pain of the obvious approach. The natural representation for a subset is an array of its elements: ["A", "C"] for the subset containing A and C, ["B", "C", "D"] for B, C, D. To enumerate all subsets, you'd build an array of arrays — const subsets: string[][] = [[], ["A"], ["B"], ["A", "B"], ...] — with sixteen entries for just four elements.

The syntax cost is brutal. Each subset requires brackets, quotes around every element, and commas between them. The empty set is [] (2 characters), but a 3-element subset like ["A", "B", "C"] costs 14 characters. Watch the character count pile up as subset size grows:

Multiply that across sixteen subsets and you're well past 200 characters of boilerplate before you've written any logic. And this is only n = 4. For n = 10, you'd need 1,024 arrays. For n = 20, over a million. The array-of-arrays representation doesn't just scale poorly — it collapses under its own weight.

Add three subsets to the code panel below and extrapolate: how many characters would it take to enumerate all sixteen? The answer will motivate the compression trick that follows.

const subsets: string[][] = [

  // ... 16 more subsets

]

Over 250 characters for sixteen subsets of four elements. Imagine twenty elements — a million subsets, each stored as a string array. The memory cost alone is absurd. But each element has exactly two states (in or out), and you already know a data structure where each position has exactly two states: a binary number. What if each subset was just... an integer?

What if you could build a physical machine where each switch controls one element's membership? Flip switch A to ON and A is in the subset. Flip it OFF and A is out. Four switches, four elements — and the state of all four switches at any moment defines exactly one of the sixteen subsets.

That machine already exists — and you've been working with it since Module A. Four switches, each either ON or OFF, each position representing one element. The circuit below asks you to discover the mapping yourself: wire the switches to build specific subsets, and see what integer each configuration produces.

If the mapping is consistent, it means every bitwise operator you learned in Modules A through D has a second interpretation you haven't seen yet. But first, you need to find the encoding rule.

Wire the circuit below and discover how bits map to set membership.

The circuit makes the mapping physical: flip a switch, an element appears. The integer IS the set. And now the operators you learned in Module A gain a second interpretation: | adds an element (union), & keeps only shared elements (intersection), & ~mask removes an element (difference). Every set operation is a single bitwise expression on integers.

You've seen that | acts as union and & as intersection. But what about removing an element from a set? Or finding what's in one set but not another? These operations require compound expressions — two operators combined. The question is: which combinations, and why do they work?

The Venn diagram below highlights different regions of two overlapping sets. For each region, think about which bits you'd need to keep and which you'd need to eliminate — then figure out which operator combination achieves that.

Tap through the operations and try to predict the expression before it's revealed:

The circuit from the previous screen persists — same four elements, same switches. Build compound expressions that combine operators, predict the resulting set, then verify.

Three operations, three patterns. S & ~T is set difference — elements in S but not T. S ^ T is symmetric difference — elements in exactly one set. Q & ~P finds what Q has that P lacks. Each operation maps a set-theoretic concept to a single line of bit manipulation. The entire field of set algebra collapses into integer arithmetic.

The deepest insight is this: the integers 0 through 2^n - 1 enumerate every possible subset of n elements, by definition. 0 is the empty set (no bits ON). 1 is {A} (only bit 0). 2 is {B} (only bit 1). 15 is {A, B, C, D} (all four bits ON).

Think about why the math works. Each of n elements is independently either IN or OUT — that's 2 choices per element. Multiply across all elements and you get 2^n total combinations. An n-bit integer has exactly 2^n possible values (from 0 to 2^n - 1). The counting aligns perfectly: every integer in that range corresponds to exactly one subset, and every subset corresponds to exactly one integer. There are no gaps and no collisions.

That means a bare for (let i = 0; i < (1 << n); i++) loop visits every subset exactly once. No recursion, no backtracking, no missed combinations. The enumeration is free — just count:

Watch the full enumeration below, then see what happens when the element count scales.

One loop. One million subsets for n = 20. The bat-signal for bitmask enumeration in competitive programming is n <= 20 — small enough that 2^n fits comfortably in a 32-bit integer and the loop terminates in under a second. When n hits 25, you're at 33 million — still feasible. At 30, over a billion — borderline. The constraint n <= 20 is the green light. When you see it in a problem, the subset-as-integer encoding should be your first thought.

Every circuit operation you performed translates to a line of TypeScript: mask | (1 << k) to add element k, mask & ~(1 << k) to remove it, mask & (1 << k) to check membership, and (1 << n) - 1 for the full set. The enumeration loop is a bare for over the range 0..(1 << n). Connect each set operation to its code equivalent, then prove you own the mapping by filling in the critical expressions.

// Integer as Set — core operations

function addElement(mask: number, k: number) {

  return mask | (1 << k)     // add element k

}

function removeElement(mask: number, k: number) {

  return mask & ~(1 << k)    // remove element k

}

function hasElement(mask: number, k: number) {

  return (mask >> k) & 1     // check element k

}

const inter = A & B          // intersection

const union = A | B          // union

const diff  = A & ~B         // difference

const sym   = A ^ B          // symmetric diff

// enumerate all subsets of n elements

for (let i = 0; i < (1 << n); i++) {

  // i IS the subset

}

The complete bitmask toolkit in TypeScript. Add, remove, check, union, intersect, enumerate — each operation is a single expression. An integer IS a set, and integer arithmetic IS set algebra. This encoding appears in dynamic programming on subsets (dp[mask]), constraint satisfaction, game state representation, and hundreds of competitive programming problems where n <= 20.