Switching two numbers without using extra space does not work if both point to the same place?

Question

I recently came across this issue of writing a function to replace two numbers without using extra space . A function can be in two ways:

int swap ( int *a, int* b) { *a = *a+*b; *b = *a-*b; *a = *a-*b; } 

Another way is the XOR operation:

 int swap ( int *a, int* b) { *a = *a^*b; *b = *a^*b; *a = *a^*b; } 

Although both of these functions are a good idea, they will not work if both a and b point to the same memory location? How to handle this?

Answer 1

The problem is obvious in mathematics.

 int swap ( int *a, int* b) { *a = *a+*b; *b = *a-*b; *a = *a-*b; } 

when a and b point to the same place, then the code above turns into

 *a = *a + *a; // *a = 2 x (*a) *b = *a - *a; // = 0 *a = *a - *a; // = 0 

So both *a and *b are zero. To do this, you must access using if :

 int swap ( int *a, int* b) { if (a!=b) { *a = *a+*b; *b = *a-*b; *a = *a-*b; } } 

And the same for xor version.

Answer 2

 #define SWAP(a, b) (((a) == (b)) || (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))) 

Answer 3

Why would anyone exchange two numbers without using extra space?

Which sadist will give you enough room for two, but not three?

Why do you call it "space"? This is just the third number, there is no need to refer to a huge place filled with vacuum.

An algorithm that uses the temporary use of O (1) space in the number of swap operations. This is O (n) in the length of the number, but it is possible that bit-twiddling and arithmetic give processor-unfriendly n.

If you do not have enough space for a simple number, you simply run out of space. I cannot see where you can go from the swap in this case.

Why not keep these two numbers in their own places in the first place?

Answer 4

You can try this, a = a + b; B = AB; a = a-b;