tags:

views:

232

answers:

10

Possible Duplicate:
What is the fastest way to swap values in C?

How can I swap the values of two variables without using 3rd variable?

I want to swap (interchange) the values of two variables a and b.

+16  A: 

Use std::swap:

std::swap(a,b)
Vladimir
Note: This does use a third variable under the hood. But you don't have to do it yourself, and it's not possible without anyway (XOR swap doesn't count, as it works only with integers(? maybe other primitives, too?)). It doesn't get any better than this.
delnan
@Vladimir: i would advise to use std::swap() as well, but this answer is not really what the OP asked for. so, explain why it is better to use std::swap() instead of hacky xorswap.
akira
@delnan: "not possible" is a bit strong. For example, x86 has`xchg` opcodes which could easily exchange two integer (and often pointer) variables with no temporary involved. Clearly a library function could have a specialized version which uses inline assembly for certain types.
Evan Teran
The other reason to use std::swap is that it's frequently specialized for the correct type.
DeadMG
If swapping two vectors in C++, vector::swap can be very efficient as it doesn't require copying either vector to a third vector. It can simply swap the internal pointers that point to the actual vector contents.I suspect std::swap might use these shortcut methods where available (as with vector)? (@DeadMG: just seen your, relevant, comment.)http://www.cplusplus.com/reference/stl/vector/swap/
Aaron McDaid
@Evan Teran: "x86 has`xchg` opcodes" doesn't xchg require that one of the opcodes is a register? If so, you won't be able to swap two bytes in memory without temporary variable - which will be a register.
SigTerm
@Evan: Yeah, it's possible in some cases. But there's no way to do it portable across platforms and/or data types, and I prefer to totally ignore non-portable stuff. Of course you're right, it's not always *impossible*.
delnan
A: 

I don't think you can. Why would you not want to use a 3rd variable?

icemanind
+4  A: 

You're referring to a pretty famous riddle. The answer depends on the data type. There is no algorithm for a generic type.

San Jacinto
A: 

Unless you can use processor-specific instructions that do the exchange without a third variable, you will have to use a temporary to do the swap, sorry.

You could use std::swap but that only hides the temporary.

Timo Geusch
+1  A: 

http://en.wikipedia.org/wiki/XOR_swap_algorithm

void xorSwap (int *x, int *y) {
    if (x != y) {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}
akira
No reason to use pointers instead of references, I think. Just makes for clumsier calling code. (And what if I do `xorSwap(0, 0)`?)
GMan
akira
@akira: Totally blanked out on the last point, though if one argument is null it's still gonna blow up. If we're writing C++ who cares if it works in C? References are much cleaner IMO.
GMan
@GMan: just taste, and just a minor one in real life code. not really worth arguing about it.
akira
@akira: Eh, I think it's more than taste. Your code as it stands is not robust. We should program C++ in C++, not C.
GMan
then go ahead and fix it in wikipedia. and no, it _is_ a matter of taste.
akira
@akira: I have indeed fixed the page, though I don't understand why your answer has to strictly be a copy. :) I don't know how far up the ivory tower you want to go, but I think it's practical to say references are more appropriate most of the time. That is, most people want to alias values, not point to them. If one method makes code broken and the other doesn't, unless broken versus non-broken is a matter of taste, choice of method is not a matter of taste.
GMan
@GMan: strict copy: because it is a "quote", pointing to the original source as well, without pretending to have "the ultimate better and improved version for this kind of hack" and to show OP that this is an old "problem". sidenote: i use references all day, i use them for more than 10 years (that is when you were really young). as i said: it is absolutely not worth discussing this piece of hackerish snippet except saying "use std::swap".
akira
@akira: But it doesn't have to maintain being a quote. If there's a problem with the source, you can change "quoted from" to "based on" and improve it. :] And I think it is worth pointing out flaws because more people than just you or I will come across this answer. It would be a shame to have them use broken code. The entire point of this site is to post answers, and comment/improve on answers that are broken/fixable.
GMan
A: 

There's a couple ways you can do it. You can swap the pointers, or if the values are integers, you can use a little arithmetic hack:

a=a+b;
b=a-b;
a=a-b;
Josiah
This works only if the first addition doesn't overflow.
Joel
Very true (more characters)
Josiah
A: 

You could use the XOR swap algorithm

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

However, this is not a great idea. Also from wikipedia:

Most modern compilers can optimize away the temporary variable in the naive swap, in which case the naive swap uses the same amount of memory and the same number of registers as the XOR swap and is at least as fast, and often faster.[cite] The XOR swap is also much less readable, and can be completely opaque to anyone who isn't already familiar with the technique.
Tim Goodman
+8  A: 

Typically, you don't. There's no reason not to use a third variable, just call std::swap(a, b) and move on with your life.

With integer types, you can do:

void swap(int& a, int& b)
{
    if (a != b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }
}

But this typically gives worse performance than just using a third variable.

GMan
@Kirill: It's not the values that have to be different, it's the variables themselves. Swapping with the same location makes the whole thing 0.
GMan
if location the same variables will be equal. in case variables are equal you shouldn't do swap too. `a != b` is more common
Kirill V. Lyadvinsky
@Kirill: Haha, duh. My bad. :) Nominate "dumbest moment" for me.
GMan
+2  A: 

There are many ways. just Google your question and you'll find many answers.

Using Sum: (fails on large numbers)

a = a + b;
b = a - b;
a = a - b;

Using Multiply (not always working):

a = a * b;
b = a / b;
a = a / b;

Using XOR:

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

Using ASM Code:

   __asm
  {
      mov EAX,b
      push EAX
      mov EAX,a
      mov b,EAX
      pop EAX
      mov a,EAX
  }

but I suggest you to use std::swap.

x86shadow
Thanks it's best for me, because i am new student of C++
Najam
"Using ASM Code:" You're using EAX/stack for storing temporary variable.
SigTerm
@SigTerm you are right. I wanted to show how to use assembly code to work with variables. actually you can implement XOR swap with asm code.
x86shadow
A: 

Generally, you will need a third, empty variable for swapping the content of two other variables.

However, there are special cases. Here's one special swap for two bool variables a and b:

void swap_bools(bool &a, bool &b)
{
    if (a != b)
    {
        a = !a, b = !b;
    }
}
stakx