May 18, 2010

Swap variables interview question

By Mohammed Abualrob Algorithms and Data Structures 0 Comments

Swapping two variables without a temp

Given two integer variables A and B. Write C++ code to swap them without using a temporary variable.

Solution

This is a well known problem for which you can find so many references on the Internet. One way to do that is to use addition and subtraction as follows:

B = B + A
A = B - A
B = B - A

B = B + A

A = B - A

B = B - A

This is more than enough to do the job. We are using one of the variables for temporary storage instead of a separate temporary variable. Let us try to trace the code and see how it does the job:

1. B = B + A
2. A = B - A = (B + A) - A = B
3. A = B
4. B = B - A = (B + A) - (B) = A
5. B = A

1. B = B + A

2. A = B - A = (B + A) - A = B

3. A = B

4. B = B - A = (B + A) - (B) = A

5. B = A

There is a drawback of this solution however. If B + A overflows B then it is not going to work.

Solution

Another solution that does not suffer from the overflow problem is using XOR bitwise operations as
follows:

A = A XOR B
B = A XOR B
A = A XOR B

A = A XOR B

B = A XOR B

A = A XOR B

Similarly let us try to see how the the chain of XOR operations does the job.

0.  A                      :  B
1.  A XOR B                :  B
2.  A XOR B                : [A XOR B] XOR B  = 
                              A XOR [B XOR B] = 
                              A XOR 0         = 
                              A
3. [A XOR B] XOR A  = 
    A XOR [A XOR B] = 
   [A XOR A] XOR B  = 
    0 XOR B         = 
    B                     :   A

0. A : B

1. A XOR B : B

2. A XOR B : [A XOR B] XOR B =

A XOR [B XOR B] =

A XOR 0 =

3. [A XOR B] XOR A =

A XOR [A XOR B] =

[A XOR A] XOR B =

0 XOR B =

B : A

Although it looks confusing a little bit we did nothing but substitution.

Swapping variables in c++

Here is an example C++ code that implements swap two variables algorithm:

//Includes
#include <iostream>

using namespace std;
 
int main ()
{
   //Define variables
   int x = 1;
   int y = 2;
   int t = 0;

   //Normal way using temporary variable
   t = x;
   x = y;
   y = t;
   cout << "x = "<< x << " y = " << y << endl;

   //Restore values
   x = 1;
   y = 2;

   //Using addition and subtraction
   y = y + x;
   x = y - x;
   y = y - x;
   cout << "x = "<< x << " y = " << y << endl;

   //Restore values
   x = 1;
   y = 2;

   //Swapping variables using XOR operations without a third
   x ^= y;
   y ^= x;
   x ^= y;
   cout << "x = "<< x << " y = " << y << endl;

   return 0;
}

//Includes

#include <iostream>

using namespace std;

int main ()

{

//Define variables

int x = 1;

int y = 2;

int t = 0;

//Normal way using temporary variable

t = x;

x = y;

y = t;

cout << "x = "<< x << " y = " << y << endl;

//Restore values

x = 1;

y = 2;

//Using addition and subtraction

y = y + x;

x = y - x;

y = y - x;

cout << "x = "<< x << " y = " << y << endl;

//Restore values

x = 1;

y = 2;

//Swapping variables using XOR operations without a third

x ^= y;

y ^= x;

x ^= y;

cout << "x = "<< x << " y = " << y << endl;

return 0;

}

If you have questions or comments, please use the comments section below. Thanks for visiting.

8 BIT AVENUE

Swap variables interview question

More from my site

About Author

Mohammed Abualrob

Add a Comment