Swapping variables without additional space

Swapping variables is a very common operation used it tons of algorithms like sorting etc. The most common and obvious technique is using of a temporary variable to swap values between two variables

void swap(int &i, int &j)
{
   int temp = i;
   i = j;
   j = temp;
}

Instead of writing a separate function for each data type, you could write a MACRO or templatize the function.

Swapping without using a temporary variable is an age old trick and there are a few ways to do this. You could use of the basic arithmetic operations like +,-,/,*

1: void swap(int &i, int &j)
2: {
3:     i=i+j;
4:     j=i-j;
5:     i=i-j;
6: }

The technique involves storing the sum of variables in one of them and then extracting it back by subtracting the other number. There are different variants to this technique. E.g, instead of starting by storing the sum, you could store the difference, product or the quotient. The last two could lead you to round-off and integer division errors. However all of them have one fundamental flaw. Its in line 3, and the issue is that this could lead to an overflow error.

This is another technique the gets you around these issues; the XOR Swapping technique

void swap(int &i, int &j)
{
     i = i ^ j;
     j = j ^ i;
     i = i ^ j;
}

This is an elegant technique and should work well with any primitive data type and you could write a simple MACRO like

#define SWAP(i, j) (((i) ^= (j)), ((j) ^= (i)), ((i) ^= (j)))

Although, the XOR technique gets rid of the other issues like overflow and round off errors that we encountered in the previous technique, the lands in into yet another issues; This does not work when you try to swap the same memory location. However if can get around this by a simple ‘if’ check or a more elegant OR check like

#define SWAP(i, j) ( (i==j) || ((i) ^= (j)), ((j) ^= (i)), ((i) ^= (j)))

The first OR condition (i == j) is checked before the actual SWAP. (You do not need a SWAP if the both memory locations hold the same data)