Work directly on the binary form of numbers with AND, OR, XOR and shifts. These are the fastest operations a CPU has.
Used for
0 ^ 4 = 4
4 ^ 1 = 5, 5 ^ 2 = 7
7 ^ 1 = 6, 6 ^ 2 = 4
What is 6 ^ 6?
Not quite. XOR gives 0 whenever the bits match, so any number XOR itself is 0. That is why pairs cancel.
Step 1 of 5
Goal: every number appears twice except one. Find the odd one out without extra memory. Trick: the XOR operation (^) turns two equal numbers into 0, and anything XOR 0 stays itself. So XOR everything together and the pairs vanish.
Step 2 of 5
Start with 0. Then 0 ^ 4 = 4.
Step 3 of 5
4 ^ 1 = 5, then 5 ^ 2 = 7.
Step 4 of 5
7 ^ 1 = 6, then 6 ^ 2 = 4. The 1s and 2s cancelled each other out. The answer is 4, in one pass with no extra memory. Working directly on the bits of numbers is bit manipulation.
Step 5 of 5
Your turn.
Binary representation of floating-point numbersBit ManipulationIs a power of two
const single = nums => nums.reduce((a, b) => a ^ b, 0); // pairs cancel under XOR