One of the very tricky questions asked in an interview.
Swap the values of two variables like a=10
and b=15
.
Generally to swap two variables values, we need 3rd variable like:
temp=a; a=b; b=temp;
Now the requirement is, swap values of two variables without using 3rd variable.
Given two variables, x, and y, swap two variables without using a third variable. The idea is to get a sum in one of the two given numbers. The numbers can then be swapped using the sum and subtraction from the sum.
Using the xor swap algorithm
void xorSwap (int* x, int* y) { if (x != y) { //ensure that memory locations are different *x ^= *y; *y ^= *x; *x ^= *y; } }
Why the test?
The test is to ensure that x and y have different memory locations (rather than different values). This is because (p xor p) = 0
and if both x and y share the same memory location, when one is set to 0, both are set to 0. When both *x and *y are 0, all other xor operations on *x and *y will equal 0 (as they are the same), which means that the function will set both *x and *y set to 0.
If they have the same values but not the same memory location, everything works as expected
*x = 0011 *y = 0011 //Note, x and y do not share an address. x != y *x = *x xor *y //*x = 0011 xor 0011 //So *x is 0000 *y = *x xor *y //*y = 0000 xor 0011 //So *y is 0011 *x = *x xor *y //*x = 0000 xor 0011 //So *x is 0011
Should this be used?
In general cases, no. The compiler will optimize away the temporary variable and given that swapping is a common procedure it should output the optimum machine code for your platform.
Take for example this quick test program written in C.
#include <stdlib.h> #include <math.h> #define USE_XOR void xorSwap(int* x, int *y){ if ( x != y ){ *x ^= *y; *y ^= *x; *x ^= *y; } } void tempSwap(int* x, int* y){ int t; t = *y; *y = *x; *x = t; } int main(int argc, char* argv[]){ int x = 4; int y = 5; int z = pow(2,28); while ( z-- ){ # ifdef USE_XOR xorSwap(&x,&y); # else tempSwap(&x, &y); # endif } return x + y; }
Compiled using:
gcc -Os main.c -o swap
The xor version takes
real 0m2.068s user 0m2.048s sys 0m0.000s
Where as the version with the temporary variable takes:
real 0m0.543s user 0m0.540s sys 0m0.000s
the general form is:
A = A operation B B = A inverse-operation B A = A inverse-operation B
however you have to potentially watch out for overflows and also not all operations have an inverse that is well defined for all values that the operation is defined. e.g. * and / work until A or B is 0
xor is particularly pleasing as it is defined for all ints and is its own inverse
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With