In-place swap is just a logic trick used to swap a content of two distinct variables without any temporary storage variable.

XOR swap

The most common way of in-place swap uses XOR operation. It’s based on the XOR property¹:

For variables a and b, the XOR swap process is like follows:

1. $$a = a \oplus b$$
2. $$b = b \oplus a = b \oplus (a \oplus b) = a$$
3. $$a = a \oplus b = (a \oplus b) \oplus a = b$$

void xorSwap(int *a, int *b) {
    if (a != b ) {
        *a = *a ^ *b; // a = a XOR b
        *b = *b ^ *a; // b = b XOR (a XOR b) = a
        *a = *a ^ *b; // a = (a XOR b) XOR a = b
    }
}

When using the XOR swap, we have to make sure the variables are distinct, otherwise the first step of the algorithm could erase the memory, as $A \oplus A = 0$.

Add/sub swap

Another way of in-place swap uses simple addition and subtraction:

1. $$a = a + b$$
2. $$b = a - b = (a + b) - b = a$$
3. $$a = a - b = (a + b) - a = b$$

void addSwap(int *a, int *b) {
    if (a != b) {
        *a = *a + *b; // a = a + b
        *b = *a - *b; // b = a - b = (a + b) - b = a
        *a = *a - *b; // a = a - b = (a + b) - a = b
    }
}

Add swap can be used only in certain languages, in which the addition operation will never cause the integer overflow exception.

Computation details

How does this work on CPU-level?

The computer actually has an implicit “temp” variable that stores intermediate results before writing them back to a register. For example add 3 to a register:

ADD 3 A // add 3 to register A, in machine-language pseudocode

The ALU² is actually executes the instruction 3 + A. It takes the inputs and creates a result, which the CPU then stores back into A’s original register. So, we used the ALU as temporary scratch space before we had the final answer. In a similar way, the ALU can return the intermediate result of the XOR in the case of a = a ^ b, then the CPU stores it into a’s original register.

Would you really use this?

This is a cool trick, but don’t write this as an actual swap function, it doesn’t boost the performance and has a very low readability.