swaping inplace

how to swap two numbers inplace without using any ad开发者_运维知识库ditional space?

You can do it using XOR operator as:

if( x != y) { // this check is very important.

  x ^= y;
  y ^= x;
  x ^= y;
}

EDIT:

Without the additional check the above logic fails to swap the number with itself. Example:

int x = 10;

if I apply the above logic to swap x with itself, without the check I end up having x=0, which is incorrect.

Similarly if I put the logic without the check in a function and call the function to swap two references to the same variable, it fails.

If you have 2 variables a and b: (each variable occupies its own memory address)

a = a xor b
b = a xor b
a = a xor b

There are also some other variations to this problem but they will fail if there is overflow:

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

a=a*b
b=a/b
a=a/b

The plus and minus variation may work if you have custom types that have + and - operators that make sense.

Note: To avoid confusion, if you have only 1 variable, and 2 references or pointers to it, then all of the above will fail. A check should be made to avoid this.

Unlike a lot of people are saying it does not matter if you have 2 different numbers. It only matters that you have 2 distinct variables where the number exists in 2 different memory addresses.

I.e. this is perfectly valid:

int a = 3;
int b = 3;

a = a ^ b;
b = a ^ b;
a = a ^ b;

assert(a == b);
assert(a == 3);

The xor trick is the standard answer:

int x, y;
x ^= y;
y ^= x;
x ^= y;

xoring is considerably less clear than just using a temp, though, and it fails if x and y are the same location

Since no langauge was mentioned, in Python:

y, x = x, y