Bitmasks For Subset Representation - Learning Module

Loading content...

0/279

Subset Operations with Bitwise Ops

Set Theory Meets Hardware Efficiency

Set theory provides a rigorous mathematical framework for reasoning about collections of elements. When we encode sets as bitmasks, we unlock something remarkable: every fundamental set operation maps directly to a hardware-level bitwise instruction. Operations that might require loops with traditional set implementations execute in a single CPU cycle with bitmasks.

This page is a comprehensive reference for bitmask set operations. We'll cover not just the basics (union, intersection, difference), but also advanced operations (symmetric difference, subset testing, superset enumeration) and specialized techniques (lowest/highest element extraction, element counting). By the end, you'll have a complete toolkit for manipulating sets at the speed of silicon.

What You Will Master

By the end of this page, you will command: (1) all fundamental set operations via bitwise operators, (2) subset and superset testing in O(1), (3) element extraction and counting techniques, (4) set modification operations, and (5) the mathematical correspondence between set theory and Boolean algebra.

The Fundamental Trio: Union, Intersection, Difference

Three operations form the core of set algebra: union (∪), intersection (∩), and set difference (−). Each maps directly to a bitwise operator.

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
/**
 * UNION: A ∪ B
 * Contains all elements that are in A, in B, or in both.
 * Bitwise: OR (|)
 * 
 * For each bit position (element):
 *   result[i] = 1 if A[i] = 1 OR B[i] = 1
 */
function union(A: number, B: number): number {
    return A | B;
}
 
/**
 * INTERSECTION: A ∩ B
 * Contains only elements that are in BOTH A and B.
 * Bitwise: AND (&)
 * 
 * For each bit position:
 *   result[i] = 1 only if A[i] = 1 AND B[i] = 1
 */
function intersection(A: number, B: number): number {
    return A & B;
}
 
/**
 * SET DIFFERENCE: A - B (also written A \ B)
 * Contains elements in A that are NOT in B.
 * Bitwise: A AND (NOT B)
 * 
 * For each bit position:
 *   result[i] = 1 if A[i] = 1 AND B[i] = 0
 */
function difference(A: number, B: number): number {
    return A & ~B;
}
 
// Demonstration with sets A = {0, 1, 3} and B = {1, 2, 3}
const A = 0b1011;  // {0, 1, 3}
const B = 0b1110;  // {1, 2, 3}
 
function setToString(mask: number, n: number = 4): string {
    const elements: number[] = [];
    for (let i = 0; i < n; i++) {
        if ((mask >> i) & 1) elements.push(i);
    }
    return `{${elements.join(', ')}}`;
}
 
console.log(`A = ${setToString(A)}`);                           // {0, 1, 3}
console.log(`B = ${setToString(B)}`);                           // {1, 2, 3}
console.log(`A ∪ B = ${setToString(union(A, B))}`);             // {0, 1, 2, 3}
console.log(`A ∩ B = ${setToString(intersection(A, B))}`);      // {1, 3}
console.log(`A - B = ${setToString(difference(A, B))}`);        // {0}
console.log(`B - A = ${setToString(difference(B, A))}`);        // {2}
 
// Verify classical set identities
console.log("
Set Identities:");
const empty = 0;
const universal = 0b1111;  // 4-element universe
 
// A ∪ ∅ = A
console.log(`A ∪ ∅ = A? ${union(A, empty) === A}`);
 
// A ∩ U = A (where U is universal set)
console.log(`A ∩ U = A? ${intersection(A, universal) === A}`);
 
// A - A = ∅
console.log(`A - A = ∅? ${difference(A, A) === 0}`);
 
// A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (distributive law)
const C = 0b0101;  // {0, 2}
const lhs = union(A, intersection(B, C));
const rhs = intersection(union(A, B), union(A, C));
console.log(`Distributive law holds? ${lhs === rhs}`);

Boolean Algebra Correspondence

Set theory and Boolean algebra are isomorphic. Union = OR, Intersection = AND, Complement = NOT, Universal set = all 1s, Empty set = all 0s. Every theorem from Boolean algebra translates directly to set theory and vice versa. De Morgan's laws, distributive laws, absorption laws—all apply.

Symmetric Difference: The Power of XOR

The symmetric difference (A △ B or A ⊕ B) contains elements that are in exactly one of the two sets—but not both. This maps to the XOR operator, which has remarkable properties.

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
/**
 * SYMMETRIC DIFFERENCE: A △ B
 * Contains elements in A or B but NOT both.
 * Equivalent to: (A - B) ∪ (B - A)
 * Also equivalent to: (A ∪ B) - (A ∩ B)
 * Bitwise: XOR (^)
 */
function symmetricDifference(A: number, B: number): number {
    return A ^ B;
}
 
// Visualization: XOR truth table applied to sets
console.log("XOR for sets:");
console.log("A[i]  B[i]  Result");
console.log("  0     0      0   (neither has element → excluded)");
console.log("  0     1      1   (only B has element → included)");
console.log("  1     0      1   (only A has element → included)");
console.log("  1     1      0   (both have element → excluded)");
 
const A = 0b1011;  // {0, 1, 3}
const B = 0b1110;  // {1, 2, 3}
 
function setToString(mask: number, n: number = 4): string {
    const elements: number[] = [];
    for (let i = 0; i < n; i++) {
        if ((mask >> i) & 1) elements.push(i);
    }
    return `{${elements.join(', ')}}`;
}
 
console.log(`
A = ${setToString(A)}`);                           // {0, 1, 3}
console.log(`B = ${setToString(B)}`);                           // {1, 2, 3}
console.log(`A △ B = ${setToString(symmetricDifference(A, B))}`);  // {0, 2}
 
// Equivalences
const viaUnionMinusIntersection = (A | B) & ~(A & B);
const viaDifferences = (A & ~B) | (B & ~A);
console.log(`Via (A∪B) - (A∩B): ${setToString(viaUnionMinusIntersection)}`);
console.log(`Via (A-B) ∪ (B-A): ${setToString(viaDifferences)}`);
 
// XOR Properties
console.log("
=== XOR Properties ===");
 
// Self-cancellation: A ^ A = ∅
console.log(`A ^ A = ${A ^ A} (self-cancellation)`);  // 0
 
// Identity: A ^ ∅ = A
console.log(`A ^ 0 = ${A ^ 0} = A? ${(A ^ 0) === A}`);  // true
 
// Commutativity: A ^ B = B ^ A
console.log(`A ^ B = B ^ A? ${(A ^ B) === (B ^ A)}`);  // true
 
// Associativity: (A ^ B) ^ C = A ^ (B ^ C)
const C = 0b0101;
console.log(`(A^B)^C = A^(B^C)? ${((A ^ B) ^ C) === (A ^ (B ^ C))}`);  // true
 
// Inverse: A ^ B ^ B = A (XORing twice cancels)
console.log(`A ^ B ^ B = A? ${(A ^ B ^ B) === A}`);  // true

XOR's Self-Cancellation Property

XOR's self-cancellation (A ^ A = 0) is the key to many clever algorithms: finding the single distinct element in a list of pairs, swapping without a temporary variable, and cryptographic operations. For sets, it means symmetric difference with itself is empty—elements in a set XOR'd with themselves 'cancel out'.

Complement: Working with Negation

The complement of a set A (denoted Aᶜ, Ā, or A') contains all elements NOT in A. With bitmasks, we need to be careful about the size of the universal set—NOT in a 32-bit integer flips all 32 bits, not just the n bits we care about.

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
/**
 * COMPLEMENT: Aᶜ (relative to n-element universal set)
 * Contains all elements in U that are NOT in A.
 * 
 * We can't just use ~A because that flips all 32 bits.
 * Instead, we XOR with the full set mask.
 */
function complement(A: number, n: number): number {
    const fullSet = (1 << n) - 1;  // All n bits set to 1
    return fullSet ^ A;
    
    // Alternatively: fullSet & ~A (AND NOT also works)
}
 
// Demonstration
const n = 4;  // 4-element universe {0, 1, 2, 3}
const fullSet = (1 << n) - 1;  // 0b1111 = 15
const A = 0b1011;  // {0, 1, 3}
 
function setToString(mask: number, n: number): string {
    const elements: number[] = [];
    for (let i = 0; i < n; i++) {
        if ((mask >> i) & 1) elements.push(i);
    }
    return `{${elements.join(', ')}}`;
}
 
console.log(`Universal set U = ${setToString(fullSet, n)}`);   // {0, 1, 2, 3}
console.log(`A = ${setToString(A, n)}`);                       // {0, 1, 3}
console.log(`Aᶜ = ${setToString(complement(A, n), n)}`);       // {2}
 
// Verify complement properties
const compA = complement(A, n);
 
// A ∪ Aᶜ = U
console.log(`A ∪ Aᶜ = U? ${(A | compA) === fullSet}`);  // true
 
// A ∩ Aᶜ = ∅
console.log(`A ∩ Aᶜ = ∅? ${(A & compA) === 0}`);  // true
 
// (Aᶜ)ᶜ = A (double complement)
console.log(`(Aᶜ)ᶜ = A? ${complement(complement(A, n), n) === A}`);  // true
 
// De Morgan's Laws
const B = 0b1110;  // {1, 2, 3}
 
// (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ
const lhs1 = complement(A | B, n);
const rhs1 = complement(A, n) & complement(B, n);
console.log(`(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ? ${lhs1 === rhs1}`);  // true
 
// (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ
const lhs2 = complement(A & B, n);
const rhs2 = complement(A, n) | complement(B, n);
console.log(`(A ∩ B)ᶜ = Aᶜ ∪ Bᶜ? ${lhs2 === rhs2}`);  // true

Beware of Raw NOT (~)

Using ~A directly gives a 32-bit complement including high bits you don't want. For a 4-element set with A = 0b1011, ~A = 0b11111111111111111111111111110100 (with sign extension). Always mask with the full set: (fullSet ^ A) or (fullSet & ~A).

Subset and Superset Testing in O(1)

A critical operation in many algorithms: testing whether one set is a subset or superset of another. With traditional set implementations (arrays, hash sets), this requires O(min(|A|, |B|)) time. With bitmasks, it's O(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
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
/**
 * SUBSET TEST: A ⊆ B
 * Is every element of A also in B?
 * Equivalent: Is the intersection of A and B equal to A?
 * 
 * Bitwise: (A & B) === A
 * Alternatively: (A & ~B) === 0 (nothing in A outside B)
 */
function isSubset(A: number, B: number): boolean {
    return (A & B) === A;
}
 
/**
 * PROPER SUBSET TEST: A ⊂ B
 * A ⊆ B and A ≠ B
 */
function isProperSubset(A: number, B: number): boolean {
    return (A & B) === A && A !== B;
}
 
/**
 * SUPERSET TEST: A ⊇ B
 * Does A contain all elements of B?
 * Flip the roles: B ⊆ A
 */
function isSuperset(A: number, B: number): boolean {
    return (A & B) === B;
}
 
/**
 * PROPER SUPERSET TEST: A ⊃ B
 */
function isProperSuperset(A: number, B: number): boolean {
    return (A & B) === B && A !== B;
}
 
/**
 * DISJOINT TEST: A ∩ B = ∅
 * Do A and B share no elements?
 */
function areDisjoint(A: number, B: number): boolean {
    return (A & B) === 0;
}
 
// Demonstrations
const empty = 0;
const A = 0b0011;  // {0, 1}
const B = 0b1111;  // {0, 1, 2, 3}
const C = 0b1100;  // {2, 3}
 
function setToString(mask: number): string {
    const elements: number[] = [];
    for (let i = 0; i < 4; i++) {
        if ((mask >> i) & 1) elements.push(i);
    }
    return `{${elements.join(', ')}}`;
}
 
console.log("=== Subset Tests ===");
console.log(`${setToString(A)} ⊆ ${setToString(B)}: ${isSubset(A, B)}`);  // true
console.log(`${setToString(A)} ⊂ ${setToString(B)}: ${isProperSubset(A, B)}`);  // true
console.log(`${setToString(B)} ⊆ ${setToString(A)}: ${isSubset(B, A)}`);  // false
console.log(`${setToString(A)} ⊆ ${setToString(A)}: ${isSubset(A, A)}`);  // true (subset, not proper)
console.log(`∅ ⊆ ${setToString(A)}: ${isSubset(empty, A)}`);  // true (empty set is subset of all)
 
console.log("
=== Superset Tests ===");
console.log(`${setToString(B)} ⊇ ${setToString(A)}: ${isSuperset(B, A)}`);  // true
console.log(`${setToString(B)} ⊃ ${setToString(A)}: ${isProperSuperset(B, A)}`);  // true
 
console.log("
=== Disjoint Tests ===");
console.log(`${setToString(A)} ∩ ${setToString(C)} = ∅: ${areDisjoint(A, C)}`);  // true
console.log(`${setToString(A)} ∩ ${setToString(B)} = ∅: ${areDisjoint(A, B)}`);  // false

Summary of Subset Relationship Tests
Test	Condition	Bitwise Expression
A = B	Equal sets	A === B
A ⊆ B	Subset	(A & B) === A
A ⊂ B	Proper subset	(A & B) === A && A !== B
A ⊇ B	Superset	(A & B) === B
A ⊃ B	Proper superset	(A & B) === B && A !== B
A ∩ B = ∅	Disjoint	(A & B) === 0
A ∩ B ≠ ∅	Overlap exists	(A & B) !== 0

Element Extraction: Finding Specific Elements

Often we need to find specific elements within a set—the lowest (smallest index), the highest (largest index), or any element for processing. Bitmask techniques provide elegant O(1) or near-O(1) solutions.

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
85
86
87
88
89
90
91
92
93
94
/**
 * ISOLATE LOWEST SET BIT
 * Returns a mask with only the rightmost 1 bit of A.
 * This corresponds to the smallest element in the set.
 * 
 * Formula: A & (-A)
 * Works because -A = ~A + 1 (two's complement)
 */
function lowestSetBitMask(A: number): number {
    return A & (-A);
}
 
/**
 * GET INDEX OF LOWEST SET BIT
 * Returns the position (element index) of the rightmost 1 bit.
 */
function lowestSetBitIndex(A: number): number {
    if (A === 0) return -1;  // No bits set
    
    // Count trailing zeros
    let index = 0;
    let mask = A;
    while ((mask & 1) === 0) {
        mask >>= 1;
        index++;
    }
    return index;
}
 
/**
 * REMOVE LOWEST SET BIT
 * Clears the rightmost 1 bit.
 * Formula: A & (A - 1)
 */
function clearLowestSetBit(A: number): number {
    return A & (A - 1);
}
 
/**
 * GET INDEX OF HIGHEST SET BIT
 * Returns the position of the leftmost 1 bit (largest element).
 */
function highestSetBitIndex(A: number): number {
    if (A === 0) return -1;
    
    let index = 0;
    while (A > 1) {
        A >>= 1;
        index++;
    }
    return index;
}
 
/**
 * ISOLATE HIGHEST SET BIT
 * Returns a mask with only the leftmost 1 bit set.
 */
function highestSetBitMask(A: number): number {
    if (A === 0) return 0;
    
    // Fill all bits below the highest, then get the top one
    let x = A;
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    return x - (x >> 1);
}
 
// Demonstrations
const A = 0b101100;  // {2, 3, 5}
 
console.log(`A = ${A.toString(2)} = {2, 3, 5}`);
console.log("
=== Lowest Set Bit ===");
console.log(`Lowest bit mask: ${lowestSetBitMask(A).toString(2)}`);  // 100 (bit 2)
console.log(`Lowest bit index: ${lowestSetBitIndex(A)}`);              // 2
console.log(`After clearing lowest: ${clearLowestSetBit(A).toString(2)}`);  // 101000
 
console.log("
=== Highest Set Bit ===");
console.log(`Highest bit index: ${highestSetBitIndex(A)}`);             // 5
console.log(`Highest bit mask: ${highestSetBitMask(A).toString(2)}`);  // 100000
 
// Iterate through all set bits (elements)
console.log("
=== Iterating Through Elements ===");
let mask = A;
while (mask !== 0) {
    const lowest = lowestSetBitIndex(mask);
    console.log(`  Element: ${lowest}`);
    mask = clearLowestSetBit(mask);  // Remove and continue
}

Why A & (-A) Works

In two's complement, -A equals ~A + 1. Adding 1 to ~A propagates a carry through all the trailing zeros of ~A (which were trailing ones of A), stopping at the first 0 of ~A (the first 1 of A). The AND then isolates just that bit. Example: A = 1100, ~A = 0011, -A = 0100, A & -A = 0100.

Counting Elements: Population Count

The cardinality |A| of a set A (number of elements) corresponds to the population count or popcount of the bitmask—the number of 1 bits. This operation is so fundamental that modern CPUs have dedicated instructions for it.

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
85
86
87
88
89
90
/**
 * Brian Kernighan's Algorithm
 * Time: O(k) where k is the number of set bits
 * 
 * Each iteration clears the lowest set bit.
 * Elegant and fast when few bits are set.
 */
function popcountKernighan(x: number): number {
    let count = 0;
    while (x !== 0) {
        x &= (x - 1);  // Clear lowest set bit
        count++;
    }
    return count;
}
 
/**
 * Lookup Table Method
 * Precompute counts for all 8-bit values, then combine.
 * Time: O(1) with O(256) preprocessing
 */
const POPCOUNT_TABLE: number[] = [];
for (let i = 0; i < 256; i++) {
    POPCOUNT_TABLE[i] = popcountKernighan(i);
}
 
function popcountTable(x: number): number {
    return POPCOUNT_TABLE[x & 0xff] +
           POPCOUNT_TABLE[(x >> 8) & 0xff] +
           POPCOUNT_TABLE[(x >> 16) & 0xff] +
           POPCOUNT_TABLE[(x >> 24) & 0xff];
}
 
/**
 * Bit Manipulation Method (SWAR algorithm)
 * Parallel bit counting using clever arithmetic.
 * Time: O(1), constant number of operations
 * 
 * This is what compilers often generate for popcount.
 */
function popcountSWAR(x: number): number {
    // Handle as unsigned 32-bit integer
    x = x >>> 0;
    
    // Count pairs of bits
    x = x - ((x >>> 1) & 0x55555555);
    
    // Count quads of bits
    x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
    
    // Count octets
    x = (x + (x >>> 4)) & 0x0f0f0f0f;
    
    // Sum all bytes
    x = x + (x >>> 8);
    x = x + (x >>> 16);
    
    return x & 0x3f;
}
 
// Demonstrations
const A = 0b10110101;  // 8 bits, 5 set
 
console.log(`A = ${A.toString(2)} has ${popcountKernighan(A)} set bits`);
console.log(`Table method: ${popcountTable(A)}`);
console.log(`SWAR method: ${popcountSWAR(A)}`);
 
// Application: Is the set size even or odd?
function hasEvenCardinality(A: number): boolean {
    return popcountKernighan(A) % 2 === 0;
}
 
// Application: Does set have exactly one element?
function isSingleton(A: number): boolean {
    return A !== 0 && (A & (A - 1)) === 0;
}
 
// Application: Does set have exactly two elements?
function hasExactlyTwo(A: number): boolean {
    if (A === 0) return false;
    const withoutOne = A & (A - 1);
    return withoutOne !== 0 && (withoutOne & (withoutOne - 1)) === 0;
}
 
console.log("
=== Special Cardinality Tests ===");
console.log(`{}: singleton? ${isSingleton(0)}`);           // false
console.log(`{2}: singleton? ${isSingleton(0b100)}`);      // true
console.log(`{1,3}: singleton? ${isSingleton(0b1010)}`);   // false
console.log(`{1,3}: exactly 2? ${hasExactlyTwo(0b1010)}`); // true

Hardware Popcount

Modern x86 CPUs (since 2008) have the POPCNT instruction that counts bits in a single cycle. WebAssembly exposes i32.popcnt. JavaScript engines may or may not use hardware popcount depending on the engine and context. For performance-critical code, benchmark your specific environment.

Set Modification: Add, Remove, Toggle

Beyond computing new sets from existing ones, we often need to modify a set by adding, removing, or toggling individual elements. These are the building blocks for constructing sets element by element.

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
85
86
/**
 * ADD ELEMENT: Insert element i into set A
 * Bitwise: A OR with singleton mask for i
 * Idempotent: Adding an existing element is a no-op
 */
function addElement(A: number, i: number): number {
    return A | (1 << i);
}
 
/**
 * REMOVE ELEMENT: Delete element i from set A
 * Bitwise: AND with complement of singleton mask
 * Idempotent: Removing an absent element is a no-op
 */
function removeElement(A: number, i: number): number {
    return A & ~(1 << i);
}
 
/**
 * TOGGLE ELEMENT: Flip membership of element i
 * Bitwise: XOR with singleton mask
 * Non-idempotent: Toggle twice returns to original
 */
function toggleElement(A: number, i: number): number {
    return A ^ (1 << i);
}
 
/**
 * SET ELEMENT: Explicitly set element i to in/out
 */
function setElement(A: number, i: number, present: boolean): number {
    if (present) {
        return A | (1 << i);
    } else {
        return A & ~(1 << i);
    }
}
 
/**
 * CONDITIONAL ADD: Add element only if condition is true
 * Avoids branching for performance-critical code
 */
function conditionalAdd(A: number, i: number, condition: boolean): number {
    // condition converts to 0 or 1
    // We create a mask of all 0s or all 1s
    const condMask = condition ? ~0 : 0;
    return A | ((1 << i) & condMask);
}
 
// Demonstrations
let set = 0;  // Start with empty set
 
console.log("Building {1, 3, 5} step by step:");
set = addElement(set, 1);
console.log(`After add(1): ${set.toString(2)}`);    // 10
 
set = addElement(set, 3);
console.log(`After add(3): ${set.toString(2)}`);    // 1010
 
set = addElement(set, 5);
console.log(`After add(5): ${set.toString(2)}`);    // 101010
 
console.log("
Removing elements:");
set = removeElement(set, 3);
console.log(`After remove(3): ${set.toString(2)}`); // 100010
 
console.log("
Toggling elements:");
set = toggleElement(set, 3);  // Add back
console.log(`After toggle(3): ${set.toString(2)}`); // 101010
 
set = toggleElement(set, 3);  // Remove
console.log(`After toggle(3): ${set.toString(2)}`); // 100010
 
// Build set from array of elements
function buildSet(elements: number[]): number {
    let mask = 0;
    for (const e of elements) {
        mask = addElement(mask, e);
    }
    return mask;
}
 
console.log(`
Build from [0, 2, 4]: ${buildSet([0, 2, 4]).toString(2)}`);  // 10101

Set Modification Summary
Operation	Effect	Expression	Idempotent?
Add element i	Ensure i is in set	A \| (1 << i)	Yes
Remove element i	Ensure i is not in set	A & ~(1 << i)	Yes
Toggle element i	Flip membership of i	A ^ (1 << i)	No
Check element i	Test if i is in set	(A >> i) & 1	N/A

Complete Bitmask Operations Reference

Here's a consolidated reference of all bitmask set operations covered in this page, organized for quick lookup:

Bitmask Set Operations Quick Reference
Operation	Set Theory	Bitmask Expression
Empty set	∅	0
Full set (n elements)	U	(1 << n) - 1
Singleton {i}	{i}	1 << i
Union	A ∪ B	A \| B
Intersection	A ∩ B	A & B
Difference	A - B	A & ~B
Symmetric difference	A △ B	A ^ B
Complement	Aᶜ	fullSet ^ A
Add element i	A ∪ {i}	A \| (1 << i)
Remove element i	A - {i}	A & ~(1 << i)
Toggle element i	A △ {i}	A ^ (1 << i)
Contains element i?	i ∈ A	(A >> i) & 1
Subset test	A ⊆ B	(A & B) === A
Disjoint test	A ∩ B = ∅	(A & B) === 0
Cardinality	\|A\|	popcount(A)
Minimum element	min(A)	index of lowest bit
Remove minimum	A - {min(A)}	A & (A - 1)
Isolate minimum	{min(A)}	A & (-A)

Operations Mastery Complete

You now have a complete toolkit for set operations using bitmasks. Every operation is O(1), leveraging hardware-level bitwise instructions. These operations form the foundation for efficient combinatorial algorithms and bitmask dynamic programming, which we explore in the next page.

Summary: Operations Unlocked

We've built a comprehensive understanding of how set operations translate to bitwise expressions. Let's consolidate the key insights:

Key Takeaways

•Boolean-Set Isomorphism: OR = Union, AND = Intersection, XOR = Symmetric Difference, NOT = Complement. All Boolean algebra theorems apply to set operations.
•O(1) Everything: Union, intersection, difference, subset testing—all single CPU cycles. No loops, no hash table lookups.
•Complement Requires Care: Use (fullSet ^ A) to get the n-bit complement, not raw ~A which affects all 32 bits.
•Subset by AND: A ⊆ B iff (A & B) === A. This elegant test underlies many algorithms.
•Lowest Bit Magic: A & (-A) isolates the lowest set bit, A & (A-1) clears it. Enables efficient element iteration.
•Popcount is Fundamental: Counting set bits gives cardinality. Modern CPUs have dedicated instructions.
•Modification is Clean: Add (OR), Remove (AND NOT), Toggle (XOR). Build sets incrementally with single operations.

What's next:

With representation, iteration, and operations mastered, we're ready for the pinnacle of bitmask techniques: Bitmask Dynamic Programming. This powerful paradigm uses bitmasks as DP states, enabling elegant solutions to combinatorial optimization problems. The next page introduces this technique that separates proficient programmers from algorithm experts.

Operations Reference Complete

You've mastered the complete set of bitmask operations—from fundamental union/intersection to element extraction and population counting. These O(1) primitives are the building blocks for efficient algorithms. Next, we'll combine everything into the powerful technique of Bitmask Dynamic Programming.