Swapping two variable value without using third variable

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.

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

Swapping two variable value without using third variable

Related

Recent Posts