46:"/_next/static/chunks/33yus346z0l_n.js" 47:"/_next/static/chunks/1r8ezocsukqp8.js" 48:"/_next/static/chunks/0iv56yrji_20j.js" 49:"/_next/static/chunks/0wa9m1-tphf9u.js" 4a:"/_next/static/chunks/08cuqqn_f60pp.js" 4b:"/_next/static/chunks/3zdsl3f9b0--r.js" 4c:"/_next/static/chunks/2j22cxchii_xx.js" 4d:"/_next/static/chunks/3bgoyiso1rhn7.js" 4e:"/_next/static/chunks/01a-3hvnqu8wl.js" 4f:"/_next/static/chunks/3m1xjj5kw5fie.js" 50:"/_next/static/chunks/0om3fkgfnicab.js" 51:"/_next/static/chunks/0gafyzg9j9yqj.js" 52:"/_next/static/chunks/20w4eaqlekefm.js" 53:"/_next/static/chunks/449--h5z1s6nq.js" 54:"/_next/static/chunks/3k2gyg36fnag_.js" 55:"/_next/static/chunks/18ggtgz2yf759.js" 56:"/_next/static/chunks/0hlb44ca7-4a2.js" 57:"/_next/static/chunks/253gnmj0-cj17.js" 58:"/_next/static/chunks/09nq57stwzkgf.js" 59:"/_next/static/chunks/082jo-0ajazgr.js" 5a:"/_next/static/chunks/2ozcrjb_hh74t.js" 5b:"/_next/static/chunks/05i8en-x14ibi.js" 5c:"/_next/static/chunks/32izpn90gvm22.js" 5d:"/_next/static/chunks/0jbzid2v9xv3h.js" 5e:"/_next/static/chunks/0i3-eynrkvqi7.js" 5f:"/_next/static/chunks/1tn-0fivsxsv1.js" 60:"/_next/static/chunks/34h36hyf_ggow.js" 61:"/_next/static/chunks/20329i6m_04t6.js" 62:"/_next/static/chunks/161uxd62cjny2.js" 63:"/_next/static/chunks/2k8pepwc4pxns.js" 64:I[593304,["$2b","$2c","$2d","$2e","$2f","$30","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61","$62","$63"],"OwnedHydration"] 65:T635,// 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)66:T919,/** * 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]67:Tb56,// 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)}`); // 368:T4b3,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}`);69:T7c8,// 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)}`); // true6a:T6dc,// 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; }45:["$","$L64",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792316207213,"state":{"data":{"json":{"id":"seed_9972cfb0906a5d1ec680c10b6fcbb693","slug":"bitmasks-for-subset-representation","category":"Data Structures & Algorithms","topic":"Bitmasks for Subset Representation","title":"Bitmasks for Subset Representation","description":"Master the elegant technique of representing sets and subsets using integers. Learn how bitmasks enable O(1) set operations, efficient subset enumeration, and form the foundation for bitmask dynamic programming—a powerful technique for solving combinatorial optimization problems.","difficulty":"INTERMEDIATE","estimatedMinutes":55,"pages":[{"id":"seed_71915742b25847ca7a0defbb7a7bd93c","title":"Representing Subsets as Integers","order":0,"content":[{"id":"opening-hook","title":"The Elegant Bridge: Sets Meet Binary","content":[{"data":{"content":"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.\n\nConsider 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."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Master","content":"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.","variant":"info"},"type":"callout"}]},{"id":"subset-integer-correspondence","title":"The Subset-Integer Correspondence","content":[{"data":{"content":"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:\n\n**U = {element₀, element₁, element₂, ..., elementₙ₋₁}**\n\nNow, for any subset S ⊆ U, we can define a characteristic function that maps each element to either 0 or 1:\n\n```\nχ_S(elementᵢ) = 1 if elementᵢ ∈ S\nχ_S(elementᵢ) = 0 if elementᵢ ∉ S\n```\n\nThis 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.\n\n**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]."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Mathematical Bijection","content":"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.","variant":"tip"},"type":"callout"},{"data":{"rows":[["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"]],"caption":"Complete Subset-Integer Mapping for a 3-Element Set {a, b, c}","headers":["Integer","Binary","Subset","Set Notation"]},"type":"table"},{"data":{"content":"**Observation from the table:**\n\n- Integer 0 (000₂) represents the empty set—no bits are set, so no elements are included\n- Integer 7 (111₂) represents the full set—all bits are set, so all elements are included\n- Each power of 2 (1, 2, 4) represents a singleton set—exactly one bit is set\n- The binary representation directly encodes membership: bit i is 1 iff element i is in the subset\n\nThis 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."},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"bit-position-mapping","title":"The Bit-Position Element Mapping","content":[{"data":{"content":"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.\n\n**Standard convention:**\n- Bit 0 (the least significant bit, or LSB) → Element 0\n- Bit 1 → Element 1\n- Bit 2 → Element 2\n- ...\n- Bit n-1 (the most significant bit in our n-bit representation) → Element n-1\n\nThis 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."},"type":"text"},{"data":{"code":"$65","title":"Bitmask Fundamentals: Element-to-Bit Correspondence","language":"typescript"},"type":"code"},{"data":{"icon":"Info","title":"Why LSB for Element 0?","content":"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.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"encoding-decoding","title":"Encoding and Decoding Subsets","content":[{"data":{"content":"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.\n\nThese operations are fundamental—they form the bridge between human-readable sets and machine-efficient integers."},"type":"text"},{"data":{"code":"$66","title":"Complete Encoding and Decoding Implementation","language":"typescript"},"type":"code"},{"data":{"content":"**Key insights from the implementation:**\n\n1. **Encoding is additive**: Each element contributes its bit independently. The order of processing doesn't matter because bitwise OR is commutative.\n\n2. **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.\n\n3. **Round-trip consistency**: For any valid subset, `decodeSubset(encodeSubset(elements))` returns a sorted version of the original elements."},"type":"text"}],"titleType":"number","titleNumber":3},{"id":"why-bitmasks-o1","title":"Why Bitmasks Enable O(1) Set Operations","content":[{"data":{"content":"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**.\n\nThe 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."},"type":"text"},{"data":{"rows":[["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"]],"caption":"Set Operations: Bitmask vs Traditional Implementations","headers":["Operation","Bitmask Impl","Array Impl","Hash Set Impl"]},"type":"table"},{"data":{"icon":"Zap","title":"Hardware-Level Efficiency","content":"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.","variant":"tip"},"type":"callout"},{"data":{"code":"$67","title":"O(1) Set Operations with Bitmasks","language":"typescript"},"type":"code"}],"titleType":"number","titleNumber":4},{"id":"power-of-two-connection","title":"The Power of Two Connection","content":[{"data":{"content":"The relationship between subsets and powers of two reveals deep mathematical structure. This isn't just convenient—it's a window into combinatorics itself.\n\n**Why exactly 2ⁿ subsets?**\n\nFor 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:\n\n2 × 2 × 2 × ... × 2 (n times) = 2ⁿ possible subsets\n\nThis is precisely the range of n-bit integers [0, 2ⁿ - 1]."},"type":"text"},{"data":{"items":["**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)."],"title":{"icon":"Sparkles","text":"Elegant Correspondences","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"code":"$68","title":"Special Sets and Power-of-Two Relationships","language":"typescript"},"type":"code"},{"data":{"icon":"AlertCircle","title":"The Maximum Set Size Constraint","content":"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.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"practical-examples","title":"Practical Examples: Bitmasks in Action","content":[{"data":{"content":"Let's solidify understanding with practical examples that demonstrate why engineers reach for bitmasks in real systems."},"type":"text"},{"data":{"code":"$69","title":"Example 1: Feature Flags with Bitmasks","language":"typescript"},"type":"code"},{"data":{"code":"$6a","title":"Example 2: Permissions in Access Control","language":"typescript"},"type":"code"},{"data":{"icon":"Database","title":"Database Efficiency","content":"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.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"subset-lattice","title":"Visualizing the Subset Lattice","content":[{"data":{"content":"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.\n\nConsider 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:"},"type":"text"},{"data":{"code":" {a,b,c} = 7 = 111₂\n / | \\\n {a,b} {a,c} {b,c}\n =6 =5 =3\n 110₂ 101₂ 011₂\n / \\ / \\ / \\\n {a} {b} {c}\n =1 =2 =4\n 001₂ 010₂ 100₂\n \\ | /\n {}\n = 0\n 000₂\n\nKey observations:\n- The empty set (0) is at the bottom - subset of everything\n- The full set (7) is at the top - superset of everything\n- Moving UP adds one element (sets one bit)\n- Moving DOWN removes one element (clears one bit)\n- Each level contains C(3,k) subsets of size k\n - Level 0: C(3,0) = 1 subset (the empty set)\n - Level 1: C(3,1) = 3 subsets (singletons)\n - Level 2: C(3,2) = 3 subsets (pairs)\n - Level 3: C(3,3) = 1 subset (the full set)\n- Total: 1 + 3 + 3 + 1 = 8 = 2³ subsets","title":"The Subset Lattice for {a, b, c}","language":"plaintext"},"type":"code"},{"data":{"content":"**The lattice and bitmask operations:**\n\n- **Union** of two sets is their **least upper bound** in the lattice\n- **Intersection** is their **greatest lower bound**\n- **Subset ordering** A ⊆ B means there's a path up from A to B\n- **Popcount** gives the level in the lattice (number of elements)\n\nThis 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."},"type":"text"}],"titleType":"number","titleNumber":7},{"id":"summary-bridge","title":"Summary: The Foundation Established","content":[{"data":{"content":"We've established the foundational understanding of bitmask subset representation. Let's consolidate what we've learned:"},"type":"text"},{"data":{"type":"ordered","items":["**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."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's next:**\n\nNow 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."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Foundation Complete","content":"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.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_a7afe573423d3505b00ba77c6b2fcc01","title":"Iterating Through All Subsets","order":1,"content":null,"isLocked":true},{"id":"seed_8821b9567910738f4459b54bb8133846","title":"Subset Operations with Bitwise Ops","order":2,"content":null,"isLocked":true},{"id":"seed_02c8eb701860780c8db2ce1f627f6b32","title":"Bitmask DP Introduction","order":3,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792316207203,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"bitmasks-for-subset-representation"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"bitmasks-for-subset-representation\"},\"type\":\"query\"}]"},{"dehydratedAt":1792316207213,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792316207210,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_9972cfb0906a5d1ec680c10b6fcbb693"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_9972cfb0906a5d1ec680c10b6fcbb693\"},\"type\":\"query\"}]"},{"dehydratedAt":1792316207213,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792316207211,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_a7afe573423d3505b00ba77c6b2fcc01"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_a7afe573423d3505b00ba77c6b2fcc01\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792316207213,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792316207211,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_a7afe573423d3505b00ba77c6b2fcc01"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_a7afe573423d3505b00ba77c6b2fcc01\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792316207213,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792316207211,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_a7afe573423d3505b00ba77c6b2fcc01"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_a7afe573423d3505b00ba77c6b2fcc01\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792316207213,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_a7afe573423d3505b00ba77c6b2fcc01","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_a7afe573423d3505b00ba77c6b2fcc01\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@6b"}]},"children":"$L6c"}]