7a:T492,Throughout this chapter on bit manipulation, you've acquired a powerful arsenal of techniques: bitwise operators, shifting, individual bit operations, XOR patterns, bitmask representations, and specialized algorithms. But there's a crucial meta-skill that separates engineers who *know* bit manipulation from those who *excel* at it: **recognizing when to apply these techniques in the first place**. Consider this paradox: the most elegant bit manipulation solutions often look nothing like the original problem statement. A problem about counting unique elements becomes an XOR operation. A subset enumeration problem becomes an integer loop. A toggle mechanism becomes a single AND or OR. The transformation from problem to bitwise solution requires a different kind of thinking—one that sees through the surface description to the underlying binary structure. This page develops that vision. We'll build systematic frameworks for identifying problems where bit manipulation provides significant advantages, explore the signatures that betray a problem's suitability for bitwise solutions, and learn to distinguish genuine optimizations from premature cleverness.7b:T4ed,Before we can identify good candidates for bit manipulation, we need to understand *why* bit manipulation works at all. This isn't about memorizing tricks—it's about understanding the computational model deeply enough to recognize opportunities. **Bit manipulation provides advantages in three fundamental dimensions:** **1. Representational Efficiency** Bits are the most compact possible representation. A 64-bit integer can represent: - 64 independent boolean flags (versus 64 bytes for a boolean array) - Any subset of a 64-element set (versus an array or hash set) - A small integer packed with other data (bit fields) **2. Operational Parallelism** A single bitwise operation affects all bits simultaneously. When you compute `a & b` for 32-bit integers, you're performing 32 AND operations in a single CPU instruction. This *implicit parallelism* makes bit operations extraordinarily efficient for problems that would otherwise require loops. **3. Hardware Proximity** Bitwise operations map directly to individual CPU instructions. There's no interpretation layer, no function call overhead, no memory indirection. They execute in single clock cycles on modern processors, often with multiple operations per cycle due to instruction pipelining.7c:T466,// Traditional approach: using object/array for permissions interface TraditionalPermissions { read: boolean; write: boolean; execute: boolean; delete: boolean; share: boolean; } function hasAllPermissions(p: TraditionalPermissions): boolean { return p.read && p.write && p.execute && p.delete && p.share; } // Bitwise approach: using bit flags const enum Permission { NONE = 0b00000, READ = 0b00001, WRITE = 0b00010, EXECUTE = 0b00100, DELETE = 0b01000, SHARE = 0b10000, ALL = 0b11111 } function hasAllPermissionsBit(p: number): boolean { return (p & Permission.ALL) === Permission.ALL; } // Checking multiple permissions at once function canEditAndShare(p: number): boolean { const required = Permission.READ | Permission.WRITE | Permission.SHARE; return (p & required) === required; } // Granting permissions function grantPermission(current: number, newPerm: Permission): number { return current | newPerm; } // Revoking permissions function revokePermission(current: number, perm: Permission): number { return current & ~perm; }7d:T427,from enum import IntFlag # Traditional approach: using dictionary for permissions def has_all_permissions_traditional(p: dict) -> bool: return (p.get('read', False) and p.get('write', False) and p.get('execute', False) and p.get('delete', False) and p.get('share', False)) # Bitwise approach: using IntFlag class Permission(IntFlag): NONE = 0b00000 READ = 0b00001 WRITE = 0b00010 EXECUTE = 0b00100 DELETE = 0b01000 SHARE = 0b10000 ALL = 0b11111 def has_all_permissions_bit(p: int) -> bool: return (p & Permission.ALL) == Permission.ALL # Checking multiple permissions at once def can_edit_and_share(p: int) -> bool: required = Permission.READ | Permission.WRITE | Permission.SHARE return (p & required) == required # Granting permissions def grant_permission(current: int, new_perm: Permission) -> int: return current | new_perm # Revoking permissions def revoke_permission(current: int, perm: Permission) -> int: return current & ~perm7e:T591,// Iterate through all subsets of a set with n elements function allSubsets(n: number): number[] { const result: number[] = []; // There are 2^n subsets, represented as 0 to 2^n - 1 for (let mask = 0; mask < (1 << n); mask++) { result.push(mask); } return result; } // Iterate through all subsets of a given set (mask) function subsetsOfMask(mask: number): number[] { const subsets: number[] = []; for (let sub = mask; sub > 0; sub = (sub - 1) & mask) { subsets.push(sub); } subsets.push(0); // Empty subset return subsets; } // Check if subset A is contained in subset B function isSubset(a: number, b: number): boolean { return (a & b) === a; } // Check if two subsets overlap function overlaps(a: number, b: number): boolean { return (a & b) !== 0; } // Union and intersection const union = (a: number, b: number): number => a | b; const intersection = (a: number, b: number): number => a & b; const difference = (a: number, b: number): number => a & ~b; // Example: Find all pairs of disjoint subsets function disjointSubsetPairs(n: number): [number, number][] { const pairs: [number, number][] = []; const total = 1 << n; for (let a = 0; a < total; a++) { for (let b = 0; b < total; b++) { if ((a & b) === 0) { // Disjoint check pairs.push([a, b]); } } } return pairs; }7f:T490,def all_subsets(n: int) -> list[int]: """Iterate through all subsets of a set with n elements.""" # There are 2^n subsets, represented as 0 to 2^n - 1 return list(range(1 << n)) def subsets_of_mask(mask: int) -> list[int]: """Iterate through all subsets of a given set (mask).""" subsets = [] sub = mask while sub > 0: subsets.append(sub) sub = (sub - 1) & mask subsets.append(0) # Empty subset return subsets def is_subset(a: int, b: int) -> bool: """Check if subset A is contained in subset B.""" return (a & b) == a def overlaps(a: int, b: int) -> bool: """Check if two subsets overlap.""" return (a & b) != 0 # Set operations def union(a: int, b: int) -> int: return a | b def intersection(a: int, b: int) -> int: return a & b def difference(a: int, b: int) -> int: return a & ~b def disjoint_subset_pairs(n: int) -> list[tuple[int, int]]: """Find all pairs of disjoint subsets.""" pairs = [] total = 1 << n for a in range(total): for b in range(total): if (a & b) == 0: # Disjoint check pairs.append((a, b)) return pairs80:T5ea,// Find the single non-duplicate in an array where every other element appears twice function findUnique(nums: number[]): number { return nums.reduce((xor, num) => xor ^ num, 0); } // Find missing number in [0, n] where one number is missing function findMissing(nums: number[]): number { const n = nums.length; let xor = n; // Start with n since we expect [0, n] for (let i = 0; i < n; i++) { xor ^= i ^ nums[i]; } return xor; } // Check if string can form a palindrome (at most one character with odd count) function canFormPalindrome(s: string): boolean { let mask = 0; for (const char of s) { const bit = 1 << (char.charCodeAt(0) - 'a'.charCodeAt(0)); mask ^= bit; // Toggle bit for this character } // Check if at most one bit is set (0 or power of 2) return (mask & (mask - 1)) === 0; } // Find the two unique numbers in array where every other appears twice function findTwoUnique(nums: number[]): [number, number] { // XOR all numbers to get xor of the two unique numbers let xorAll = 0; for (const num of nums) { xorAll ^= num; } // Find rightmost set bit (where the two numbers differ) const rightmostBit = xorAll & (-xorAll); // Partition numbers by this bit and XOR separately let a = 0, b = 0; for (const num of nums) { if (num & rightmostBit) { a ^= num; } else { b ^= num; } } return [a, b]; }81:T53c,from functools import reduce from operator import xor def find_unique(nums: list[int]) -> int: """Find the single non-duplicate where every other element appears twice.""" return reduce(xor, nums, 0) def find_missing(nums: list[int]) -> int: """Find missing number in [0, n] where one number is missing.""" n = len(nums) xor_result = n # Start with n since we expect [0, n] for i in range(n): xor_result ^= i ^ nums[i] return xor_result def can_form_palindrome(s: str) -> bool: """Check if string can form a palindrome.""" mask = 0 for char in s: bit = 1 << (ord(char) - ord('a')) mask ^= bit # Toggle bit for this character # Check if at most one bit is set (0 or power of 2) return (mask & (mask - 1)) == 0 def find_two_unique(nums: list[int]) -> tuple[int, int]: """Find the two unique numbers where every other appears twice.""" # XOR all numbers to get xor of the two unique numbers xor_all = reduce(xor, nums, 0) # Find rightmost set bit (where the two numbers differ) rightmost_bit = xor_all & (-xor_all) # Partition numbers by this bit and XOR separately a = b = 0 for num in nums: if num & rightmost_bit: a ^= num else: b ^= num return (a, b)82:T44f,/** * Problem: Given n items with values and weights, and a knapsack capacity, * find the maximum value subset where no two items are adjacent in the * original array. n ≤ 20. * * Recognition: n ≤ 20 suggests bitmask enumeration is feasible. * 2^20 = ~1 million, easily computable. */ function maxValueNoAdjacent(values: number[], weights: number[], capacity: number): number { const n = values.length; let maxValue = 0; // Enumerate all 2^n subsets for (let mask = 0; mask < (1 << n); mask++) { // Check if any adjacent bits are both set if ((mask & (mask >> 1)) !== 0) continue; // Adjacent items selected // Calculate total weight and value let totalWeight = 0; let totalValue = 0; for (let i = 0; i < n; i++) { if (mask & (1 << i)) { totalWeight += weights[i]; totalValue += values[i]; } } if (totalWeight <= capacity) { maxValue = Math.max(maxValue, totalValue); } } return maxValue; }83:T56d,/** * Find the single number when all others appear exactly 3 times. * Can't use simple XOR since triple XOR doesn't cancel. * * Approach: Count the number of 1s at each bit position. * If a number appears 3 times, its bits contribute multiples of 3. * The unique number's bits will have counts not divisible by 3. */ function singleNumberThrice(nums: number[]): number { let result = 0; // Check each bit position (assuming 32-bit integers) for (let bit = 0; bit < 32; bit++) { let count = 0; // Count how many numbers have this bit set for (const num of nums) { if (num & (1 << bit)) { count++; } } // If count is not divisible by 3, the unique number has this bit set if (count % 3 !== 0) { result |= (1 << bit); } } return result; } // Alternative: Using state machine with two variables function singleNumberThriceOptimized(nums: number[]): number { let ones = 0; // Bits that have appeared 1 mod 3 times let twos = 0; // Bits that have appeared 2 mod 3 times for (const num of nums) { // Update ones and twos // After seeing a bit: 0->1->2->0 cycle ones = (ones ^ num) & ~twos; twos = (twos ^ num) & ~ones; } return ones; // Bits appearing exactly once }84:T545,def single_number_thrice(nums: list[int]) -> int: """ Find the single number when all others appear exactly 3 times. Approach: Count the number of 1s at each bit position. If a number appears 3 times, its bits contribute multiples of 3. The unique number's bits will have counts not divisible by 3. """ result = 0 # Check each bit position (assuming 32-bit integers) for bit in range(32): count = 0 # Count how many numbers have this bit set for num in nums: if num & (1 << bit): count += 1 # If count is not divisible by 3, the unique number has this bit set if count % 3 != 0: result |= (1 << bit) # Handle negative numbers in Python (arbitrary precision) if result >= (1 << 31): result -= (1 << 32) return result def single_number_thrice_optimized(nums: list[int]) -> int: """Alternative: Using state machine with two variables.""" ones = 0 # Bits that have appeared 1 mod 3 times twos = 0 # Bits that have appeared 2 mod 3 times for num in nums: # Update ones and twos # After seeing a bit: 0->1->2->0 cycle ones = (ones ^ num) & ~twos twos = (twos ^ num) & ~ones return ones # Bits appearing exactly once85:T694,/** * Traveling Salesman Problem using Bitmask DP * * State: dp[mask][i] = minimum cost to visit all cities in mask, ending at city i * Transition: dp[mask | (1 << j)][j] = min(dp[mask][i] + cost[i][j]) for all i in mask * * Time: O(n² × 2^n) * Space: O(n × 2^n) */ function tsp(cost: number[][]): number { const n = cost.length; const INF = Number.MAX_SAFE_INTEGER; // dp[mask][i] = min cost to visit cities in mask, ending at i const dp: number[][] = Array(1 << n) .fill(null) .map(() => Array(n).fill(INF)); // Start at city 0 dp[1][0] = 0; // Iterate over all masks for (let mask = 1; mask < (1 << n); mask++) { // For each ending city in the current mask for (let last = 0; last < n; last++) { if (!(mask & (1 << last))) continue; // last not in mask if (dp[mask][last] === INF) continue; // Try extending to unvisited cities for (let next = 0; next < n; next++) { if (mask & (1 << next)) continue; // next already visited const newMask = mask | (1 << next); dp[newMask][next] = Math.min( dp[newMask][next], dp[mask][last] + cost[last][next] ); } } } // Find minimum: visit all cities and return to start const fullMask = (1 << n) - 1; let minCost = INF; for (let last = 1; last < n; last++) { if (dp[fullMask][last] !== INF) { minCost = Math.min(minCost, dp[fullMask][last] + cost[last][0]); } } return minCost; }86:T669,Building recognition skills requires practice. For each problem description below, determine whether bit manipulation is appropriate and why. **Exercise 1:** *"Given an array of integers where every element appears three times except one that appears once, find that element."* **Analysis:** ✅ Good for bit manipulation. Count bits modulo 3. XOR alone doesn't work, but bit counting does. **Exercise 2:** *"Given a sorted array of 10^6 unique integers and a target, find two numbers that sum to the target."* **Analysis:** ❌ Not suitable. Large array, arithmetic relationship (sum), two-pointer or hash approach is better. **Exercise 3:** *"Given n ≤ 15 items with weights and a truck capacity, find the maximum number of items that can fit if selected items can't be adjacent in the original list."* **Analysis:** ✅ Good for bit manipulation. Small n means 2^15 = 32K subsets. Bitmask to check adjacency: `(mask & (mask >> 1)) == 0`. **Exercise 4:** *"Given a string, determine if any permutation of it could form a palindrome."* **Analysis:** ✅ Good for bit manipulation. Use bitmask to track odd character counts. Result: at most one bit set. **Exercise 5:** *"Given an array of integers, find the longest increasing subsequence."* **Analysis:** ❌ Not suitable. This is a classic DP problem. Binary search optimization exists but isn't bitwise. **Exercise 6:** *"Given n ≤ 20 people and m ≤ 20 tasks, where each person can do certain tasks, find if all tasks can be assigned to different people."* **Analysis:** ✅ Good for bit manipulation. Bitmask DP or bipartite matching. Small n and m make 2^20 feasible.72:{"json":{"id":"seed_3cf708270c04c1b27818bd723ce78fbd","slug":"when-to-use-bit-manipulation","category":"Data Structures & Algorithms","topic":"When to Use Bit Manipulation","title":"When to Use Bit Manipulation","description":"Master the meta-skill of recognizing when bit manipulation is the optimal approach. Learn to identify problem signatures, understand space-performance trade-offs, and know when bit-level thinking simplifies versus complicates solutions—the judgment that separates senior engineers from novices.","difficulty":"ADVANCED","estimatedMinutes":60,"pages":[{"id":"seed_b7e7722999c2dbc89ff50af0d0d4602d","title":"Identifying Problems Suited for Bits","order":0,"content":[{"id":"opening-hook","title":"The Pattern Recognition Problem","content":[{"data":{"content":"$7a"},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will be able to recognize problem patterns that signal bit manipulation opportunities, understand the categorical domains where bits excel, apply a systematic decision framework for choosing bitwise approaches, and avoid common traps where bit manipulation seems attractive but isn't optimal.","variant":"info"},"type":"callout"}]},{"id":"fundamental-question","title":"The Fundamental Question: Why Bits?","content":[{"data":{"content":"$7b"},"type":"text"},{"data":{"rows":[["64 boolean flags","64-byte array","Single 64-bit integer","64× space reduction"],["Check 32 conditions","32 conditional branches","Single AND/OR operation","~32× time reduction"],["Toggle N values","N loop iterations","Single XOR operation","N× time reduction"],["Subset enumeration (n≤20)","Recursive generation","Integer iteration","Lower overhead, cache-friendly"],["Parity computation","Loop with counter","XOR reduction + popcount","Often 10×+ speedup"]],"caption":"Bit Manipulation Advantage Sources","headers":["Dimension","Traditional Approach","Bitwise Approach","Advantage Factor"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"The Core Insight","content":"Bit manipulation excels when you can **transform a problem operating on discrete, bounded elements into operations on the bit representations of those elements**. The key is recognizing that transformation possibility.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"problem-domain-categories","title":"Problem Domain Categories","content":[{"data":{"content":"Certain problem domains are naturally suited to bit manipulation. Recognizing these categories is the first level of pattern recognition.\n\n### Category 1: Boolean Flag Management\n\nWhenever a problem involves multiple independent boolean states, bit manipulation is almost always superior.\n\n**Signature characteristics:**\n- Multiple on/off or true/false values\n- Need to check, set, or toggle individual states\n- States need to be stored or transmitted compactly\n- Operations on combinations of states\n\n**Examples:**\n- Permission systems (read/write/execute)\n- Feature toggles in configuration\n- Game state flags (visited cells, collected items)\n- Hardware register manipulation"},"type":"text"},{"data":{"fileName":"boolean_flags_example","languages":[{"code":"$7c","label":"TypeScript","value":"typescript"},{"code":"$7d","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"### Category 2: Subset and Combination Problems\n\nWhen dealing with small sets (typically n ≤ 20-25), representing subsets as integers unlocks powerful iteration and manipulation patterns.\n\n**Signature characteristics:**\n- Enumerate all subsets or combinations\n- Check subset relationships (contains, overlaps)\n- Dynamic programming on subsets (Traveling Salesman, assignment problems)\n- Small, fixed-size universe of elements"},"type":"text"},{"data":{"fileName":"subset_enumeration","languages":[{"code":"$7e","label":"TypeScript","value":"typescript"},{"code":"$7f","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"### Category 3: Parity and Uniqueness Detection\n\nXOR's self-cancellation property makes it perfect for detecting odd-one-out elements and parity-related problems.\n\n**Signature characteristics:**\n- Find unique elements among duplicates\n- Detect missing or extra elements in sequences\n- Parity checks (even/odd occurrence counts)\n- Error detection in data transmission"},"type":"text"},{"data":{"fileName":"parity_detection","languages":[{"code":"$80","label":"TypeScript","value":"typescript"},{"code":"$81","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"### Category 4: Arithmetic and Mathematical Properties\n\nMany mathematical operations have efficient bitwise implementations, especially when dealing with powers of two or binary representations.\n\n**Signature characteristics:**\n- Operations involving powers of two\n- Modular arithmetic with power-of-two moduli\n- Division/multiplication by 2 (shifting)\n- Integer properties (even/odd, sign)\n- Range checks and bounds"},"type":"text"},{"data":{"content":"### Category 5: Low-Level System Operations\n\nWhen interfacing with hardware, network protocols, or file formats, bit manipulation is often *required*, not merely optimal.\n\n**Signature characteristics:**\n- Parsing binary file formats or protocols\n- Hardware register access\n- Network packet construction/parsing\n- Cryptographic operations\n- Compression and encoding algorithms"},"type":"text"}],"titleType":"number","titleNumber":2},{"id":"recognition-signals","title":"Recognition Signals: Keywords and Patterns","content":[{"data":{"content":"Beyond domain categories, certain keywords and structural patterns in problem statements signal bit manipulation opportunities. Training yourself to recognize these signals accelerates problem-solving in competitive programming and interviews.\n\n### Linguistic Signals in Problem Statements\n\nCertain words and phrases frequently appear in problems amenable to bit manipulation:"},"type":"text"},{"data":{"rows":[["\"exactly once\" / \"unique\"","XOR to cancel pairs","XOR reduction"],["\"appears twice\" / \"duplicates\"","Pairs cancel on XOR","XOR all elements"],["\"subset\" / \"combination\"","Represent as bitmask","Bitmask DP or iteration"],["\"power of two\"","n & (n-1) == 0 check","Bit count and properties"],["\"toggle\" / \"flip\"","XOR with mask","XOR operation"],["\"on/off\" / \"enable/disable\"","Set/clear bits","OR/AND with masks"],["\"without using arithmetic\"","Bit manipulation required","Bitwise add, XOR swap"],["\"maximize XOR\"","Greedy bit selection","Trie-based approach"],["\"reverse bits\"","Bit manipulation loop","Iterative or divide-conquer"],["\"binary representation\"","Direct bit access","Various bit operations"],["\"Gray code\"","Specific pattern needed","XOR with shifted value"],["\"Hamming distance\"","Count differing bits","XOR + popcount"]],"caption":"Problem Statement Keywords and Their Bitwise Implications","headers":["Keyword/Phrase","Bitwise Interpretation","Common Technique"]},"type":"table"},{"data":{"content":"### Structural Patterns\n\nBeyond keywords, certain problem structures strongly suggest bitwise solutions:\n\n**Pattern 1: Small Universe Size**\n\nWhen the problem involves a small, fixed set of elements (typically n ≤ 20-25), bitmask representation becomes viable.\n\n*Recognition:* Look for:\n- \"Given at most 20 elements...\"\n- \"The set contains up to N items where N ≤ 20\"\n- Constraints that conspicuously limit a parameter to small values"},"type":"text"},{"data":{"fileName":"small_universe_example","languages":[{"code":"$82","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"content":"**Pattern 2: Binary Properties of Numbers**\n\nWhen the problem asks about intrinsic properties of numbers that relate to their binary form.\n\n*Recognition:* Problems involving:\n- Even/odd classification\n- Leading/trailing zeros\n- Counting set bits\n- Highest/lowest set bit position\n- Numbers in specific ranges like [2^k, 2^(k+1))"},"type":"text"},{"data":{"content":"**Pattern 3: Pair Cancellation**\n\nWhen elements appear in pairs that should \"cancel out,\" leaving only anomalies.\n\n*Recognition:* Problems involving:\n- Finding the element that appears an odd number of times\n- Missing or duplicate detection in sequences\n- Comparing two similar but not identical sets\n- Parity checks"},"type":"text"},{"data":{"content":"**Pattern 4: State Space that Maps to Bits**\n\nWhen the problem's state can be naturally encoded as a bit vector.\n\n*Recognition:* Problems with:\n- Multiple boolean conditions\n- Visited/unvisited tracking for small sets\n- Configuration states with independent toggles\n- Games with cell states (lights out puzzle, etc.)"},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Constraint Hint","content":"Pay special attention to problem constraints. If n ≤ 20 is conspicuously specified, the problem designers are often hinting at O(2^n) or O(n·2^n) solutions using bitmasks. Similarly, if an operation must be done \"without extra space\" or \"in O(1) space,\" bit manipulation may be the intended approach.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"decision-framework","title":"A Systematic Decision Framework","content":[{"data":{"content":"Developing intuition takes practice, but a structured framework accelerates the learning process. Here's a systematic approach to evaluating whether bit manipulation is appropriate for a given problem:\n\n### Step 1: Analyze the Data Types and Constraints\n\n**Questions to ask:**\n- Are we dealing with integers, booleans, or elements from a small set?\n- What are the size constraints? Is n small enough for bitmask enumeration?\n- Are there powers of two appearing in the problem?\n\n**Bit-friendly indicators:**\n- n ≤ 20 for subset problems\n- Operations on integers up to 32 or 64 bits\n- Small alphabets (lowercase letters = 26 elements)\n- Fixed-size state spaces"},"type":"text"},{"data":{"content":"### Step 2: Identify the Core Operation\n\n**Questions to ask:**\n- What's the fundamental operation being repeated?\n- Can it be expressed as a bitwise operation?\n- Is there implicit parallelism that bit operations can exploit?\n\n**Map operations to bitwise equivalents:**"},"type":"text"},{"data":{"rows":[["Check if all conditions hold","AND with mask, compare to mask","(x & mask) == mask"],["Check if any condition holds","AND with mask, compare to 0","(x & mask) != 0"],["Toggle state","XOR with mask","x ^= mask"],["Set state to on","OR with mask","x |= mask"],["Set state to off","AND with complement","x &= ~mask"],["Check if power of two","AND with n-1","(n & (n-1)) == 0"],["Get lowest set bit","AND with negation","n & (-n)"],["Multiply by 2^k","Left shift by k","n << k"],["Divide by 2^k (unsigned)","Right shift by k","n >>> k"],["Modulo 2^k","AND with 2^k - 1","n & ((1 << k) - 1)"]],"caption":"Operation Mapping Reference","headers":["Logical Operation","Bitwise Equivalent","Condition"]},"type":"table"},{"data":{"content":"### Step 3: Evaluate the Alternative\n\n**Questions to ask:**\n- What's the non-bitwise approach?\n- How do they compare in time and space complexity?\n- Is the bitwise approach significantly better, or marginally so?\n- Is the code readability trade-off worth it?\n\n**Decision criteria:**\n- **Strong yes:** Bit manipulation provides an asymptotic improvement (e.g., O(n) vs O(n²))\n- **Moderate yes:** Same complexity but with significant constant factor improvement\n- **Weak yes:** Marginal improvement with good readability\n- **No:** Similar or worse performance with reduced clarity"},"type":"text"},{"data":{"content":"### Step 4: Consider Maintainability\n\n**Questions to ask:**\n- Will other developers understand this code?\n- Is this in a performance-critical path, or general code?\n- Can the bitwise logic be encapsulated in well-named functions?\n- Are there library functions that handle this more readably?\n\n**Pragmatic guidelines:**\n- In library/utility code: bit manipulation is acceptable with clear documentation\n- In application code: prefer readability unless performance is critical\n- In competitive programming: optimize freely (it's write-once code)\n- In interviews: show awareness of both approaches; ask interviewer preference"},"type":"text"},{"data":{"icon":"Target","title":"The Decision Flowchart","content":"**Ask in order:** 1) Is the problem naturally expressible in bits? → 2) Does bit manipulation provide meaningful benefit? → 3) Is the complexity justified for this context? If all three are yes, proceed with bit manipulation. If any is no, prefer the clearer alternative.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"classic-problem-types","title":"Classic Problem Types and Their Bitwise Solutions","content":[{"data":{"content":"Certain problem types appear repeatedly across interviews, competitive programming, and real-world systems. Recognizing these classics and their bitwise solutions builds a powerful problem-solving vocabulary.\n\n### Classic 1: Single Number Variations\n\n**Problem family:** Find the element(s) that appear a different number of times than others.\n\n**Variants and solutions:**\n- *Single number (others appear twice):* XOR all elements\n- *Single number (others appear three times):* Count bits mod 3\n- *Two single numbers:* XOR all, partition by differentiating bit\n- *Three single numbers:* More complex, typically uses different techniques"},"type":"text"},{"data":{"fileName":"single_number_thrice","languages":[{"code":"$83","label":"TypeScript","value":"typescript"},{"code":"$84","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"### Classic 2: Subset Sum and Partitioning\n\n**Problem family:** Divide or select elements based on sum constraints.\n\n**When to use bitmasks:**\n- When n is small (n ≤ 20)\n- When meet-in-the-middle applies (n ≤ 40, split into two halves)\n- When the state needs to track exactly which elements are chosen"},"type":"text"},{"data":{"content":"### Classic 3: Traveling Salesman and Assignment Problems\n\n**Problem family:** Visit all nodes exactly once with minimum cost.\n\n**Bitwise approach:** Bitmask DP where the mask represents visited nodes.\n\n**Recognition:** Small n (typically ≤ 20), need to track visited set, optimal substructure."},"type":"text"},{"data":{"fileName":"tsp_bitmask","languages":[{"code":"$85","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"content":"### Classic 4: Maximum XOR Problems\n\n**Problem family:** Find pair or subset with maximum XOR value.\n\n**Approach:** Use trie on bit representations, process bits from high to low.\n\n**Recognition:** Keywords like \"maximum XOR\", working with binary representations."},"type":"text"},{"data":{"content":"### Classic 5: Counting Bits in Ranges\n\n**Problem family:** Count set bits across a range of numbers.\n\n**Approach:** Use digit DP or mathematical formulas based on bit patterns.\n\n**Recognition:** Ranges [L, R], counting properties across many numbers."},"type":"text"}],"titleType":"number","titleNumber":5},{"id":"red-flags","title":"Red Flags: When Bit Manipulation Is Wrong","content":[{"data":{"content":"Equally important as knowing when to use bit manipulation is recognizing when it's *not* the right choice. Here are the warning signs:\n\n### Red Flag 1: Large or Unbounded Set Sizes\n\nBitmask approaches fail when the set size exceeds the integer width (typically 32 or 64 elements).\n\n**Warning signs:**\n- n can be up to 10^5 or 10^6\n- Set elements are not from a small, fixed universe\n- Constraints don't limit the set size\n\n**What to use instead:** Hash sets, balanced trees, or problem-specific data structures."},"type":"text"},{"data":{"content":"### Red Flag 2: Floating-Point Operations\n\nBit manipulation is for integers. Applying bitwise operations to floating-point at the bit level is almost never correct in high-level languages (and subtle even in low-level ones).\n\n**Warning signs:**\n- Problem involves real numbers\n- Results need decimal precision\n- Calculations involve division or roots\n\n**What to use instead:** Standard arithmetic, specialized numeric libraries."},"type":"text"},{"data":{"content":"### Red Flag 3: Readability-Critical Code\n\nIn production systems where maintainability matters more than micro-optimization, bit manipulation can be a liability.\n\n**Warning signs:**\n- Code will be read by junior developers\n- The bitwise approach saves minimal time\n- Clear alternatives exist with similar performance\n- The code isn't in a performance-critical path\n\n**What to use instead:** Explicit boolean arrays, named constants, or library functions."},"type":"text"},{"data":{"content":"### Red Flag 4: Signed Integer Complications\n\nBitwise operations on signed integers can produce unexpected results, especially right shifts and operations near the sign bit.\n\n**Warning signs:**\n- Working with potentially negative numbers\n- Right shifts that might propagate sign bits\n- Bit positions approaching the sign bit\n- Cross-language compatibility requirements\n\n**What to use instead:** Explicit handling, unsigned operations, or alternative algorithms."},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Cleverness Trap","content":"Bit manipulation can feel clever, and cleverness is seductive. But clever code is often fragile code. If you find yourself explaining your bitwise solution at length, that's a signal that a clearer approach might serve better. The best code is code that doesn't need explanation.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"practice-recognition","title":"Practice: Recognition Exercises","content":[{"data":{"content":"$86"},"type":"text"},{"data":{"icon":"CheckCircle","title":"Mental Checklist","content":"When you see a problem, quickly check: **1)** Small bounded set (n ≤ 20)? **2)** Boolean or toggle states? **3)** Uniqueness or parity? **4)** Powers of two or binary properties? **5)** Subset operations? If any apply, investigate bitwise approaches.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary","content":[{"data":{"content":"Recognizing when to apply bit manipulation is a meta-skill that distinguishes expert problem-solvers. We've covered:"},"type":"text"},{"data":{"type":"ordered","items":["**Fundamental advantages** — Representational efficiency, operational parallelism, and hardware proximity make bit manipulation powerful","**Domain categories** — Boolean flags, subset problems, parity detection, mathematical properties, and system operations are natural fits","**Linguistic signals** — Keywords like \"unique,\" \"toggle,\" \"subset,\" and \"power of two\" hint at bitwise solutions","**Structural patterns** — Small universe size, pair cancellation, and bit-mappable state spaces","**Decision framework** — Analyze constraints, map operations, evaluate alternatives, consider maintainability","**Classic problems** — Single number variants, subset sum, TSP, maximum XOR are recurring patterns","**Red flags** — Large sets, floating point, readability requirements, and signed integer complications"],"title":{"icon":"CheckCircle","text":"Key Recognition Skills","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's next:**\n\nNow that you can identify when bit manipulation applies, the next page explores how to leverage it for **space optimization**—one of the most practical applications in production systems where memory efficiency directly impacts cost and performance."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now have a systematic framework for identifying bit manipulation opportunities. The pattern recognition you've developed will serve you across competitive programming, technical interviews, and production engineering. Practice applying these recognition criteria to problems you encounter.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_1e8620f9b9f1b89cca684ed5af158ac1","title":"Space Optimization with Bits","order":1,"content":null,"isLocked":true},{"id":"seed_f1183405dc9646e425b61e868dbfb8b5","title":"Performance Considerations","order":2,"content":null,"isLocked":true},{"id":"seed_92aca2d0e7dde13e5d55cfebc83a5dab","title":"When Bit Manipulation Adds Complexity","order":3,"content":null,"isLocked":true}]}}