By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,851 Members | 1,141 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,851 IT Pros & Developers. It's quick & easy.

exchange variables without aux. var...

P: n/a
Hi all,

How can I exchange the values of two integer variable without
using an auxiliary one.

=--=
kotee


9BF6 00E9 0CA9 B3A8 5234 03DB 3FB3 F85B 0033 74D7
http://keyserver.noreply.org/pks/loo...fingerprint=on
Feb 8 '07 #1
Share this Question
Share on Google+
13 Replies


P: n/a
"Szabolcs Szucs" <ko***@elte.huwrote in message
news:s7*************@login08.caesar.elte.hu...
Hi all,

How can I exchange the values of two integer variable without
using an auxiliary one.
std::swap( Int1, Int2 );

Although I'm sure std::swap makes a copy itself, you don't have to.
Feb 8 '07 #2

P: n/a
Szabolcs Szucs wrote:
Hi all,

How can I exchange the values of two integer variable without
using an auxiliary one.
There is a way to do it, but it doesn't really have any advantage, so don't
bother.

Feb 8 '07 #3

P: n/a
How can I exchange the values of two integer variable without
using an auxiliary one.
Lets say you have variables:

int a = A, b = B;

and want to exchange their values without using auxiliary variable.
Then write code like this:

a += b; // This gives you a == (A)+B
b = a-b; // This gives you b == (A+B)-B == A
a -= b; // This gives you a == (A+B)-A == B

and done!

However if this is not a school task then the method is not worth.
Using

std::swap(a, b);

(as Jim Langston sugested) is much better. Some processors (for
example Pentium) support instructions for exchanging registers or
memory values - and "swap" could be implemented using this advantage.

Adam Badura

Feb 8 '07 #4

P: n/a
Szabolcs Szucs a écrit :
Hi all,

How can I exchange the values of two integer variable without
using an auxiliary one.
This does look like a homework asignment.

Here is your answer:

int a=1;
int b=2;

a^=b^=a^=b;

And the detail:

....a^=b -a'=a^b
.... b^=a' -b'=b^a^b=a
a^=b' -a''=b'^a'=a^a^b=b;
Michael
Feb 8 '07 #5

P: n/a
On Feb 8, 4:18 pm, "abadura" <abad...@o2.plwrote:
How can I exchange the values of two integer variable without
using an auxiliary one.

Lets say you have variables:

int a = A, b = B;

and want to exchange their values without using auxiliary variable.
Then write code like this:

a += b; // This gives you a == (A)+B
b = a-b; // This gives you b == (A+B)-B == A
a -= b; // This gives you a == (A+B)-A == B

and done!

However if this is not a school task then the method is not worth.
Using

std::swap(a, b);

(as Jim Langston sugested) is much better. Some processors (for
example Pentium) support instructions for exchanging registers or
memory values - and "swap" could be implemented using this advantage.

Adam Badura
An XOR should also work,

int a=A, b=B;

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

Feb 8 '07 #6

P: n/a
On Feb 8, 1:22 pm, "Kishore Yada" <yadakish...@gmail.comwrote:
On Feb 8, 4:18 pm, "abadura" <abad...@o2.plwrote:


How can I exchange the values of two integer variable without
using an auxiliary one.
Lets say you have variables:
int a = A, b = B;
and want to exchange their values without using auxiliary variable.
Then write code like this:
a += b; // This gives you a == (A)+B
b = a-b; // This gives you b == (A+B)-B == A
a -= b; // This gives you a == (A+B)-A == B
and done!
However if this is not a school task then the method is not worth.
Using
std::swap(a, b);
(as Jim Langston sugested) is much better. Some processors (for
example Pentium) support instructions for exchanging registers or
memory values - and "swap" could be implemented using this advantage.
Adam Badura

An XOR should also work,

int a=A, b=B;

a = a ^ b;
b = a ^ b;
a = a ^ b;- Hide quoted text -

- Show quoted text -
I believe the xor tricks works whenever there is no aliasing, although
there might teoretically be corner-cases (-0 =0 on 1-bit complement
cpus?). Apart from no aliasing, the addition-trick requires that there
are no overflows.

/Peter

Feb 8 '07 #7

P: n/a
An XOR should also work,

Nice... I didn't knew this one... Thanks! :)

XOR ides seems more "low level" (requirement of binary
representation and so one...) while the arithmetic one is more
"algorithmic". However XOR is more general because this method can
used for every data type not just numbers.
I am wandering which method is faster: using temp, addition and
subtraction or XOR... This surly depends on the processor used...

Adam Badura

Feb 8 '07 #8

P: n/a
On Feb 8, 1:36 pm, "abadura" <abad...@o2.plwrote:
An XOR should also work,

Nice... I didn't knew this one... Thanks! :)

XOR ides seems more "low level" (requirement of binary
representation and so one...) while the arithmetic one is more
"algorithmic". However XOR is more general because this method can
used for every data type not just numbers.
I am wandering which method is faster: using temp, addition and
subtraction or XOR... This surly depends on the processor used...
The XOR will be fast since it's 3 operations on registers, but as you
pointed out earlier some processors can perform register swaps which
makes std::swap very attractive since a good compiler can optimize it
down to that while I doubt that you'll ever see a compiler that can
optimize the XORing to a register-swap.

Of course, if anyone is seriously contemplating optimizing a variable-
swap then either they are performing a very premature optimization, or
they have serious problems (if the swap is a bottleneck).

--
Erik Wikström

Feb 8 '07 #9

P: n/a
Kishore Yada wrote:
On Feb 8, 4:18 pm, "abadura" <abad...@o2.plwrote:
>>How can I exchange the values of two integer variable without
using an auxiliary one.
Lets say you have variables:

int a = A, b = B;

and want to exchange their values without using auxiliary variable.
Then write code like this:

a += b; // This gives you a == (A)+B
b = a-b; // This gives you b == (A+B)-B == A
a -= b; // This gives you a == (A+B)-A == B

and done!
There's no defined behavior for over/underflow on singed
integers. The above code isn't guaranteed to work.

>>
(as Jim Langston sugested) is much better. Some processors (for
example Pentium) support instructions for exchanging registers or
memory values - and "swap" could be implemented using this advantage.
Even without specialized instructions it's pretty easy to code up a
swap() function that's faster than anything you could write as a series
of C expressions, especially on machines that can't do a memory to
memory move directly:
LOAD a to R1
LOAD b to R2
STORE R1 to b
STORE R2 to a

> Adam Badura

An XOR should also work,

int a=A, b=B;

a = a ^ b;
b = a ^ b;
a = a ^ b;
You better be sure a and b are not aliased to the same
variable before you try this trick.

Feb 8 '07 #10

P: n/a
Erik Wikström wrote:
>
The XOR will be fast since it's 3 operations on registers
Once you have loaded them into registers there's no need to
actually swap the registers. Just switch your knowledge
of which register corresponds to which variable.
Feb 8 '07 #11

P: n/a
Michael DOUBEZ <mi************@free.frwrote:
Szabolcs Szucs a écrit :
>How can I exchange the values of two integer variable without
using an auxiliary one.

Here is your answer:

int a=1;
int b=2;

a^=b^=a^=b;
Undefined behavior: it attempts to modify the variable a twice between
sequence points.

Refer to the C FAQ (but this also applies to C++):
http://www.c-faq.com/expr/xorswapexpr.html

--
Marcus Kwok
Replace 'invalid' with 'net' to reply
Feb 8 '07 #12

P: n/a
Marcus Kwok a écrit :
Michael DOUBEZ <mi************@free.frwrote:
>Szabolcs Szucs a écrit :
>>How can I exchange the values of two integer variable without
using an auxiliary one.
Here is your answer:

int a=1;
int b=2;

a^=b^=a^=b;

Undefined behavior: it attempts to modify the variable a twice between
sequence points.
You are right. Yet another reason not to use it.

Michael
Feb 9 '07 #13

P: n/a
Szabolcs Szucs wrote:
>
How can I exchange the values of two integer variable without
using an auxiliary one.
Note, that even if yuor CPU support hadware memory-memory exchange, exchange
operation even in theory need temporary storage and take 2 reads & 2 writes
to memory.

To exchange you can declare a CPU-specific function swap and make some
specialisations.

namespace Nxxx_CPU
{

template<class T>
inline void swap(T& a,T& b)
{
T tmp=a;
a=b;
b=tmp;
}

//if your compiler support asm & inline &
//your CPU support "xchange memory-memory"
template<>
inline void swap<int>(int& a, int& b)
{
asm xchg [a],[b];
}

//if your compiler support asm & inline but
//your CPU soes not support "xchange memory-memory"
template<>
inline void swap<int>(int& a, int& b)
{
asm mov reg,[a];
asm xchg reg,[b];
asm mov [a],reg;
}

//namespace Nxxx_CPU
}

using Nxxx_CPU::swap;
void test()
{
int a=0,b=1;
swap<int>(a, b);
}

How tell to compiler to use "xchange" operation instead assignment? Maybe
very good compiler can do maximal optimization itself. It is compiler
specific. Changing theorder of operations can help if your compiler support
human "register" priotity.

template<class T>
inline void swap(T& a,T& b)
{

register T tmp_a=a; //a to register

//a=b;
register T tmp_b=b; //b to register
a=tmp_b; //register to a

//b=tmp;
b=tmp_a; //register to b
}

-- NOT C++ --

1.
It is easy to see, that best solution is to add to C++ new operator, to
explicit declare exchange opertions, for example "operator<-(a,b)", to
help compiler to optimize. This is most perfomans solution.

template<>
inline void swap<int>(int& a, int& b)
{
a<->b;
/*
can be unrolled to maximum perfomance exchange

register int tmp=a; //a to register tmp
b<->tmp; //register tmp <-to b
a=tmp; //register b ->a
*/
}

2.
In case of complex data high prefomans exchange can ne reached by
introducing to C++ new prefix "operator< ()" (operator "move").

If complex object of class T can be represented at runtime as
- "pointer to its internal state" &
- "methods to manage the state" as "move, delete, create, copy"
then "swap" it is a "shallow copy" of the pointer instead of "deep copy" of
internal state.

template <class Tswap(T& a, T& b)
{
const T tmp(<a);
//here "a" internal state pointer move to "tmp", "a" marked as
"destroyed":

a = <b;
//here "b" internal state pointer move to "a", "b" marked as
"destroyed":

b = <tmp;

//here "tmp" internal state pointer move to "b", "tmp" marked as
"destroyed":
}

It is interesting, that low-level "pointer exchange" can be implemented with
the help of <-operator and swap perfomans of complex data can be equal to
swap perfomans of POD types.

3.
You can do fast swap with the help of C-style macro

//if your compiler support only "asm"
#define swap_int(a,b)\
asm{\
mov eax,a\
xchg eax,b\
mov a,eax\
}

or asm implemented over pragma aux

//if your compiler support pragma aux
//#pragma aux ...

-- NOT C++ --

--
Maksim A. Polyanin

"In thi world of fairy tales rolls are liked olso"
/Gnume/
Feb 10 '07 #14

This discussion thread is closed

Replies have been disabled for this discussion.