How does the XOR (^) swap algorithm work?

Question

Here is a way of swapping a and b without a need for a third variable. I understand what XOR means in a truth table with "true" or "false" but what is it doing here exactly? How does XOR work when we're dealing with numbers not booleans? ``` int a = 5; int b = 10; a = a ^ b; b = a ^ b; a = a ^ b; ```

Accepted Answer

The operation happens bitwise, once for each bit in the binary encoding of each number.

Have you ever played the game "Lights Out"? Each light is either on or off, and each button press swaps (XORs) a pattern of them. If you press the button a second time, the same swap changes the pattern back. The same thing is true if you press a combination of buttons. The same combination of buttons will change it back - the order does not have to be the same.

This same behavior happens in the game and also in bitwise operations on a variable. When you XOR two variables together, the bits in one are used to toggle the bits in the other. Due to the nature of this change, it doesn't matter which one is doing the toggling on which - the results are the same. The same bit in the same position in both numbers yields a 0 in that position in the result. Opposite bits yields a 1 in that position.

```
a = a ^ b;
```

`a` is now set to the combined bitmask of a and b. `b` is still the original value.

```
b = a ^ b;
```

`b` is now set to the combined bitmask of (a XOR b) and b. The b's cancel out, so now `b` is set to the original value of `a`. `a` is still set to the combined bitmask of a and b.

```
a = a ^ b;
```

`a` is now set to the combined bitmask of (a XOR b) and a. (remember, `b` actually contains the original value of `a` now) The a's cancel out, and so `a` is now set to the original value of `b`.

How does the XOR (^) swap algorithm work?

Solution

Problem