Bit Tricks
XOR pairing, masks as sets, n & (n-1), two's-complement tricks.
1 min readInterview · DSA Patterns
A small toolbox of bit-level tricks that show up in interview problems where the input is "numbers" but the algorithm is really about the bits.
Finished reading?
Mark it done to track your progress in Interview.
DP — Bitmask
Use bits as a "set of used elements." dp[mask] iterates over 2^n states. The pattern for TSP, assignment problems, shortest-path-visiting-all-nodes, and "which subset have I taken" problems.
Bit Manipulation
XOR for pairing/cancellation, n & (n-1) for popcount and lowest-bit-clear, masks-as-sets for subset enumeration. A small toolbox that unlocks elegant O(n)/O(1) solutions for a specific class of problems.