Problem:Developing Algorithm to interchange of the values stored in two given variables.
The exchanging of the values between two given variables is commonly known as value “swap” and the process is known as “swapping”.This can be archived by various approaches. Below, we will discuss about two different approaches with a total of three processes, and see their benefits and pitfalls.
Article Index
- Introduction
- Algorithm 1 : Exchanging with three variables
- Algorithm 2 : Exchanging with two variables (Arithmetic)
- Algorithm 3 : Exchanging with two variables (Bitwise)
- Discussion
- Download Source Code
Introduction
If ‘a=5’ and ‘b=10’ The first idea which comes into mind (commonly in beginner ) is as below. But this is wrong
a=5; b=10; a=b; b=a
Let us discuss the problem with graphical example. We draw two boxes with the left box representing variable ‘a’ and the right box representing variable ‘b’. When the ‘a = b’ is executed the value at variable ‘a’ is overwritten by the value of ‘b’ and thus lost. Next, when ‘b = a’ gets executed it transfers the current value of a into ‘b’. The current value of ‘a’ is the initial value of ‘b’ (ie. 10). So at the end both the variables have the same value, so the swap operation fails. Diagram 1 shows this process graphically.
The above described process and the below diagram is wrong, it is just to clarify the common mistake and for better conception for the beginners.
Algorithm Discussion 1 (Three Variables)
We can see that the above method has failed. The main problem is that when performing the first operation ‘a=b’,the value of variable a is overwritten by the value at variable b, and is permanently destroyed,and now contains the same value as variable ‘b’. We need to develop such a process that the initial value of variable ‘a’ is preserved before we assign it with the value of variable ‘b’. We will now discuss this.
If we store the value of ‘a’, in a third temporary variable, before overwriting it with the value at variable ‘b’ the initial value at variable ‘a’ could be retrieved from the temporary variable, when we need to overwrite ‘b’. This will make this “swap” operation correct.
Let us introduce another third variable named ‘t’ which will represent the temporary variable.
First we store the value at variable ‘a’ into variable ‘t’. Second we overwrite the value at variable ‘a’ with the value at variable ‘b’. Third, we overwrite the value at variable ‘b’ with the value at variable ‘t’; which was actually the initial value of variable ‘a’. Thus the value of the variables ‘a’ and ‘b’ are interchanged. The operation sequence will be as described below.
int a,b,t; a=5; b=10; /* The interchange operations */ t=a; a=b; b=t;
This process is described graphically in Diagram 2. The striked out values out represents the variables which are overwritten. The values inside the arrows represent the values which are overwriting the values in the variables which the arrow points to.
Algorithm 1
Step1: Assign the initial value at variable 'a' into temporary variable 't' :
t = a
Step2: Assign the initial value of variable 'b' to variable 'a' :
a = b
Step3: Assign the value at temporary variable 't' to variable 'b' :
b = t
C Source Code
#include <stdio.h>
int
main (void)
{
int a, b, temp;
printf ("\nProgram to Swap two variables using 3 variables.");
printf ("\n\nEnter two variables (\"a\" and \"b\") seperated by a blankspace:");
scanf ("%d %d", &a, &b);
printf ("\n\nBEFORE Swap\n a=%d\tb=%d", a, b);
temp = a;
a = b;
b = temp;
printf ("\n\nAFTER Swap\n a=%d\tb=%d", a, b);
return 0;
}
Get the C implementation of Algorithm 1 Here
Two variable solutions are very popular and commonly asked at interviews and asked in exams. We will be discussing two Algorithms for 2 variable variations of swapping values between variables. But none of the two are reliable and has their limitations. The best way is to use the three variable method.
Algorithm Discussion 2 (Two Variables)
In Algorithm 1 we interchanged the values of two variables with the help of another third temporary variable. In this Algorithm 2 we will discuss how to achieve this interchange without the third variable. In this section we will algebraically to solve this problem.
By using simple addition and subtraction we will swap the values of two variables without any third variable. The processes are describer in detail below.
- We will at first store the sum of value at variable a and value at variable b into variable a. Step 1
a = a + b;
- Then we subtract the value at variable ‘b’ from the value at variable ‘a’ and store it to variable ‘b’. In the previous step a contains ‘a + b’. We substitute the current value at variable ‘a’ and notice that variable ‘b’ is now holding the initial value of variable ‘a’. The process in Step 2 describes the fact. Substitutions are in comments.
b=a-b; //where a=a+b b=(a+b)-b b=a
- Then we subtract the value at variable ‘b’ from the value at variable ‘b’ and store it to variable ‘a’. Substituting the current values of variable a and b which are ‘a + b’ and ‘a’ respectively we get Step 3. Substitutions are in comment.
a=a-b; //where a=a+b and b=a a=(a+b)-(a) a=b
After these three steps we notice that the values in the variables ‘a’ and ‘b’ are interchanged, as in Step 2 ‘b=a’ represents that the initial value of variable ‘a’ is transfered in variable ‘b’, and from Step 3 ‘b=a’ represents that the initial value of variable ‘b’ is transfered in variable ‘b’.
Let us take the example ‘a=5’ and ‘b=10’ and run the above three steps on them. The dry run is shown below.
| Step 1: | Current Values : a=5,b=10 Operation : a = 5 + 10 = 15 because (a=a+b) |
| Step 2: | Current Values : a=15,b=10 Operations : b = 15 – 10 = 5 because (b=a-b) |
| Step 3: | Current Values : a=15, b=5 Operations : a = 15 – 5 = 10 because (a=a-b) |
| Final Values : | a = 10, b = 5 |
Algorithm 2
Step1: Add value at variable 'a' with value at variable 'b'
and assign the total to variable 'b' : 'a = a + b'
Step2: Subtract value at variable 'b' from value at variable 'a'
and store the answer to variable 'b' : 'b = a - b'
Step3: Subtract value at variable 'b' from value at variable 'a'
and store the answer to variable 'b' : 'a = a - b'
C Source Code
#include <stdio.h>
int
main (void)
{
int a, b;
printf ("\nProgram to Swap two variables using 2 variables.");
printf ("\n\nEnter two variables (\"a\" and \"b\") seperated by a blankspace:");
scanf ("%d %d", &a, &b);
printf ("\n\nBEFORE Swap:\n a=%d\tb=%d", a, b);
a = a + b;
b = a - b;
a = a - b;
printf ("\n\nAFTER Swap:\n a=%d\tb=%d", a, b);
return 0;
}
Click below to get the source code
Get the C Implementation of Algorithm 2 Here
Other operators could also be used to achieve this interchange. Like the “*” (Multiplication) and the “/” (Division) operators could also be used as the Plus and the minus operator used in Algorithm 2 But while division the floating part gets lost and the number gets changed like 1.25 gets 1 as it looses the float part. While multiplying if the two numbers are big then the of the variable can overflow resulting in wrong result.
Algorithm Discussion 3 (Bitwise XOR Operator)
In this section we will discuss abut the “swapping” technique without the third temporary variable as used in Algorithm1 and use only two variables. Unlike in the previous algorithm Algorithm 2 we will not use the classical algebraic method. This approach would be with Boolean Algebra.
There are basically three boolean functions in Boolean Algebra,AND, OR and NOT, with which we can construct all other functions. In this technique we will need such a compound function, XOR function. Without going in details in other functions we will first discuss about the XOR function in brief.
If there are two binary digits or bits ‘x’ and ‘y’ and the XOR function is applied on them, then for all the four possible bit combination for the two values the function output will be as described in the truth table of XOR in Table 2
| x | y | f(Output) = x ^ b |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Where “^” is the Bitwise XOR operator in C Programming Language.
Do not mix it up with the exponent operator found in other programming languages.
In this table the variable f represents the result of the XOR operation of the two variables. As we can see the XOR function practically describes that whenever the two values of the variable, on which the function is being applied, are equal the output f will be 0. That is, when both the variables ‘x’ and ‘y’ are 1 or 0. On the other hand when the values of the variables are different, the output f will be 1. That is when the variables ‘x’ is ‘1’ and ‘y’ is ‘0’ or vice versa.
In the case, when the binary numbers will consist of two or more bits, we will apply the XOR function on each individual bit one by one and get the answer. For example if the two numbers are 11 and 10 in binary, then then the XOR function will first XOR the first bit of both the numbers and get the first bit of the result. Then it will XOR the second bit of both of the numbers and get the second bit of the result (SeeTable 3). Thus with ‘n’ bit numbers we will XOR the first bit of the first number with the first bit of the second number and get the first bit of the output, and proceed XOR ing between the second,third,fourth and up to nth bit of the two binary numbers and get the second,third,fourth, and up to nth of the output numbers. We interpret the string of output bits and get the XORed number.
| Operation: 11 ^ 10 | First Bit | Second Bit |
| First Binary Number (11) | 1 | 1 |
| XOR Operation (^) | ^ | ^ |
| Second Binary Number (10) | 1 | 0 |
| = | = | = |
| Output Number (01) | 0 | 1 |
Table 4 demonstrates the XOR Operation between one three bit number 100 and one 4 bit number 1101. To achieve this we add an extra 0 in the MSB position as to make it 4 bits long, then apply the previous method. In this case we get the output 1001 , this can be easily understood if the previous technique is followed and using the Truth table if XOR function (Table 2) if case of each bit operation.
| Operation: 0100 ^ 1101 | First Bit | Second Bit | Third Bit | Fourth Bit |
| First Binary Number (0100) | 0 | 1 | 0 | 0 |
| XOR Operation (^) | ^ | ^ | ^ | ^ |
| Second Binary Number (1101) | 1 | 1 | 0 | 1 |
| = | = | = | = | = |
| Output Number (1001) | 1 | 0 | 0 | 1 |
When we will apply the XOR function upon two integers in Decimal number system, it first gets converted into binary internally and then the XOR function is applied, as described above, and the answer is acquired, and converted in Decimal again. As an example if XOR function is applied upon two decimal numbers 5 and 3 then it will be as showed below in Table 5
| Operation: 5 ^ 3 | Decimal Number | Binary Equivalent | First Bit | Second Bit | Third Bit |
| First Number | 5 | 101 | 1 | 0 | 1 |
| XOR Operation | ^ | ^ | ^ | ^ | ^ |
| Second Number | 3 | 011 | 0 | 1 | 1 |
| = | = | = | = | = | = |
| Output Number | 6 | 110 | 1 | 1 | 0 |
At first 5 and 3 are converted into binary equivalents and then applied XOR function and after acquiring the XOR value in Binary, it as again converted into Decimal.
As per boolean algebraic theorems it can be proved that ‘a ^ b = b ^ a’ , also ‘a ^ a = 0’ or ‘b ^ b = 0’ (it can also be easily be seen without need of any proof). In C Programming Language the “^” represents the XOR Operator (Implemented as ‘a^b’), As in other programming languages this operator stands for the power, but is C there is no power operator, and this operator is used as the bitwise XOR operator.
But what is how would we use this operator to interchange the values between two variables? An operation sequence with the XOR operation to interchange values between two variables is described below and then discussed in detail how it works.
Algorithm Discussion
- The XOR function is implemented between two variables ‘a’ and ‘b’, and the answer of the ‘XOR’ operation is assigned into variable ‘a’. (Which overwrites the initial value at variable ‘a’). That is ‘a = a ^ b’
/* The Operation */ a = a ^ b;
- The XOR operation is implemented between variables ‘a’ and ‘b’, again, and the answer of the XOR operation is assigned into variable ‘b’. That is ‘b = a ^ b’. Variable ‘a’ contains the value of ‘a ^ b’ (from Step 1), so the operation ‘a ^ b’ is practically ‘b = ( a ^ b ) ^ b’ after substituting ‘a’ with it’s new value ‘a ^ b’ (from Step 1). Solving ‘b = ( a ^ b ) ^ b’ we get ‘b = a’ . Step 2 is shown with the substitutions of each variable in comments.
/* The Operation */ b = a ^ b; /* Substitution */ b = ( a ^ b ) ^ b; //because a = a ^ b b = a ^ 0; b = a;
- Next the XOR operation is implemented between variables ‘a’ and ‘b’, for the third and the last time, and the answer is assigned into variable ‘a’. That is ‘a = a ^ b’. Currently variable ‘b’ contains the initial value of variable ‘a’ and, variable ‘a’ contains value of ‘a ^ b’. So the operation ‘a = a ^ b’ is practically ‘a = ( a ^ b ) ^ a’ after substituting with the current values variable ‘a’ and ‘b’. Step 3 is shown with the substitutions of each variable in comments.
/* The Operation */ a = a ^ b; /* Substitution */ a = ( a ^ b ) ^ a; //because a = a ^ b and b = a a = b ^ 0; a = b;
After these steps we can see that the final values of variable ‘a’ and ‘b’ are interchanged. (a=b and b=a proofs it). Let us take the example of ‘a=5’ and ‘b=3’ and apply these steps on them and see the results.
| Step 1: | Current Values : a = 5, b = 3 Operation : a = 5 ^ 3 = 6 from ( a = a ^ b) |
| Step 2: | Current Values : a = 6 , b = 3 Operation : b = 6 ^ 3 = 5 from (b = a ^ b) |
| Step 3: | Current Values : a = 6, b = 5 Operation : a = 6 ^ 5 = 3 (a = a ^ b) |
| Final Values : | a = 3 , b = 5 |
Algorithm 3
Step1: Apply OR function between variables 'a' and 'b'
and store the XOR output into variable 'a' : 'a = a ^ b'
Step2: Apply XOR function between variables 'a' and 'b'
and store the XOR output into variable 'b' : 'b = a ^ b'
Step3: Apply XOR function between variables 'a' and 'b'
and store the XOR output into variable 'a' : 'a = a ^ b'
Where “^” is the bitwise XOR operator.
C Source Code
#include <stdio.h>
int
main (void)
{
int a, b;
printf ("\nProgram to Swap two variables using 2 variables and bitwise XOR Operator.");
printf ("\n\nEnter two variables (\"a\" and \"b\") seperated by a blankspace:");
scanf ("%d %d", &a, &b);
printf ("\n\nBEFORE Swap:\n a=%d\tb=%d", a, b);
a ^= b;
b ^= a;
a ^= b;
printf ("\n\nAFTER Swap:\n a=%d\tb=%d", a, b);
return 0;
}
Get the C Implementation of Algorithm 2 Here
Discussion
Two variable methods are very popular in the beginners who are tempted to use them in the code. The two variable methods has very much limitations, and actually internally the two variable method uses the third variable.
Algorithm 2: In this method we have used arithmetic operators. When we add the two numbers, the result of the addition can overflow the limit of the variable’s range and come out with wrong results. For an example let us consider 2byte integers, which have a limit 32767. Now if ‘a = 10’ and ‘b = 32760’ , then executing the first operation ‘a = a + b’ will make an overflow and instead of 32770 ‘a’ will contain -32766. Same will be the case when “*” and “/” operators are used, in this case the overflows will occur for even lower values and divide by zeros can occur.
Algorithm 3: In this method we have used the bitwise XOR operators. This will only work with integer variables, this is because bitwise operators are only defined for integer values and will only work on them. Results when using this method on char, long int, or short int is compiler dependent and might draw undefined behaviour. This method is far better than Algorithm 2, when used on integer variables.
Although we think we are saving some bytes of memory, a temporary variable is used internally when executing Algorithm 2 and 3.
Note another thing: The two variable methods needs three transfer operations and 3 arithmatic or bitwise operations, where the three variable method needs only three transfer operation, so the three variable method will be faster than the two variable method. Many applications like sorting, uses swapping, and it has to be done a huge number if time. Like if the swap operation is done 1000000000 times then the two variable versions take twice the time than the three variable version (when compiled without the -O tags).
Phoxis 
excellent ……..