Code Tricks: Swapping values without a third variable

The classic way to swap two values in most languages (C code shown) is by means of using a temporary third variable. For example:

void swapBYtemp(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

Python supports parallel assignments of the form:

a, b := b, a

Swapping can also be achieved without the use of a temporary variable in at least two other ways: (i) XOR swap, and (ii) arithmetic swap.

Bitwise XOR

In the first case, swapping using bitwise XOR, for example if a = 2 (010), and b = 4 (100)

a = a XOR b = 010 XOR 100 = 110
b = b XOR a = 100 XOR 110 = 010
a = a XOR b = 110 XOR 010 = 100

The associated C code would look like:

void swapBYbit(int *a, int *b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

The use of this technique in swapping values is limited to [embedded] situations where memory may be extremely constrained, however in most cases bitwise XOR may be more expensive than the traditional swap.

Arithmetic swap

The second case involves swapping by using arithmetic, of which are are two forms. The first form involves the use of addition and subtraction:

void swapBYmath1(int *a, int *b)
{
    *a = *a + *b;
    *b = *a - *b;
    *a = *a - *b;
}

The second form involves multiplication and division:

void swapBYmath2(int *a, int *b)
{
    *a = *a * *b;
    *b = *a / *b;
    *a = *a / *b;
}

Note that swapBYmath2 does not work if one of the numbers to be swapped has the value 0, as the result of the first line of code will result in a zero. Both these methods may also result in some form of arithmetic overflow, if large enough numbers are being swapped.

Caveats

If an attempt it made somewhere in an algorithm to swap two variables that point to the same memory location, the methods that don’t use a third variable will fail. For example for bitwise XOR swap, if the addresses are equal, the algorithm will fold to a triple *x ^= *x resulting in zero. So if you are going to incorporate these algorithms in your code, make sure to add some defensive programming.

void swapBYmath1(int *a, int *b)
{
    if (*a == *b)
        return ;
    *a = *a + *b;
    *b = *a - *b;
    *a = *a - *b;
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s