Ways to swap two numbers

_{^{From my old
blog.}}

Here are a few ways to swap two numbers. Just so that we know such ways do exist though using some of them may not be a good idea.

Swapping using a third variable

Probably the first way of swapping that any programmer encountered.

int a=10, b=20;

a = a + b;
// Now, a=30, b=20

// Like ((a+b) - b) which is a.
b = a - b;
// Now, a=30, b=10

// Like ((a+b) - a) which is b.
a = a - b;
// Now, a=20, b=10. Swap complete

First, the second value is added to the first value which leaves the sum of the two values in the first variable.

Then, second value is subtracted from the sum of values now stored in the first value, which will result in the original value of the first variable, and is assigned to the second variable. Here, the first step is complete and the second variable has the initial value of the first variable.

Next step is to subtract the current value of second variable (which is the initial value of first variable) from the sum of values present in the first variable which will result in the original value of the second variable. This value is now assigned to the first variable and the swap is complete.

Note that this can be made into a single line:

a = a+b - (b=a)

b = a+b - (a=b)

but that could be undefined behaviour in C as we are modifying a variable and using its value in the same expression.

(Source:https://stackoverflow.com/questions/18394609/how-to-swap-two-variables-in-one-line-in-c)

Multiplication and division

The principle behind the addition-subtraction way for swapping can be implemented using multiplication and division operators as well.

Overflows are likely and hence precautions must be taken. For example, when applied to integer values, the intermediate value would well be floating-point numbers.

float a = 10, b = 20;
a = a * b;
b = a / b;
a = a / b;

But for this to work, both values must be non-zero.

void swap(int *a, int *b)
{
    if(*a!=0 && *b!=0)  //Ensuring that both are non-zero
    {
        *a*=*b;
        *b = *a/(*b);
        *a/=*b;
    }
}

Using the bitwise XOR operator (^)

The bitwise XOR operation is its own 'inverse operation'.

int a = 10, b = 20;
a = a ^ b;
b = a ^ b;
a = a ^ b;

The underlying principle behind this method is same to that of the swapping done by addition and subtraction.

(Source: http://en.wikipedia.org/wiki/XOR_swap_algorithm )

Here's an example with a=1010₂=10₁₀ and b=0101₂=5₁₀ (¹)

|    x |    y | x ^ y | Assign to |
|------+------+-------+-----------|
| 1010 | 0101 |  1111 | → x       |
| 1111 | 0101 |  1010 | → y       |
| 1111 | 1010 |  0101 | → x       |

It’s just that XOR operation is its own inverse. That’s its specialty.

Usually, the trivial swap algorithm is more efficient as the compiler is smart enough to do the necessarily optimization.

Here, it should be noted that if we try to swap a variable with itself, the result would be incorrect. This is because if the variable is the same, swapping is attempted on the same memory. The first XOR operation would render the value of the variable to zero as any value xor-ed with itself would be zero.

So we better make sure that the two variables do not have the same address before swapping.

void (int *a, int *b)
{
    if(a != b) //Only if a and b are different addresses
    {
        *a = *a ^ *b;
        *b = *a ^ *b;
        *a = *a ^ *b;
    }
}

This could also be made into a single line:

a ^= b ^= a ^= b

but that too could invoke undefined behaviour in C as we are modifying a variable more than once before a sequence point. (Source: https://stackoverflow.com/a/18394679)

Swapping using a third variable

Multiplication and division

Using the bitwise XOR operator (^)

References: