Swapping two variable value without using third variable

Question

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.

Answer 1

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 

Answer 2

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