Bitwise XOR
XOR outputs 1 where inputs differ. Since x ^ x = 0, XOR-ing everything finds the un-paired element; it also swaps variables without a temp.
- Category
- Bit Manipulation
- Time complexity
- O(1)
- Space complexity
- O(1)
Pseudocode
for each bit position out = a XOR b x^x=0 → find the lone value
Reference implementation
10101100 (172)
^ 11001010 (202)
--------
01100110 (102)
# toggle; x ^ x == 0