i have heard from a friend of mine that the best algorithm for swapping is " (a^=b^=a^=b)" where a and b are two integers to be swapped. but when i applied this using c language it resulted in crashing. can anyone of you fine people explain the possible reason for that? please suggest the best algorithm for swapping. thank you!!!! guys i would like to know the reason for crashing.
+8
A:
this swapping trick is sometimes dangerous, I have seen a a wrong quicksort program using this swap generates wrong results. But a usual swap generates correct program.
Respect to speed, the compiler sometimes generates faster code if we use a tmp variable.
use tmp = a; a = b; b = tmp;
Yin Zhu
2010-03-13 05:24:22
thanks @yin i would like to know why is my trick very dangerous?
CadetNumber1
2010-03-13 05:29:48
XOR swap (`a^=b^=a^=b`) will only work on integers (and pointers). XOR swap will change both `a` and `b` to 0 if they are equal.
LiraNuna
2010-03-13 05:32:01
Suppose `a` and `b` are pointers that point to the same thing.Then `(*a)^=(*b)^=(*a)^=(*b)` will zero out the value. In C++ if these are references you can do this without the dereference.But the real reason to use what @Yin Zhu suggests is that your code should be clear, and you shouldn't worry about a micro-optimization like this.
rlbond
2010-03-13 05:34:25
@ashish http://en.wikipedia.org/wiki/XOR_swap_algorithm for detail discussion. the wiki article does not discuss why it is dangerous.
Yin Zhu
2010-03-13 05:35:17
@liranuna is that the reason for CRASH that swap (a^=b^=a^=b) is not generic?
CadetNumber1
2010-03-13 05:35:21
@yin no problem .thanks for your support
CadetNumber1
2010-03-13 05:36:07
but this method consumes extra memory
ratty
2010-03-13 05:45:49
@ratty: Not necessarily; the compiler can optimize away the temporary integer. In fact, this analysis (http://big-bad-al.livejournal.com/98093.html) found that not only did the XOR and addition/subtraction methods fail to save any memory over the temporary variable method on an X86 processor, they were actually slower than the tmp method. The addition/subtraction one even used an additional register. In short, you should leave micro-optimizations like this to the compiler.
Josh Townzen
2010-03-13 07:15:49
@Yin Zhu: "I have seen a a wrong quicksort program" - even better IMO, the first listed runner-up in the 2007 Underhanded C contest: http://underhanded.xcott.com/?page_id=16. Code deliberately uses a flawed swap to undermine the security of a PRNG. The flaw is subtle to anyone who would ever contemplate using XOR swap in real life, and screamingly obvious to anyone who understands why not to. Programmers should strive to join the latter group ;-)
Steve Jessop
2010-03-13 14:59:40
A:
Use this logic for numeric values :
int a = 10, b =5 ;
a = a-b;
b = b+a ; // b gets the original value of a
a = b - a; // a gets the original value of b
printf ("value : %d %d \n",a ,b) ;
pavun_cool
2010-03-13 05:40:41
+2
A:
See http://en.wikipedia.org/wiki/Swap_(computer_science) .
Using a temporary variable generates more overhead, but is more stable than the XOR swap algorithm and parallel computing renders it faster than XOR swap.
See the first code example of http://www.ibm.com/developerworks/linux/library/l-metaprog1.html for a solid implementation of using a temporary variable for swapping.
Yktula
2010-03-13 05:45:56
+9
A:
a^=b^=a^=b; probably crashes because it invokes the dreaded undefined behaviour. The rule it breaks is that it modifies a twice without an intervening sequence point. It can be fixed by inserting some sequence points - for example, with the comma operator:
a ^= (b ^= a ^= b, b);`
Or by breaking it up into multiple statements:
b ^= a ^= b; a ^= b;
It is still, however, usually a bad method for swapping variables - several of the other answers and comments have adequately explained why.
caf
2010-03-13 07:47:18
A:
Write that code that is faster to read by human being. And trust compilers' ability to generate better code most of the time. Do a profiling to see if this is the only place to improve speed. Then apply XOR solutions listed many times above , it may not work every where.
Jayan
2010-03-13 09:52:11