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;

Answer 1

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.

Answer 2

It converts them to binary first then performs a bitwise operation.

So

a =  5 = 0000 0101
b = 10 = 0000 1010

Then XOR is performed bit by bit, i.e.

a^b = 0000 1111

(or 15).

Performing XOR bit by bit means doing the boolean XOR (that you already understand) on each bit in the number. So use the truth table to compare the first digit of a with the first digit of b, then compare the second digit of a with the second digit of b, and so on.

Follow this logic through to get:

int a = 5; int b = 10;

a = a ^ b; // a = 1111 = 15

b = a ^ b; // b = XOR (1111, 1010) = 0101 = 5

a = a ^ b; // a = XOR (1111, 0101) = 1010 = 10

Answer 3

XOR is a bitwise operator, so your numbers are XORed bit-by-bit, for example

5 = 4+1 = 0101 
10 = 8+2 = 1010

For booleans, it is well known, that a xor b xor b = a. Simply apply it bit by bit and you get the swapping of numbers (or any other data represented as bits, so pretty much everything in computer science).

Answer 4

Bitwise operators process all the bits in a variable independently.

For example:

5=0101
8=1000

5|8=
0101
1000
=
1101

5&8=
0101
1000
=
0000

5^8=
0101
1000
=
1101

etc

This is as compared to operators such as +, -, ||, && which work on the full value of a variable.