XOR cancels duplicates (a ^ a = 0), useful for "find the unique element" problems. n & (n-1) clears the lowest set bit, useful for counting bits or checking powers of 2.
Sub-patterns
- A — XOR Tricks. Cancellation and toggling.
- B — Bit Counting. Counting set bits efficiently.
- C — Subset Generation via Bitmask. Enumerate all subsets by iterating bitmask values.
- D — Single-Number Family. Find the element(s) that don't repeat, using XOR or bit-counting.
Practice set (9)
- Easy — Single Number, Number of 1 Bits, Counting Bits, Missing Number, Power of Two
- Medium — Single Number II, Single Number III, Sum of Two Integers, Maximum XOR of Two Numbers in an Array
Pending
XOR Tricks
Cancellation (a ^ a = 0) and bit-toggling tricks.
Pending
Bit Counting
Count set bits efficiently, e.g. via n & (n-1) to clear the lowest set bit.
Pending
Subset Generation via Bitmask
Enumerate all subsets of a set by iterating every bitmask value from 0 to 2^n - 1.
Pending
Single-Number Family
Find the element(s) that don't repeat, using XOR cancellation or per-bit counting.
Notes from readers
Comments — via GitHub