Swaping two variables without using any temporary variable

It is a common belief that two variables can only be swapped by means of using a temporary variable. Interestingly this is not true !!!

There is a smart way of exchanging two variable without using any other temporary variable.  Here comes the explanation.

Given X and Y as two variables to be swapped, the following sequence of assignments swaps the X and Y at the end.

X = X XOR Y

Y = X XOR Y

X = X XOR Y

Proof:

First of all, let’s recall the truth table of XOR.

XOR Truth Table
INPUT OUTPUT
A B
0 0 0
0 1 1
1 0 1
1 1 0

As is shown on the table, the result of XOR operator is 1 unless the two operands are equal.

This clearly leads us to the following formulas.

X XOR 0 = X

X XOR X = 0

where X represent not only a boolean type variable but also integral type variables.  So let’s analyze the sequence of assignments.

Step 1) X = X XOR Y

After the first equation X holds the result of X XOR Y.

Step 2) Y = X XOR Y

The second equation can be broken down to the following assignments.

Y = (X XOR Y) XOR Y

or alternatively

Y = X XOR (Y XOR Y)

which is identical to

Y = X XOR 0

which is is identical to

Y = X

So at the end of the second equation Y holds the original value of X.

Step 3) X = X XOR Y

The last equation can be broken down to the following assignments.

X = (X XOR Y) XOR X

which is identical to

X = Y XOR (X XOR X)

which is identical to

X = Y XOR 0

which is identical to

X = Y

 At the end of the last assignment the variable X holds the original value of Y. That’s it !

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