Swapping Techniques

Swapping refer to exchanging the contents of the variables. It is most important process in the programming. Generally, the sorting techniques use the swapping operations. When the information is very vast, we need some efficient sorting techniques to improve the speed of processing. You should use the swapping technique which has least time and space complexity in order to improve the speed of processing of the algorithms.
The generalized swapping technique that most software developers use it is have a temporary variable. For example:

if,
x = 12
y = 15

t = x
x = y
y = t

This will swap the contents of variables x and y. But, this technique wastes the extra memory in variable 't'. We can eliminate this by using the concept of addition and subtraction to swap the contents. For example:

x = x + y
y = x - y
x = x - y

Here, we are not using the temporary variable but three mathematical operations are required. This can be optimized by introducing the bitwise operation technique to swap the contents. The XOR operation will do the task for us. Let's see how this technique work.

You might be knowing the truth table of XOR operation.

x   y   x XOR y
0   0      0
0   1      1
1   0      1
1   1      0

The following operation will do the swapping.

x = x XOR y
y = x XOR y
x = x XOR y

Lets demonstrate it by simple example.

Let x = 12 and y = 15
means in digital or binary format, x = 1100 and y = 1111

so,

x = x XOR y = 1100 XOR 1111 = '0011'
y = x XOR y = 0011 XOR 1111 = '1100'
x = X XOR y = 0011 XOR 1100 = '1111'

So the final value of x and y are 1111 (15) and 1100 (12) respectively!

You may check this technique in C/C++/Java program by following operations.

int x = 12, y = 15;
x = x ^ y;  /* The ^ called as XOR operator */
y = x ^ y;
x = x ^ y;

These operations can be combined using assignment operator also. Such as,

x^=y^=x^=y;

Done.

tushar@tusharkute.com