### Fast Swap Values Between Two Variables in C

by Miroslaw M. Soja

First Published: September 1

^{st}, 2002

At the beginning there was a swap() ...

Most of beginner programmers and computer science students face a simple problem: how to swap two numerical variables? In most cases, course's books and instructors suggest a following solution:

void swap(int *a, int *b)

{

int temp ;

temp = *a ;

*a = *b ;

*b = temp ;

}

For the educational purposes, the mentioned function swap() serves well in order to educate future champions in computer science. However, the computer programming industry is not the University - the industry requires that people must think harder.

In other words, the function swap() has a problem - each time when the function is invoked, it must create (a time expensive process) a temporary variable the int temp. In spite of the fact that today's computers are relatively fast, it still could be a problem - especially, when the real time system requires to invoke the process of swapping in a large scale.

In reply to the challenge, one could propose a solution: the int temp must be declared as a static variable - it eliminate the time for creating temporary variable in a computer memory. It is great! Yahoo! But... unfortunately, this solution is only good for students who want to get some bonus points on an exam as a reward for their smart suggestion.

Real World Challenges Academic swap()

Real life is more difficult and full of surprises! Therefore, the real problem is finding answer to the following question: Can we swap two values without any additional variable used as a temporary storage?

For a small group of industrial programmers the answer is obvious - it means, YES! And the solution is extremely simple -- when I learned about the solution for the first time, I was amazed with its simplicity and beauty.

XOR Logic and its Beauty

The new code for swap() is following:

void swap(int *a, int *b)

{

*a ^= *b ;

*b ^= *a ;

*a ^= *b ;

}

XOR -- How Does it Work?

The entire secret is in a property of XOR - the logical operation. The XOR has following logic:

0 XOR 0 = 0

1 XOR 1 = 0

1 XOR 0 = 1

0 XOR 1 = 1

In order to illustrate the method used in function swap(), let us consider two integer numbers x and y in binary form:

x = {0011} and

y = {1001}

Let us perform the first operation: x= x XOR y (which is equivalent of *a ^= *b )

x = x XOR y = {0011} XOR {1001} = {1010}

The value {1010}, from the XOR perspective, carries information about two numbers: {0011} and {1001}

Next, y = x XOR y (or *b ^= *a ),

Please note: the current value of x is {1010}!

y = x XOR y = {1010} XOR {1001} = {0011}

At this moment y value became the original value of x !

Finally, x = x XOR y (or *a ^= *b ),

x = x XOR y = {1010} XOR {0011} = {1001}

Therefore x value became the original value of y !

Conclusion

The logical operation XOR is amazing - it can create a new result number by merging two other initial numbers. At the same time, XOR is capable to restore from the result number one of the initial numbers using another one.

Return to the List

I support the following technologies:

and so on...