XOR Swap Explained Visually
Nov 04, 2018
A common riddle-like question for programmers asks them to swap the values of two integers without a temporary intermediate value. There are two common solutions that I'm aware of, addition swap and XOR swap. Here's what each looks like in C:
void addSwap (unsigned int *x, unsigned int *y) {
if (x != y) {
*x = *x + *y;
*y = *x - *y;
*x = *x - *y;
}
}
void xorSwap (int *x, int *y) {
if (x != y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
}
Credit: https://en.wikipedia.org/wiki/XOR_swap_algorithm
The more interesting of the two is XOR swap. It only uses a single operation, rather than addition and subtraction in addition swap. Wikipedia tries to explain this with bit vectors but I think 1 bit black and white images work better. In the images below, black corresponds to 0
and white corresponds to 1
.
A = A ^ B
:
A | B | = A |
---|---|---|
![]() |
![]() |
![]() |
B = B ^ A
:
A | B | = B |
---|---|---|
![]() |
![]() |
![]() |
A = A ^ B
:
A | B | = A |
---|---|---|
![]() |
![]() |
![]() |
Here's the code used to generate the images above:
import sys
from PIL import Image
a = Image.open("A.png")
b = Image.open("B.png")
if not a.size == b.size:
print("Images must have the same dimensions")
sys.exit(1)
if not a.mode == b.mode:
print("Images must be the same mode")
sys.exit(1)
result = bytes([
a.getpixel((x, y))[0] ^ b.getpixel((x, y))[0]
for y in range(a.size[1])
for x in range(a.size[0])
])
Image.frombytes("P", a.size, result).save("OUT.png")