by Frank Lin in Programming

2017-12-14 5 minutes to read 1 views 0 comments

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: $(A \oplus B) \oplus A = B$. For variables `a`

and `b`

, the XOR swap process is like follows:

- $a = a \oplus b$
- $b = b \oplus a = b \oplus (a \oplus b) = a$
- $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 swap

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

- $a = a + b$
- $b = a - b = (a + b) - b = a$
- $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 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.

## no comments yet