Swapping two variable value without using 3rd variable

Question

One of the very tricky question asked in an interview...

we need to swap the values of two variables like a=10 and b=15

Generaly to swap two variables values, we need 3rd variable like..

temp=a
a=b
b=temp

Now the requirement is, swaping value of two variable values without using 3rd variable?

How can be accopmplish this?

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

Have you looked at XOR swap algorithm?

Answer 3

a = a + b
b = a - b // b = a
a = a - b

Answer 4

As already noted by manu, XOR algorithm is a popular one which works for all integer values (that includes pointers then). For the sake of completeness I would like to mention another less powerful algorithm with addition/subtraction:

A = A + B
B = A - B
A = A - B

Here you have to be careful of overflows/underflows, but otherwise it works just as fine. You might even try this on floats/doubles in the case XOR isn't allowed on those.

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

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 7

No-one has suggested using std::swap, yet.

std::swap(a, b);

I don't use and temporary variables and depending on the type of a and b the implementation may have a specalization that doesn't either. The implementation should be written knowing whether a 'trick' is appropriate or not. There's no point in trying to second guess.

More generally, I'd probably want to do something like this, as it would work for class types enabling ADL to find a better overload if possible.

using std::swap;
swap(a, b);

Of course, the interviewer's reaction to this answer might say a lot about the vacancy.

Answer 8

I believe it's safe to say that all of the above answers address the question quite well. One thing that hasn't been addressed here, probably due to political correctness, is the interviewers need for a basic English 101 class. Yes, taking into consideration that the interviewer may not have English as their first language. However, if they're interviewing in the U.S.A. they should command the language of their candidate. The point being, as the example illustrates, often they don't.

Example: "How can be accopmplish this?"

As Mr. Bailey & Null303 has addressed, other than making the unknowing candidate squint a bit as they hopefully write down one of the above solutions, hopefully this wouldn't be the deciding factor of whether the candidate gets the job or not. Then, in this day and age, there's reality.

Answer 9

More trivia, there's also the InterlockedCompareExchange functions, not a portable solution however.