XOR Tricks

Iterating over all subsets of every subset of an `n`-element set sounds like `4^n` work. The actual cost is `3^n`: each element is in three states (in the outer mask only, in both, or in neither), and the binomial theorem collapses the sum. Insights like that turn what looks like a complexity wall into a tight, elegant solution. **Advanced Bit Manipulation** collects those insights. You will generate Gray codes (adjacent values differ by one bit, used in error correction), enumerate all subsets of a bitmask via the `for (s = mask; s > 0; s = (s - 1) & mask)` template, and master bit tricks like isolating the lowest set bit with `x & -x`, turning it off with `x & (x - 1)`, counting trailing zeros, and swapping without a temp variable. The lesson also covers advanced XOR applications (range XOR, two missing numbers, XOR basis over GF(2)) and bitwise DP including profile DP for grid tiling. In **Bit Manipulation (Intro)**, you mastered the basic operators and the single-number XOR trick. This lesson treats bits as a full algorithmic medium. Next, **Complexity & Proof Intuition (Optional)** revisits the theoretical foundations behind everything built so far.

Given an array where every element appears twice except one, find the loner. The hash-map solution is `O(n)` time and `O(n)` space. XOR-ing every element together solves it in `O(n)` time and `O(1)` space, in three lines, exploiting the fact that `a ^ a = 0` and `a ^ 0 = a`. Knowing how integers are laid out as bits unlocks solutions like that across an entire family of problems. **Bit Manipulation (Intro)** covers the building blocks. You will master the six bitwise operators (`&`, `|`, `^`, `~`, `<<`, `>>`) and the standard tricks: check whether `n` is a power of two with `n & (n - 1) == 0`, count set bits, get/set/clear/toggle the ith bit, and the XOR "single number" pattern. The lesson then introduces bitmasks as compact set representations and previews how subset enumeration powers later bitmask DP and TSP algorithms. In **How to Read Code (JS & Python)**, you saw integers and arithmetic. This lesson zooms in past arithmetic: the same integer is also a fixed-width string of bits you can address one at a time. Next, **Divide and Conquer (Intro)** returns to recursion with the recurrence framework that explains merge and quick sort.

Two players take turns removing stones from piles, the player who takes the last stone wins, and the entire winning strategy boils down to one calculation: XOR all pile sizes together, and you win if and only if the result is non-zero. That is Nim, and the surprise is not that it has a strategy but that the strategy is so compact. The Sprague-Grundy theorem extends the same idea to every impartial combinatorial game. **Game Theory** introduces the algorithmic side of two-player game analysis. You will work through Nim and its XOR strategy, then see how the Sprague-Grundy theorem assigns a Grundy number (nimber) to every position and how XOR-of-nimbers solves any sum of games. The lesson then moves to general game trees: minimax for optimal play, alpha-beta pruning for cutting branches that cannot affect the result, and move ordering for better pruning. You will analyze game states using DP, classifying positions as winning or losing by computing backward from terminal states, and meet retrograde analysis as a complete-game-state technique. In **Dynamic Programming (Intro)**, you learned to recurse on subproblems and cache results. **Recursion Fundamentals** gave you the call-stack model behind minimax and Grundy computation. Game theory recasts those tools as adversarial search. Next, **Randomized Algorithms** turns to a different way of taming worst-case inputs.