LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 June 5 2012

Ra8
Member

[Exercise] Swapping without using temp variable

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.

Offline

#2 June 5 2012

Joe
Member

Re: [Exercise] Swapping without using temp variable

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

Beware though, as this code might overflow.

Offline

#3 June 5 2012

Ra8
Member

Re: [Exercise] Swapping without using temp variable

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;

Offline

#4 June 5 2012

arithma
Member

Re: [Exercise] Swapping without using temp variable

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.

Offline

#5 June 5 2012

rolf
Member

Re: [Exercise] Swapping without using temp variable

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.

Last edited by rolf (June 5 2012)

Offline

#6 June 5 2012

arithma
Member

Re: [Exercise] Swapping without using temp variable

@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.

Offline

#7 January 31 2013

Joe
Member

Re: [Exercise] Swapping without using temp variable

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

a, b = b, a

Offline

#8 February 6 2013

elzalem
Member

Re: [Exercise] Swapping without using temp variable

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)

Offline

Board footer