best algorithm for swapping?

Question

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.

Guibert

I can't believe this is even a question on SO. What's wrong with std::swap? – Penmanship

@BillyONeal: since std::swap is C++ and this question is tagged with C. – Glabrate

OK -- Sorry -- Let me change that to "What's wrong with the plain simple implementation typical of std::swap? T temp = one; one = two; two = temp;? Seriously -- if swap is a speed limiter of your program then you have a problem I'd sure like to have. – Penmanship

Whether this is the "best algorithm for swapping" is entirely subjective and dependent on what you are trying to achieve. It may be amongst the 'cleverest' tricks, but 'best' IMO would be the code a future maintainer will understand and for which the behaviour for all possible inputs is well defined and understood. This does not pass that test. Always bear in mind the following: nedbatchelder.com/blog/200310/… – Myalgia

Your friend's a menace. Who writes code like that? – Flier

Answer 1

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;

Duel

thanks @yin i would like to know why is my trick very dangerous? – Guibert

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. – Glabrate

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. – Marinara

@ashish en.wikipedia.org/wiki/XOR_swap_algorithm for detail discussion. the wiki article does not discuss why it is dangerous. – Duel

@liranuna is that the reason for CRASH that swap (a^=b^=a^=b) is not generic? – Guibert

but this method consumes extra memory – Argyle

@ratty: Not necessarily; the compiler can optimize away the temporary integer. In fact, this analysis (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. – Mudcat

@Yin Zhu: "I have seen a a wrong quicksort program" - even better IMO, the first listed runner-up in the 2007 Underhanded C contest: 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 ;-) – Flier

Answer 2

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.

Fourfold

Answer 3

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.

Wrens

why does is generate more overhead for the temporary variable solution ? The XOR swap also creates more computation overhead also. – Natheless

Answer 4

well, in this case we can use Mathematics for swap two Numbers without third variable

• there are some rules which you need to learn which are given below;

assume that you have two variables A = 10 and B = 20 so now if you add them both you get 30 as total right.

Now if you subtract A from total then you get B as a result and if you subtract B from total then you will get A as a result.

For Example:

A = (A+B)-A;       //(10 + 20) -10;  ===>   we will get 20 as a result
B = (A+B)-B;       //(10 + 20) -20;  ===>   we will get 10 as a result

so by this technique you understand that by subtracting one number from total of two number we will get another number as a result.

So Now Final Answer for swapping two Number is Stated Below

• A=(A+B)-(B=A)

So here we have subtract A from Total of A and B so we get B in A as result and we get value of A in B by assignment ;``

Boxberry

Answer 5

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.

Defeasible

Answer 6

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

Carmelitacarmelite

What happens when a is INT_MAX, and b is INT_MIN? In other words, a-b can overflow/underflow. – Nickels

@Alok: Despite the overflow, it will still give the correct answer with wraparound arithmetic. – Fortunate

@dan04: wraparound is not guaranteed - in C/C++ integer overflow is UB. – Meneses