Bit Manipulation

Use bitwise operations (XOR, AND, OR, shifts) to exploit integer-level properties and achieve O(1) space or constant-factor speedups.

Use bitwise operations (XOR, AND, OR, shifts) to exploit integer-level properties and achieve O(1) space or constant-factor speedups.

XOR is self-inverse: a ^ a = 0 and a ^ 0 = a. Accumulating XOR over all elements cancels every value appearing an even number of times, leaving only values with odd frequency.

Bitwise operations map to single CPU instructions — O(1) regardless of integer magnitude.

XOR cancellation solves the "single non-duplicate" class in O(n) time and O(1) space without any auxiliary structure.