Representing Subsets as Integers - Bitmasks for Subset Representation | OneNoughtOne

0/361

Data Structures & AlgorithmsBitmasks for Subset Representation

Bitmasks for Subset Representation

LevelIntermediate

Duration55 mins

TopicBitmasks for Subset Representation

1 / 4

Representing Subsets as Integers

The Elegant Bridge: Sets Meet Binary

In the world of algorithms, few techniques offer such an elegant marriage of mathematical abstraction and computational efficiency as bitmask subset representation. This technique transforms the familiar concept of sets—fundamental to mathematics since Cantor's pioneering work in the 1870s—into compact integers that computers can manipulate with extraordinary speed.

Consider this profound insight: every subset of a set with n elements can be uniquely represented by an n-bit integer. This isn't merely a convenient encoding—it's a fundamental correspondence that unlocks O(1) set operations, makes subset iteration trivial, and enables entirely new classes of dynamic programming solutions.

What You Will Master

By the end of this page, you will understand: (1) the mathematical bijection between subsets and integers, (2) how individual set elements map to specific bit positions, (3) why this representation enables O(1) fundamental set operations, and (4) how bitmasks illuminate the connection between combinatorics and binary arithmetic.

The Subset-Integer Correspondence

Let's begin with the foundational insight that makes bitmask representation possible. Consider a universal set U containing exactly n elements, which we'll index from 0 to n-1:

U = {element₀, element₁, element₂, ..., elementₙ₋₁}

Now, for any subset S ⊆ U, we can define a characteristic function that maps each element to either 0 or 1:

χ_S(elementᵢ) = 1  if elementᵢ ∈ S
χ_S(elementᵢ) = 0  if elementᵢ ∉ S

This characteristic function produces a sequence of n binary digits (bits). Reading these bits as a binary number gives us a unique integer for each subset.

The profound implication: Since each bit independently chooses 'in' or 'out' for one element, there are exactly 2ⁿ possible combinations—matching the 2ⁿ possible subsets of an n-element set. This isn't coincidence; it's a mathematical bijection (one-to-one correspondence) between subsets and integers in the range [0, 2ⁿ - 1].

The Mathematical Bijection

A bijection means every subset maps to exactly one integer, and every integer (in range) maps to exactly one subset. This isn't just encoding—it's a perfect mathematical correspondence. The empty set ∅ maps to 0, the full set U maps to 2ⁿ - 1, and every integer between represents a unique subset.

Complete Subset-Integer Mapping for a 3-Element Set {a, b, c}
Integer	Binary	Subset	Set Notation
0	000	{}	∅ (empty set)
1	001	{a}	Element 0 only
2	010	{b}	Element 1 only
3	011	{a, b}	Elements 0 and 1
4	100	{c}	Element 2 only
5	101	{a, c}	Elements 0 and 2
6	110	{b, c}	Elements 1 and 2
7	111	{a, b, c}	Full set U

Observation from the table:

Integer 0 (000₂) represents the empty set—no bits are set, so no elements are included
Integer 7 (111₂) represents the full set—all bits are set, so all elements are included
Each power of 2 (1, 2, 4) represents a singleton set—exactly one bit is set
The binary representation directly encodes membership: bit i is 1 iff element i is in the subset

This mapping is consistent and computable in O(1): checking if element i is in subset S encoded as integer mask is simply (mask >> i) & 1, which tests whether bit i is set.

The Bit-Position Element Mapping

The power of bitmask representation stems from a crucial design decision: each bit position corresponds to exactly one element in our universal set. This isn't arbitrary—it enables constant-time operations.

Standard convention:

Bit 0 (the least significant bit, or LSB) → Element 0
Bit 1 → Element 1
Bit 2 → Element 2
...
Bit n-1 (the most significant bit in our n-bit representation) → Element n-1

This means the integer 1 << i (which equals 2ⁱ) represents the singleton set containing only element i. More generally, if element i should be included in the set, we 'set' bit i to 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Universal set with n elements indexed 0 to n-1
// Each element i is represented by bit position i
 
// The bitmask for element i alone (singleton set)
function singletonMask(i: number): number {
    // 1 << i creates a number with only bit i set
    // Examples:
    //   i=0: 1 << 0 = 0001₂ = 1
    //   i=1: 1 << 1 = 0010₂ = 2
    //   i=2: 1 << 2 = 0100₂ = 4
    //   i=3: 1 << 3 = 1000₂ = 8
    return 1 << i;
}
 
// Check if element i is in the subset represented by mask
function containsElement(mask: number, i: number): boolean {
    // (mask >> i) shifts bit i to position 0
    // & 1 isolates that single bit
    // Result is 1 (true) if element i is present, 0 (false) otherwise
    return ((mask >> i) & 1) === 1;
}
 
// Alternative: use AND with the singleton mask
function containsElementAlt(mask: number, i: number): boolean {
    // (1 << i) creates mask with only bit i set
    // AND with mask is non-zero iff mask also has bit i set
    return (mask & (1 << i)) !== 0;
}
 
// Example usage
const n = 4;  // Elements: {0, 1, 2, 3}
const mask = 0b1011;  // Binary: 1011 = Subset {0, 1, 3}
 
console.log(`Subset represented by ${mask} (binary: ${mask.toString(2)}):`);
for (let i = 0; i < n; i++) {
    if (containsElement(mask, i)) {
        console.log(`  Element ${i} is IN the subset`);
    } else {
        console.log(`  Element ${i} is NOT in the subset`);
    }
}
// Output:
//   Element 0 is IN the subset  (bit 0 = 1)
//   Element 1 is IN the subset  (bit 1 = 1)
//   Element 2 is NOT in the subset  (bit 2 = 0)
//   Element 3 is IN the subset  (bit 3 = 1)

Why LSB for Element 0?

Using the least significant bit for element 0 is conventional but not mandatory. The critical requirement is consistency: whichever mapping you choose, all operations must follow the same convention. LSB-first aligns naturally with how we read binary numbers and with the behavior of the shift operators.

Encoding and Decoding Subsets

Now that we understand the mapping, let's build complete encoding and decoding functions. Encoding converts a set (represented as an array of element indices) into an integer. Decoding recovers the set from the integer.

These operations are fundamental—they form the bridge between human-readable sets and machine-efficient integers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
 * Encode a subset (array of element indices) as an integer bitmask.
 * 
 * Time Complexity: O(|elements|) - linear in subset size
 * Space Complexity: O(1)
 */
function encodeSubset(elements: number[]): number {
    let mask = 0;
    
    for (const elementIndex of elements) {
        // Set the bit at position elementIndex
        // Using |= ensures we accumulate all elements
        mask |= (1 << elementIndex);
    }
    
    return mask;
}
 
/**
 * Decode an integer bitmask into a subset (array of element indices).
 * 
 * Time Complexity: O(n) where n is the number of bits to check
 * Space Complexity: O(|subset|) for the output array
 */
function decodeSubset(mask: number, n: number): number[] {
    const elements: number[] = [];
    
    for (let i = 0; i < n; i++) {
        // Check if element i is in the subset
        if ((mask >> i) & 1) {
            elements.push(i);
        }
    }
    
    return elements;
}
 
/**
 * Optimized decoding that only iterates while there are set bits.
 * Faster when the subset is small relative to n.
 * 
 * Time Complexity: O(|subset|) when subset is small
 */
function decodeSubsetOptimized(mask: number): number[] {
    const elements: number[] = [];
    let bitPosition = 0;
    
    while (mask > 0) {
        // Check if current LSB is set
        if (mask & 1) {
            elements.push(bitPosition);
        }
        // Shift right to examine next bit
        mask >>= 1;
        bitPosition++;
    }
    
    return elements;
}
 
// Demonstration
console.log("=== Encoding Examples ===");
console.log(`{0, 2, 3} encoded: ${encodeSubset([0, 2, 3])}`);  // 13 (1101₂)
console.log(`{1, 4} encoded: ${encodeSubset([1, 4])}`);        // 18 (10010₂)
console.log(`{} (empty) encoded: ${encodeSubset([])}`);         // 0
console.log(`{0} encoded: ${encodeSubset([0])}`);               // 1
 
console.log("
=== Decoding Examples ===");
console.log(`13 decoded (n=4): [${decodeSubset(13, 4)}]`);      // [0, 2, 3]
console.log(`18 decoded (n=5): [${decodeSubset(18, 5)}]`);      // [1, 4]
console.log(`0 decoded (n=3): [${decodeSubset(0, 3)}]`);        // []
console.log(`7 decoded (n=3): [${decodeSubset(7, 3)}]`);        // [0, 1, 2]
 
console.log("
=== Optimized Decoding ===");
console.log(`13 decoded (optimized): [${decodeSubsetOptimized(13)}]`);  // [0, 2, 3]

Key insights from the implementation:

Encoding is additive: Each element contributes its bit independently. The order of processing doesn't matter because bitwise OR is commutative.
Decoding can be optimized: The standard approach checks all n bit positions. The optimized version stops when no more set bits remain, which is faster when subsets are sparse.
Round-trip consistency: For any valid subset, decodeSubset(encodeSubset(elements)) returns a sorted version of the original elements.

Why Bitmasks Enable O(1) Set Operations

Here's where bitmask representation reveals its true power. Operations that would require O(n) time with traditional set representations (arrays, linked lists, or even hash sets for some operations) become O(1) with bitmasks.

The magic lies in how CPUs handle bitwise operations. Modern processors include specialized circuitry that can perform operations like AND, OR, and XOR on 32 or 64 bits in a single clock cycle. When we represent sets as integers, set operations map directly to these hardware primitives.

Set Operations: Bitmask vs Traditional Implementations
Operation	Bitmask Impl	Array Impl	Hash Set Impl
Union (A ∪ B)	A \| B → O(1)	O(m + n) merge	O(m) iterate & insert
Intersection (A ∩ B)	A & B → O(1)	O(m + n) or O(m × n)	O(m) lookup each
Difference (A - B)	(A) & (~B) → O(1)	O(m + n)	O(m) check & remove
Symmetric Diff	A ^ B → O(1)	O(m + n)	O(m + n)
Subset test (A ⊆ B)	(A & B) == A → O(1)	O(m) check each	O(m) check each
Cardinality \|A\|	popcount(A) → O(1)*	O(1) with length	O(1) with size
Element test (x ∈ A)	(A >> x) & 1 → O(1)	O(n) search	O(1) hash lookup

Hardware-Level Efficiency

Modern CPUs provide the POPCNT instruction that counts set bits in O(1). In JavaScript/TypeScript, this is available through library functions. The key insight is that bitmask operations leverage transistor-level parallelism—all 32 or 64 bit operations happen simultaneously, not sequentially.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Prerequisite: Sets A and B are encoded as bitmasks
 
// UNION: Elements in A OR B
function union(a: number, b: number): number {
    return a | b;
    // Each bit is 1 if it's 1 in A or B (or both)
    // Example: A={0,1}, B={1,2} → 0011 | 0110 = 0111 = {0,1,2}
}
 
// INTERSECTION: Elements in BOTH A AND B
function intersection(a: number, b: number): number {
    return a & b;
    // Each bit is 1 only if it's 1 in both A and B
    // Example: A={0,1}, B={1,2} → 0011 & 0110 = 0010 = {1}
}
 
// DIFFERENCE: Elements in A but NOT in B
function difference(a: number, b: number): number {
    return a & ~b;
    // ~b flips all bits of B (complement)
    // AND with A keeps only bits in A that aren't in B
    // Example: A={0,1,2}, B={1} → 0111 & 1101 = 0101 = {0,2}
}
 
// SYMMETRIC DIFFERENCE: Elements in A or B but NOT both
function symmetricDifference(a: number, b: number): number {
    return a ^ b;
    // XOR produces 1 where exactly one input is 1
    // Example: A={0,1}, B={1,2} → 0011 ^ 0110 = 0101 = {0,2}
}
 
// SUBSET TEST: Is A a subset of B?
function isSubset(a: number, b: number): boolean {
    return (a & b) === a;
    // If every element in A is also in B, then A & B = A
    // Alternatively: (a & ~b) === 0 (nothing in A outside B)
}
 
// PROPER SUBSET TEST: Is A a proper subset of B?
function isProperSubset(a: number, b: number): boolean {
    return (a & b) === a && a !== b;
    // Subset, but not equal
}
 
// EQUALITY TEST: Are A and B the same set?
function setsEqual(a: number, b: number): boolean {
    return a === b;
    // Direct integer comparison!
}
 
// CARDINALITY: Count elements in set
function cardinality(mask: number): number {
    // Brian Kernighan's algorithm - O(number of set bits)
    let count = 0;
    while (mask) {
        mask &= (mask - 1);  // Clear rightmost set bit
        count++;
    }
    return count;
}
 
// For truly O(1), use built-in popcount when available
// In JavaScript: no native popcount, but this works:
function cardinalityFast(mask: number): number {
    // Divide and conquer bit counting
    mask = mask - ((mask >>> 1) & 0x55555555);
    mask = (mask & 0x33333333) + ((mask >>> 2) & 0x33333333);
    mask = (mask + (mask >>> 4)) & 0x0f0f0f0f;
    mask = mask + (mask >>> 8);
    mask = mask + (mask >>> 16);
    return mask & 0x3f;
}
 
// Demonstration
const setA = 0b1011;  // {0, 1, 3}
const setB = 0b1110;  // {1, 2, 3}
 
console.log("A = {0, 1, 3}, B = {1, 2, 3}");
console.log(`Union A ∪ B: ${union(setA, setB).toString(2)} = {0,1,2,3}`);
console.log(`Intersection A ∩ B: ${intersection(setA, setB).toString(2)} = {1,3}`);
console.log(`Difference A - B: ${difference(setA, setB).toString(2)} = {0}`);
console.log(`Symmetric diff A △ B: ${symmetricDifference(setA, setB).toString(2)} = {0,2}`);
console.log(`Is A ⊆ B? ${isSubset(setA, setB)}`);  // false
console.log(`|A| = ${cardinality(setA)}`);  // 3

The Power of Two Connection

The relationship between subsets and powers of two reveals deep mathematical structure. This isn't just convenient—it's a window into combinatorics itself.

Why exactly 2ⁿ subsets?

For each element in an n-element set, we have exactly two choices: include it or exclude it. These choices are independent. By the multiplication principle:

2 × 2 × 2 × ... × 2 (n times) = 2ⁿ possible subsets

This is precisely the range of n-bit integers [0, 2ⁿ - 1].

Elegant Correspondences

•Empty set ↔ 0: No elements selected, no bits set. The additive identity in both domains.
•Full set ↔ 2ⁿ - 1: All elements selected, all bits set. This value is always all 1s in binary.
•Singleton {i} ↔ 2ⁱ: Exactly one element selected, exactly one bit set. Powers of two are singletons.
•Complement ↔ XOR with (2ⁿ - 1): The complement of A is (2ⁿ - 1) ^ A, flipping all n bits.
•Subset count ↔ Integer range: k-element subsets correspond to k-bit set integers, counted by C(n,k).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const n = 4;  // 4-element universal set {0, 1, 2, 3}
 
// The full set: all bits set
const fullSet = (1 << n) - 1;  // 2⁴ - 1 = 15 = 1111₂
console.log(`Full set (all ${n} elements): ${fullSet} = ${fullSet.toString(2)}`);
 
// The empty set: no bits set
const emptySet = 0;
console.log(`Empty set: ${emptySet}`);
 
// All singleton sets
console.log("
Singleton sets (powers of 2):");
for (let i = 0; i < n; i++) {
    const singleton = 1 << i;
    console.log(`  {${i}} = ${singleton} = 2^${i}`);
}
 
// Complement of a set
function complement(mask: number, n: number): number {
    const fullSet = (1 << n) - 1;
    return fullSet ^ mask;  // XOR with all 1s flips all bits
}
 
const setA = 0b1010;  // {1, 3}
const complementA = complement(setA, n);
console.log(`
Set A: ${setA.toString(2).padStart(4, '0')} = {1, 3}`);
console.log(`Complement of A: ${complementA.toString(2).padStart(4, '0')} = {0, 2}`);
 
// Verify: A ∪ complement(A) = full set
console.log(`A ∪ A' = ${(setA | complementA).toString(2)} = full set? ${(setA | complementA) === fullSet}`);
 
// Verify: A ∩ complement(A) = empty set
console.log(`A ∩ A' = ${setA & complementA} = empty set? ${(setA & complementA) === emptySet}`);

The Maximum Set Size Constraint

Standard 32-bit integers limit us to sets of at most 32 elements. With 64-bit integers (BigInt in JavaScript), we can handle 64 elements. For larger sets, we'd need arrays of integers (bit vectors), but most algorithmic applications involve small sets where bitmasks excel.

Practical Examples: Bitmasks in Action

Let's solidify understanding with practical examples that demonstrate why engineers reach for bitmasks in real systems.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// Define features as bit positions
const FEATURE_DARK_MODE = 0;      // bit 0 = 1
const FEATURE_BETA_UI = 1;        // bit 1 = 2
const FEATURE_ANALYTICS = 2;      // bit 2 = 4
const FEATURE_AI_ASSIST = 3;      // bit 3 = 8
const FEATURE_EXPORT_PDF = 4;     // bit 4 = 16
 
// Create feature masks
const DARK_MODE = 1 << FEATURE_DARK_MODE;      // 0b00001 = 1
const BETA_UI = 1 << FEATURE_BETA_UI;          // 0b00010 = 2
const ANALYTICS = 1 << FEATURE_ANALYTICS;      // 0b00100 = 4
const AI_ASSIST = 1 << FEATURE_AI_ASSIST;      // 0b01000 = 8
const EXPORT_PDF = 1 << FEATURE_EXPORT_PDF;    // 0b10000 = 16
 
// USER FEATURE FLAGS STORED AS SINGLE INTEGER
// Instead of: { darkMode: true, betaUI: false, analytics: true, ... }
// We use:
let userFeatures = 0;
 
// Enable features for a user
userFeatures |= DARK_MODE;    // Turn on dark mode
userFeatures |= ANALYTICS;    // Turn on analytics
// Now userFeatures = 0b00101 = 5
 
// Check if user has a feature (O(1) operation)
function hasFeature(flags: number, feature: number): boolean {
    return (flags & feature) !== 0;
}
 
console.log(`Has dark mode? ${hasFeature(userFeatures, DARK_MODE)}`);  // true
console.log(`Has beta UI? ${hasFeature(userFeatures, BETA_UI)}`);      // false
console.log(`Has analytics? ${hasFeature(userFeatures, ANALYTICS)}`);  // true
 
// Toggle a feature
userFeatures ^= BETA_UI;  // Now beta UI is on
console.log(`After toggle, has beta UI? ${hasFeature(userFeatures, BETA_UI)}`);  // true
 
// Define feature tiers as combinations
const FREE_TIER = DARK_MODE | ANALYTICS;           // 0b00101 = 5
const PRO_TIER = FREE_TIER | AI_ASSIST | BETA_UI;  // 0b01111 = 15
const ENTERPRISE = PRO_TIER | EXPORT_PDF;          // 0b11111 = 31
 
// Check if user has all features of a tier
function hasTier(userFlags: number, tierFlags: number): boolean {
    return (userFlags & tierFlags) === tierFlags;
}
 
const proUser = PRO_TIER;
console.log(`Pro user has free tier features? ${hasTier(proUser, FREE_TIER)}`);  // true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// Unix-style file permissions as bitmasks
const READ    = 4;   // 0b100
const WRITE   = 2;   // 0b010
const EXECUTE = 1;   // 0b001
 
// Common permission combinations
const READ_WRITE = READ | WRITE;           // 6 = 0b110
const READ_EXECUTE = READ | EXECUTE;       // 5 = 0b101
const ALL_PERMISSIONS = READ | WRITE | EXECUTE;  // 7 = 0b111
 
// Represent user/group/other as three 3-bit fields
// Format: [user:3][group:3][other:3]
function makePermissions(user: number, group: number, other: number): number {
    return (user << 6) | (group << 3) | other;
}
 
// Common file permission patterns
const FILE_755 = makePermissions(ALL_PERMISSIONS, READ_EXECUTE, READ_EXECUTE);
const FILE_644 = makePermissions(READ_WRITE, READ, READ);
const FILE_600 = makePermissions(READ_WRITE, 0, 0);
 
function permissionString(perm: number): string {
    const chars = [
        (perm & 4) ? 'r' : '-',
        (perm & 2) ? 'w' : '-',
        (perm & 1) ? 'x' : '-',
    ];
    return chars.join('');
}
 
function fullPermissionString(perms: number): string {
    const user = (perms >> 6) & 0b111;
    const group = (perms >> 3) & 0b111;
    const other = perms & 0b111;
    return permissionString(user) + permissionString(group) + permissionString(other);
}
 
console.log(`chmod 755: ${fullPermissionString(FILE_755)}`);  // rwxr-xr-x
console.log(`chmod 644: ${fullPermissionString(FILE_644)}`);  // rw-r--r--
console.log(`chmod 600: ${fullPermissionString(FILE_600)}`);  // rw-------
 
// Check access in O(1)
function canUserWrite(perms: number): boolean {
    const userPerms = (perms >> 6) & 0b111;
    return (userPerms & WRITE) !== 0;
}
 
function canOthersRead(perms: number): boolean {
    const otherPerms = perms & 0b111;
    return (otherPerms & READ) !== 0;
}

Database Efficiency

Storing feature flags as a single integer column instead of multiple boolean columns saves space and enables efficient querying. A query like 'SELECT * FROM users WHERE (features & required_features) = required_features' checks multiple flags in one operation.

Visualizing the Subset Lattice

The subsets of a set form a beautiful mathematical structure called a lattice under the subset relation. This lattice has a direct correspondence to integer ordering and bit patterns.

Consider the power set of {a, b, c}. If we draw edges between sets where one is a subset of another (differing by exactly one element), we get a structure that reveals deep patterns:

                    {a,b,c} = 7 = 111₂
                   /    |    \
             {a,b}     {a,c}    {b,c}
              =6       =5        =3
             110₂     101₂      011₂
            /   \    /   \    /   \
         {a}     {b}      {c}
          =1      =2       =4
         001₂   010₂     100₂
            \    |    /
               {}
              = 0
             000₂
 
Key observations:
- The empty set (0) is at the bottom - subset of everything
- The full set (7) is at the top - superset of everything
- Moving UP adds one element (sets one bit)
- Moving DOWN removes one element (clears one bit)
- Each level contains C(3,k) subsets of size k
  - Level 0: C(3,0) = 1 subset  (the empty set)
  - Level 1: C(3,1) = 3 subsets (singletons)
  - Level 2: C(3,2) = 3 subsets (pairs)
  - Level 3: C(3,3) = 1 subset  (the full set)
- Total: 1 + 3 + 3 + 1 = 8 = 2³ subsets

The lattice and bitmask operations:

Union of two sets is their least upper bound in the lattice
Intersection is their greatest lower bound
Subset ordering A ⊆ B means there's a path up from A to B
Popcount gives the level in the lattice (number of elements)

This structure is called a Boolean lattice or power set lattice. It appears throughout computer science—in logic, database query optimization, and formal verification. Understanding it deepens your grasp of why bitmask operations work as they do.

Summary: The Foundation Established

We've established the foundational understanding of bitmask subset representation. Let's consolidate what we've learned:

Key Takeaways

•Subset-Integer Bijection: Every subset of an n-element set corresponds uniquely to an integer from 0 to 2ⁿ-1. This is a mathematical bijection, not just a convenient encoding.
•Bit-Position Mapping: Element i is represented by bit i. The singleton {i} corresponds to 2ⁱ. Membership testing is O(1) via bit extraction.
•O(1) Set Operations: Union → OR, Intersection → AND, Difference → AND NOT, Symmetric Difference → XOR. These leverage CPU hardware for massive speedup.
•Space Efficiency: A 32-element set fits in a single 32-bit integer. This is far more compact than arrays or hash sets.
•Power of Two Structure: The 2ⁿ subsets correspond to the 2ⁿ integers. Powers of two are singletons. All 1s is the full set.
•Practical Applications: Feature flags, permissions, state tracking—anywhere sets need fast operations and compact storage.

What's next:

Now that we can represent subsets as integers, the next natural question is: how do we iterate through all subsets? Whether we need to enumerate all 2ⁿ subsets, iterate through subsets of a given set, or find subsets of a particular size, bitmasks provide elegant solutions. The next page explores these iteration patterns—essential techniques for brute-force algorithms and the foundation of bitmask dynamic programming.

Foundation Complete

You now understand how bitmasks elegantly represent subsets as integers, enabling O(1) set operations and compact storage. This mathematical correspondence between sets and binary numbers is the foundation for all bitmask techniques. Next, we'll explore how to systematically iterate through these subset representations.