424,851 Members | 1,141 Online
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
13 Replies

 P: n/a "Szabolcs Szucs"

 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"

 P: n/a On Feb 8, 1:22 pm, "Kishore Yada"

 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"

 P: n/a Kishore Yada wrote: On Feb 8, 4:18 pm, "abadura" >How can I exchange the values of two integer variable withoutusing 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 == Band 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 (forexample Pentium) support instructions for exchanging registers ormemory 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 How can I exchange the values of two integer variable withoutusing 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 Szabolcs Szucs a écrit : >>How can I exchange the values of two integer variable withoutusing 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 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& 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& 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(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 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& 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

### This discussion thread is closed

Replies have been disabled for this discussion.