exchange variables without aux. var...

[Szabolcs Szucs]

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/[email protected]&fingerprint=on

 

[Jim Langston]

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.

 

[Rolf Magnus]

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.

 

[abadura]

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

 

[Michael DOUBEZ]

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

 

[Kishore Yada]

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;

 

[peter koch]

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

 

[abadura]

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

 

[=?iso-8859-1?q?Erik_Wikstr=F6m?=]

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

 

[Ron Natalie]

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


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

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.

 

[Ron Natalie]

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.

 

[Marcus Kwok]

Szabolcs Szucs a écrit :

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

 

[Michael DOUBEZ]

Marcus Kwok a écrit :

Undefined behavior: it attempts to modify the variable a twice between
sequence points.

You are right. Yet another reason not to use it.

Michael

 

[Grizlyk]

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],;
}

//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,;
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 T> swap(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++ --