swap two values withou using temp. storage

[lgmanuel]

hi guys need help about my problem, am trying to swap the values of 'x' and 'y' without using a temporary storage like 'z'.. here is the code int x = 150 (or any integer value); int y = 45 (or any integer value); output: x = 45 y = 150 help guys, thanks ahead.

[_Superman_]

x += y;
y = x - y;
x -= y;

If you have long variables or able to type cast to long, try InterlockedExchange.

«_Superman_»
I love work. It gives me something to do between weekends.

Microsoft MVP (Visual C++)

Polymorphism in C

[Luc Pattyn]

one way to get there is by using a number of exclusive-or operations. :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, and improve readability.

[Nuri Ismail]

1. With simple arithmetic operations:

int x = 150;
int y = 45;
x = x + y;
y = x - y;
x = x - y;

[EDIT] The above technique is dangerous because in some situations you can exceed the data types range!! Now I know (thanks to emilio_grv and his excellent post[^]) that this technique is not dangerous if the two variables are of the same integer type. [/EDIT] 2) The XOR swap:

int x = 150;
int y = 45;
x ^= y;
y ^= x;
x ^= y;

You can read more about the XOR swap here[^]. Also you can check out some CodeProject articles (and their message boards) on this topic: - A Curious Economic Swap[^] - The Stupid XOR Trick[^] :)

modified on Thursday, July 22, 2010 3:56 AM

[Emilio Garavaglia]

Point 1 isn't dangerous at all. The carry overflow of the sum is compensated by a missing borrow of the subtraction. Both +- and ^ operates on closed Galois field (+- of size 232 and ^ on 32 fields of size 2) The only difference is that the ^ operation requires a combinatorial network simpler than + and this can make the processor ALU faster. But it is quite hard this may be observed outside.

2 bugs found. > recompile ... 65534 bugs found. :doh:

[Nuri Ismail]

Thank you very much for this enlightening information. :thumbsup:

modified on Thursday, July 22, 2010 4:01 AM

[Aescleal]

If you're using C the various tricks other people have shown you will work, well, the XOR trick will, the add'em subtract'em one won't in all cases (you can't add two pointers although you can subtract them but can't use -=). Having said that I wouldn't bother too much unless it's an accademic exercise. Years ago when I worked in the games industry there were loads of tricks like this one which were meant to save clock cycles. However when, after loads of micro-optimisations like this one, someone actually did any timings there didn't turn out to be a lot of difference. Cheers, Ash

[Aescleal]

More importantly if you're into this sort of micro-optimisation then add'em subtract'em method only works on arithmetic types. Pointers need not apply. Cheers, Ash

[Nuri Ismail]

This is absolutely true! :thumbsup: I didn't mention that, because I thought it was obvious. But you are right - maybe it is not quite obvious for the OP, I should mention this fact. Thanks, :) Nuri

[Maximilien]

lgmanuel wrote:

am trying to swap the values of 'x' and 'y' without using a temporary storage like 'z'..

why ? IMO, other than the fact that it uses a small "hack", there is no reason to use that in 2010. (or as a stupid interview question).

Watched code never compiles.

[Emilio Garavaglia]

Aescleal wrote:

Pointers need not apply

Not necessarily: swapping two pointers can be achieved by add/subtract if reinterpreted as integers of the appropriate size. Don't think to pointer as "addresses" and to integer as "numbers". Think in term of "sequence of bits". The triple xor (as well as the add subtract) is just a mechanism that mix-up the bits so that the ones that were on a place appear to the other and vice-versa. What the bit are used to represent what is indifferent. The important thing is that +- (as well of ^) are not the overloaded specific for the particular type, but just the integer ones. The only constrain is that the integer size (in bits) must be the same as the swapping type.

2 bugs found. > recompile ... 65534 bugs found. :doh:

[Emilio Garavaglia]

consider this:

template<class A>
void xswap(A& a, A& b)
{
for(size_t i=0; i<sizeof(a); ++i)
{
((char*)&a)[i] ^= ((char*)&b)[i];
((char*)&b)[i] ^= ((char*)&a)[i];
((char*)&a)[i] ^= ((char*)&b)[i];
}
}

This works even if A is a class one gigabyte wide, without allocate an extra gigabyte.

2 bugs found. > recompile ... 65534 bugs found. :doh:

[Niklas L]

...and who would ever handle such monster objects by value?

home

[Emilio Garavaglia]

Depends on what the object represent: may be transfer buffers, one of which is shared with a DMA or another process. "Swap" merely means exchange the data visibility between devices, or processors. And since they are physically bounded to a device, cannot be swapped by reference (swapping the respective pointers). With less dimensions (typically, up to 4K or 9K), this exchanges are typically operated between the switch processors and the route processors of routers. Of course, is not something to be abused, but may have its own specific application.

2 bugs found. > recompile ... 65534 bugs found. :doh:

[Aescleal]

I don't think of pointers as addresses - they're variables that store addresses. The problem with add'em substract'em with pointers is either your code ends up with either loads of casts OR spurious zeros:

x += (y - 0);

Which may or may not be bad depending on your point of view. Personally I'd just use std::swap and say sod the efficiency unless someone can show me in a profiler that it's too slow. Cheers, ash

[Peter Mulholland]

I've been asked this one in an interview. I wasn't aware of the XOR swap at the time and I think I used a temp variable in my answer. I don't think I got an offer from that interview.

Pete

[stevev6]

i think its a homework question.

[Craig Norton]

Using Ruby: x, y = y, x

Try not to take life to seriously. When all is done no one gets out alive anyway.

[Aescleal]

I have been a couple of times as well - I'm a bit wary of taking any job that needs that sort of low level bit fiddling though. A good one to fire back at the interviewer is "I'll show you the C, you show me the boolean algebra proof." It's a good test of what the interviewer is like. Cheers, Ash

[ghle]

Use the processor registers. No temp variable involved. Use assembly language of your choice. Fast! 4 CPU instructions w/4 memory waits & you're done!

int x = 150;
int y = 45;
asm{
LDA x;
LDB y;
STA y;
STB x;
}

Using XOR, do it 3 times slower... 11 CPU instructions w/7 memory waits int x = 150; int y = 45; x ^= y; y ^= x; x ^= y;

#DEFINE B 1
int x = 150;
int y = 45;
asm{
/* x ^= y */
LDA x; /* A register = x */
XOR y; /* A = A XOR y */
STA x; /* x = A, i.e., x ^= y */

/* y ^= x */
STA B; /* B register = x */
LDA y; /* A register = y */
XOR B; /* A = A XOR B */
STA y; /* y = A, i.e., y ^= x */

/* x ^= y */
STA B; /* B register = y */
LDA x; /* A register = x */
XOR B; /* A = A XOR B */
STA x; /* x = A, i.e., x ^= y */
}

Otherwise, this other SLOW method... 12 CPU instructions w/6 memory waits x += y; y = x - y; x -= y;

#DEFINE B 1
int x = 150;
int y = 45;
asm{
/* x = x + y; */
LDA x; /* A register = x */
LDB y; /* B register = y */
ADA B; /* A register = A + B, i.e. A = x + y */
STA x; /* Save A register to x */

/* y = x - y */
/* A contains x, B contains y */
CMB; /* 1's complement B register, i.e. B = -y -1 */
INB; /* increment (2's complement) B , i.e. B = -y */
ADA B; /* Add B (-y) to A (x), i.e. A = x - y */
STA y; /* Save A register to y */

/* x = x - y */
/* At this point, A contains y */
CMA; /* 1's complement A register, i.e. A = -y -1 */
INA; /* increment A (2's complement), i.e. A = -y */
ADA x; /* Add x to A, i.e., A = -y + x */
STA x; /* Save A register to x */
}

Notes for the unknowing: Operations on registers are much faster than memory access Negating a number is two's complement Two's complement is one's complement +1 One's complement reverses (NOTs) all bits Who loves Assembler??? :thumbsup: No JITCHIT X| either.

Gary