[Exercise] Swapping without using temp variable

Ra8

Implement a swap without using any temp variable nor using the built in swap function (like the swap() function in C++) to swap two integers.
example:

a=1234;
b=2;
//[i]your code goes here[/i]
//a=2;
//b=1234;

I tested it on C++ and on PHP it worked.

Joe

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

Beware though, as this code might overflow.

Ra8

yeah, i was thinking of a method that does not involve arithmetic operation, just pure binary operations, it will not overflow:

a=1234;
b=2;
a=a^b;
b=a^b;
a=a^b;

^ is the XOR binary operator

note that:
P XOR P = 0
and that 0 XOR P =P

first step:
a=a XOR b b =b
second step:
a=a XOR b b=a XOR b XOR b = a XOR 0 =a
third step:
a=a XOR b XOR a = b XOR 0 = b b=a;

arithma

rahmu wrote

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

Beware though, as this code might overflow.

This is correct even if overflow wraps around (which is standard behavior for unsigned integral types, but not so much for signed ones which can clamp to limits).
Try it modula 8 on 3 and 6.

rolf

Thinking at the binary level, we could reserve 1 bit (the leftmost / most significant bit) off each variable to use as temporary bit, then swap the variables 1 bit at a time using this temporary bit.
This way we only loose 1 bit from the maximum variable size; eg 32 bit integer will become 31 bit integer.

PS: Actually we don't even need 2 bits, just one, so if we're dealing with 32 bit numbers, only one of them has to fit in 31 bits, that's all that is required.

arithma

@rolf, the point that was being made before your post is that no extra space is required at all. Not even 1-bit.
The reason is that XOR operation is information preserving if you have at least one of the operands.

Note: Addition is actually very closely related to the XOR operation. At the one bit level, addition is a XOR operation. The carry is an and. Addition could be implemented as a series of cascading XORs and Ands.

Joe

It's worth mentioning one of my favorite Python features:

a, b = b, a

elzalem

using php:

list($x, $y) = array($y, $x)

that's creating a copy implicitly so I don't think it counts, but it's a nice one liner (can exchange more than 2 variables too)