Bit Manipulation
Treat integers as arrays of bits and use AND, OR, XOR, and shifts to solve counting and set problems in constant space.
Key ideas
- —XOR cancels equal values, so a ^ a == 0 — perfect for finding lone elements.
- —x & (x - 1) clears the lowest set bit; iterate to count or strip bits.
- —Bitmasks represent subsets compactly: bit i set means element i is included.
XOR as a cancellation tool
XOR is its own inverse: a value XORed with itself vanishes, and XOR is commutative, so order does not matter. XOR the whole array and every duplicated value cancels, leaving the single unpaired number. The same property recovers a missing value when you XOR the full expected range against what is present.
Masks and the lowest set bit
The idiom x & (x - 1) removes the lowest set bit, so counting set bits becomes a loop that runs once per set bit rather than once per bit width. Bitmasks also let a single integer stand in for a subset of up to ~30 elements, which is how subset-enumeration and bitmask DP keep state cheap.
Practice this
Sources
- Bitwise operationWikipedia
- Bitwise AND (&)MDN