XOR swap algorithm
Xor swap is a simple algorithm which uses the XOR operation to swap the values of two variables without using an extra variable. This algorithm follows (where X and Y are the names of two variables, rather than two values):
- XOR the value of X with Y and store the value in X
- XOR the value of X with Y and store the value in Y
- XOR the value of X with Y and store the value in X
To see how this works, call the initial value of X = x0 and the initial value of Y = y0. Then:
- after step 1, X = x0 XOR y0, Y = y0
- after step 2, X = x0 XOR y0, Y = x0 XOR y0 XOR y0 = x0
- after step 3, X = x0 XOR y0 XOR x0 = y0, Y = x0
This algorithm varies from other swap algorithms only in that it doesn't need to store the original value of X in a temporary buffer prior to overwriting it and doesn't need to restore this value in Y.