Swapping two variable value without using third va

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

Stupid questions deserve appropriate answers:

void sw2ap(int& a, int& b) {
  register int temp = a; // !
  a = b;
  b = temp;
}

The only good use of the register keyword.

Answer 2

The best answer would be to use XOR and to use it in one line would be cool.

    (x ^= y), (y ^= x), (x ^= y);

x,y are variables and the comma between them introduces the sequence points so it does not become compiler dependent. Cheers!

Answer 3

Maybe off topic, but if you know what you are swapping a single variable between two different values, you may be able to do array logic. Each time this line of code is run, it will swap the value between 1 and 2.

n = [2, 1][n - 1]

Answer 4

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 5

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

Answer 6

#include<iostream.h>
#include<conio.h>
void main()
{
int a,b;
clrscr();
cout<<"\n==========Vikas==========";
cout<<"\n\nEnter the two no=:";
cin>>a>>b;
cout<<"\na"<<a<<"\nb"<<b;
a=a+b;
b=a-b;
a=a-b;

cout<<"\n\na="<<a<<"\nb="<<b;
getch();
}