site logo

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: (AB)A=B(A \oplus B) \oplus A = B. For variables a and b, the XOR swap process is like follows:

  1. a=aba = a \oplus b
  2. b=ba=b(ab)=ab = b \oplus a = b \oplus (a \oplus b) = a
  3. a=ab=(ab)a=ba = 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 AA=0A \oplus A = 0.

Add swap

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

  1. a=a+ba = a + b
  2. b=ab=(a+b)b=ab = a - b = (a + b) - b = a
  3. a=ab=(a+b)a=ba = 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.

swap xor tricks