0

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.

Community
  • 1
  • 1
Najam
  • 21
  • 1
  • 3
  • 1
    Why don't you want to use another variable? I don't think it's possible. – Ash Burlaczenko Jul 21 '10 at 20:11
  • 1
    Was this an interview question or a homework assignment? – MikeD Jul 21 '10 at 20:21
  • 1
    *Way* too many duplicates on SO already, e.g. http://stackoverflow.com/questions/36906/what-is-the-fastest-way-to-swap-values-in-c – Paul R Jul 21 '10 at 20:23
  • @Paul R, it's worth noting that C isn't the same as C++, and `std::swap` (the "correct" way to swap variables in C++) doesn't exist in C. – Brendan Long Jul 21 '10 at 20:38
  • 1
    Brand new user asks super-duplicated question without doing a search first; question is classic homework/interview question. Vote to close, delete, and terminate with extreme prejudice. Why are people even answering? – Stephen P Jul 21 '10 at 20:40
  • @Brendan: there are many dupes, for both C and C++ - I just picked one at random – Paul R Jul 21 '10 at 20:40
  • @Stephen P: because answering is faster than searching for a possible duplicate. – akira Jul 21 '10 at 20:53
  • @Stephen P, easy points. I sometimes think people shouldn't get points for answering closed questions.. – Brendan Long Jul 21 '10 at 21:24

7 Answers7

17

Use std::swap:

std::swap(a,b)
Vladimir
  • 170,431
  • 36
  • 387
  • 313
  • 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. –  Jul 21 '10 at 20:15
  • 1
    @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 Jul 21 '10 at 20:21
  • @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 Jul 21 '10 at 20:22
  • 1
    The other reason to use std::swap is that it's frequently specialized for the correct type. – Puppy Jul 21 '10 at 20:24
  • 3
    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 Jul 21 '10 at 20:26
  • @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 Jul 21 '10 at 20:33
  • @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*. –  Jul 21 '10 at 20:41
10

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.

GManNickG
  • 494,350
  • 52
  • 494
  • 543
4

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
  • 8,774
  • 5
  • 43
  • 58
1

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

void xorSwap (int *x, int *y) {
    if (x != y) {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}
MrTux
  • 32,350
  • 30
  • 109
  • 146
akira
  • 6,050
  • 29
  • 37
  • No reason to use pointers instead of references, I think. Just makes for clumsier calling code. (And what if I do `xorSwap(0, 0)`?) – GManNickG Jul 21 '10 at 20:14
  • a) as the url suggests, it is a direct copy of the wikipedia form. b) because c does not know 'references' and thus this will work in c++ as well as in c. c) `if (x != y)` covers `xorSwap(0, 0)` as well as `xorSwap(&z, &z)` – akira Jul 21 '10 at 20:19
  • 1
    @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. – GManNickG Jul 21 '10 at 20:22
  • @GMan: just taste, and just a minor one in real life code. not really worth arguing about it. – akira Jul 21 '10 at 20:27
  • 1
    @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. – GManNickG Jul 21 '10 at 20:45
  • then go ahead and fix it in wikipedia. and no, it _is_ a matter of taste. – akira Jul 21 '10 at 20:52
  • @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. – GManNickG Jul 21 '10 at 20:57
  • @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 Jul 21 '10 at 21:09
  • @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. – GManNickG Jul 21 '10 at 21:26
0

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
  • 24,095
  • 5
  • 52
  • 70
0

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
  • 4,754
  • 1
  • 20
  • 19
0

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
  • 23,308
  • 7
  • 64
  • 83