How to Swap Two Variables Without a Third Variable?

Everett Gaius's picture
Submitted by Everett Gaius on Fri, 04/10/2020 - 09:37

One of the most common whiteboarding questions is "Swapping of two (2) integers without using a third variable". The objective is not to optimize the standard way of swapping variables but rather to show the resourcefulness of the applicant given problems with constraints. Because in real life, you'll face challenges where you have to work on projects with limited resources.

But how do we approach this problem? The computer operations available are:

  • declaration and assignment
  • logic operations
  • control flow
  • arithmetic operations
  • other complex operations

Since the problem is about integers, we will use declaration, assignment, and arithmetic operations.

If we have two integer variables (int a_ and int b_), assigning one to the other will immediately result in a bug!

If we use arithmetic operations like add, subtract or multiply, the output must be stored somewhere. That output cannot be stored in another location aside from a_ or b_. Storing the result in a_ or b_ essentially combines the output of operation performed on a_ and b_. We will combine a_ and b_ for now and hope that we can swap their values in the process of separating them.

COMBINE OPERATION:

The basic idea is:

Let a_ = combine_function(a_, b_)

There are several functions to combine two integer values. We can use simple arithmetic operations or we can also choose complex functions such as type casting integer to string. Let's go for the simpler solution and perform an add operation.

 a_ = a_ + b_;

 

UNDOING THE COMBINE OPERATION:

If we have a_ = 3 and b_ = 5, performing the add operation will make the new value of a_ = 8. Remember that a_ = old_value_of_a_ + b_ (8 = 3 + 5). Using Algebra, we do a_ - b_ to get the old_value_of_a. We will assign the result of this expression to b_.

 b_ = a_ - b_;

As you may have observed, the new value of b_ is now the old_value_of_a_. We will repeat the same method for a_ to get the old_value_of_b_;

 a_ = a_ - b_;

 

The problem with arithmetic operators like add is they may tend to overflow. To show how it overflows, let us suppose that a_ and b_ are unsigned 8-bit integers with initial values of 255 and 1, respectively. Adding these two numbers and assigning the result to a_ will make it zero.

An alternative combine function that does not overflow is the xor function. As we all know from Boolean Algebra, xor results in 1 if the operands are 0 and 1 or vice-versa, and results in 0 if the operands are both 0 or both 1. This observation allowed us to combine, extract and swap  the values of a_ and b_ as shown below: 

 

 		value	128	64	32	16	8 	4 	2 	1
a_		73 	0	1 	0 	0 	1 	0 	0 	1
b_ 		40 	0	0	1 	0 	1 	0 	0 	0
a_ ^= b		97 	0 	1 	1 	0 	0 	0 	0 	1
b_ ^= a 	73 	0	1 	0 	0 	1 	0 	0 	1
a_ ^= b 	40 	0	0	1 	0 	1 	0 	0 	0

 

Below is the C/C++ implementation of XOR Swap.

 int a_ = 3, b_ = 5;

a_ = a_ ^ b_;
b_ = a_ ^ b_;
a_ = a_ ^ b_;

 

Important Note: If the interviewer does not constraint you and asks only for a normal swap, just do it with a third variable.

 

 int a_ = 3, b_ = 5, t_;

t_ = a_;
a_ = b_;
b_ = a_;

 

This method is faster since the operations required to perform assignments have fewer clock cycles than add, subtract, and xor.

Tags: