16

I recently came along this method for swapping the values of two variables without using a third variable.

a^=b^=a^=b

But when I tried the above code on different compilers, I got different results, some gave correct results, some didn't.

Is anything terribly wrong with the code?

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Pattrick
  • 177
  • 2
  • 3
  • 19
    Of course one wouldn't actually swap like that. Use a temporary, it's cleaner and executes faster on modern hardware. – GManNickG Sep 18 '10 at 11:17
  • 1
    I would say "I got different results" means that there is something terribly wrong with the code for all X such that X is "the code". – msw Sep 18 '10 at 11:25
  • @GMan : Hmm, that's right. But it seems you are angry or something at someone, somewhere. :D – Prasoon Saurav Sep 18 '10 at 11:26
  • 3
    One shouldn't actually swap manualy with a temporary. in C++ exists a STL function called std::swap that does the same thing. – BatchyX Sep 18 '10 at 11:26
  • 17
    @Prasoon: I'm sick of [these](http://stackoverflow.com/questions/3741051/couple-noob-c-questions) "I know Java/I know C#, trying to learn C++, in Java/C# we..." questions. The answer is stop and read a book. That's all. If you don't know beginner C++, you learn it by reading a beginner C++ book. There's no shortcuts there. Trying to guess around with "knowledge" from another language is like trying to fly a plane because you know how to ride a tricycle. That's stupid. – GManNickG Sep 18 '10 at 11:28
  • @GMan : Yeah right, stackoverflow.com is not(at all) an alternative to those really good books. One should read those books and then come and ask his/her doubts here. :) – Prasoon Saurav Sep 18 '10 at 11:32
  • @msw : `Swap` and `Code-Golf` tags were perfectly valid. I have often seen some beginner coders employing these (sort of) methods when they try implementing some basic algorithms which make use of bitwise operators. – Prasoon Saurav Sep 18 '10 at 11:35
  • So use your rollback privilege if you like, it is too trivial to warrant discussion. – msw Sep 18 '10 at 11:47
  • 1
    Many, many duplicates, e.g. [Swapping two variable value without using 3rd variable](http://stackoverflow.com/questions/1826159/swapping-two-variable-value-without-using-3rd-variable) – Paul R Sep 18 '10 at 11:57
  • 6
    @Paul : No, Pattrick's problem here is different. He is not asking about `Swapping two variable value without using 3rd variable`. – Prasoon Saurav Sep 18 '10 at 11:58
  • swapping in this manner would only work for integer values, use third values instead its cleaner and also in case of floating point values doenst cause any truncation – keshav84 Sep 18 '10 at 14:04
  • 2
    @All who have voted to close: As per my opinion this was not a duplicate because the question Pattrick asked what not `How to swap two variable values without using 3rd variable`, I have voted to reopen. – Prasoon Saurav Sep 18 '10 at 14:46
  • 5
    I agree that a question about "why doesn't *A* work?" shouldn't be closed as a duplicate of "How to do *B*?" with the solution being *C*. – Georg Fritzsche Sep 18 '10 at 15:29
  • 3
    @GMan: let me quote you a comment from a MetaSO user that i feel perfectly sums up what SO is for: "This is a question and answer site. Not a "complex question, insightful answer that grows you as a person site." People should be able to ask simple questions with simple answers, that just may so happen to be spoon-fed. A lot of people just want to write code that works. Not be empowered. – Owen Sep 19 '08 at 21:23" – RCIX Sep 19 '10 at 06:48
  • 1
    @GMan: I'm not saying people shouldn't read the book, just that they shouldn't get yelled at for asking a perfectly valid question. – RCIX Sep 19 '10 at 06:49

8 Answers8

38

Is anything terribly wrong with the code?

Yes!

a^=b^=a^=b in fact invokes Undefined Behaviour in C and in C++ because you are trying to change the value of a more than once between two sequence points.

Try writing (although not foolproof )

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

instead of a^=b^=a^=b.

P.S : Never try to swap the values of two variables without using a third one. Always use a third variable.

EDIT :

As @caf noticed b^=a^=b is fine even though the order of evaluation of arguments of ^= operator is unspecified, since all the accesses of b within the expression are being used to compute the final value that is being stored in b, the behaviour is well defined.

Community
  • 1
  • 1
Prasoon Saurav
  • 91,295
  • 49
  • 239
  • 345
  • 1
    The modification of `b` is actually OK, since it is read only to determine the new value (`b ^= a ^= b;` would be OK). – caf Sep 18 '10 at 11:15
  • 5
    @caf : but the order of evaluation of arguments of `=` operator is unspecified. – Prasoon Saurav Sep 18 '10 at 11:17
  • @Prasoon_Saurav,Why do you tag the 3 statements as "not foolproof"? –  Sep 18 '10 at 12:03
  • 2
    @crypto : Because this swapping method would work only for integers. :-) – Prasoon Saurav Sep 18 '10 at 12:04
  • 1
    @Prasoon_Saurav, The operations are simply swapping the bit representation used for a & b, how would it matter if it were a different data type? –  Sep 18 '10 at 12:10
  • 1
    @crypto: the `^=` operator is not even defined for other types. – R.. GitHub STOP HELPING ICE Sep 18 '10 at 12:13
  • Do you mean that ^= is only defined for int types? –  Sep 18 '10 at 13:09
  • @Crypto : For `int` family. :) – Prasoon Saurav Sep 18 '10 at 13:15
  • This time it's also undefined for C++0x for the original expression. But `b ^= a ^= b` is actually fine in C++0x. The assignment to `b` is sequenced after value computation of `a ^= b`. The wording of C++03 is not clear in my opinion, but I'm not opposed to @caf's interpretation. I'm not going to bet on C++03 though :) – Johannes Schaub - litb Sep 18 '10 at 14:13
  • @Johannes : Thats for the information. I found C++-03 sequence points stuffs easier to read and understand as compared to terms like sequenced/unsequenced in C++0x. And as [R](http://stackoverflow.com/users/379897/r) said `a ^= ( a^=b , b^=a );` is also undefined in C++(and I am sure it would be well defined in C++0x). I'll miss good'ol sequence points :-) – Prasoon Saurav Sep 18 '10 at 14:19
  • @Prasoon well C++03's rules are too unclear to describe what really happens to `b ^= a ^= b` IMO. It looks innocent because the Standard says that it's fine to read and write the same variable in an expression if the read is to determine the value to write. This seemingly is the case in `b ^= a ^= b` or `i = a[i];` and similar. But there is no really strong wording in C++03 for this so I'm not going to bet, unlike for C++0x :) – Johannes Schaub - litb Sep 18 '10 at 14:23
  • @Johannes : But C++03 also says that the order of evaluation of arguments of `=` operator is unspecified. So you never know whether which side of the assignment operator gets evaluated first. :) – Prasoon Saurav Sep 18 '10 at 14:25
  • @Prasoon yes `a^= (a^=b, b^=a)` is definitely undefined in C++03 and C++0x => `a` is changed by `a^=b` (side effect) and value-computed by the left-most `a`, and both of these are not sequenced. – Johannes Schaub - litb Sep 18 '10 at 14:32
  • @Johannes : Damn! Now I am confused. You said that in `b ^= a ^= b`, the assignment to `b` is sequenced after value computation of `a ^= b` right? so that means in `a^= (a^=b, b^=a)` the assignment to left-most `a` is sequenced after the value computation of `(a^=b, b^=a)`, right? But hey, we have a comma operator in `(a^=b, b^=a)`, which would clear the side effect of `a^=b` then how would that be UB in C++0x? – Prasoon Saurav Sep 18 '10 at 14:37
  • 1
    @Prasoon it's UB for the above reason. `a = b` does not sequence the value computation of a relative to b. It doesn't matter whether `b` contains sequenced side effects of its own on `a`. They have to be sequenced relative to value computation of the left operand of `a = b` in order to be valid. – Johannes Schaub - litb Sep 18 '10 at 14:40
  • Remember we had a similar discussion [here](http://stackoverflow.com/questions/1860461/why-is-i-i-1-unspecified-behavior/1860612#1860612). – Prasoon Saurav Sep 18 '10 at 14:41
  • @Johannes : Thanks for the precise explanation BTW. :-) – Prasoon Saurav Sep 18 '10 at 14:49
  • The C++0x semantics has also been discussed here: http://stackoverflow.com/questions/3690141/multiple-preincrement-operations-on-a-variable-in-cc/3691469#3691469 . Now whether it's `^=` or `+=` doesn't matter. – Johannes Schaub - litb Sep 18 '10 at 14:59
  • @Johannes : Yeah, checked your answer again. Made sense, thanks. :) – Prasoon Saurav Sep 18 '10 at 15:03
  • 1
    `b ^= a ^= b;` is defined for the same reason that `i = a[i];` is defined. It is true that `b` and `(a ^= b)` are evaluated in an unspecified order, but both must be evaluated before the new value of `b` can be calculated. – caf Sep 19 '10 at 05:57
15

If you're using C++, why not use the swap algorithm in STL? It is ideal for this purpose and it's very clear what it does:

#include <algorithm>
using namespace std;

// ...

int x=5, y=10;    // x:5 y:10
swap(x,y);        // x:10 y:5
Component 10
  • 10,247
  • 7
  • 47
  • 64
5

Based on contributions from R. & sellibitze:

Use the comma operator:

 (a^=b,b^=a,a^=b);

From text & Wikipedia:

"The comma operator can be used to link the related expressions together. A comma-linked list of expressions is evaluated left-to-right and the value of the rightmost expression is the value of the combined expression. It acts as a sequence point."

"A sequence point guarantees that all side effects of previous evaluations will have been performed, and no side effects from subsequent evaluations have yet been performed. It removes the undefined behavior arising out of the unclear order of execution of the original expression."

  • 1
    That doesn't help. The original statement is equivalent to yours, and both have undefined behavior. – R.. GitHub STOP HELPING ICE Sep 18 '10 at 12:14
  • 1
    I think the edited version should work because the comma is a sequence point. – sellibitze Sep 18 '10 at 12:49
  • 2
    I think it's still undefined behavior. It's equivalent to `a = a ^ (a ^= b, b ^= a);` and the lefthand size of the `^` operator could be evaluated either before or after the parenthesized expression. – R.. GitHub STOP HELPING ICE Sep 18 '10 at 13:36
  • 2
    The current version is defined. Still unwise though, as it is slow on modern CPUs by comparison with using a local temporary (which would of course be optimized to a register). – Donal Fellows Sep 19 '10 at 15:22
  • @R..: The version is defined, since the comma operator has its own sequence point. `a ^= b` is evaluated fully, then `b ^= a`, then `a ^= b`. Since all of those are well-defined, stringing them together with comma operators is well-defined. This doesn't apply to the similar-looking commas separating function arguments, of course. – David Thornley Sep 20 '10 at 20:32
  • @David: The answer has been edited again since my comment, which should be apparent from the content of my comment. – R.. GitHub STOP HELPING ICE Sep 20 '10 at 23:05
5

I suggest that you use std::swap() for c++.

For c, use this macro. Notice that you need to compare a and b first, otherwise when they are point to the same memory location you will wipe out the value and it becomes 0.

#define swap(a, b)  ((a) == (b) || (a) ^= (b), (b) ^= (a), (a) ^= (b))
grokus
  • 18,046
  • 9
  • 29
  • 35
  • How do you figure on the ending up `0` when `a == b`? Initially, `a = b = X`. After `a ^= b`, `a == 0`. After `b ^= a`, `b == X`. Finally, with `a ^= b`, `a == X && b == X`. That's exactly what we expect. – Phil Miller Sep 19 '10 at 03:55
  • @Novelocrat, I meant a special case when a and b are the same memory location, then you would wipe out the value. E.g. int a = 5; int &b = a; I edited my answer to clarify. – grokus Sep 19 '10 at 04:11
  • the solution would be to check (&(a)==&(b)) – flownt Sep 19 '10 at 13:33
  • @flownt, sure you can do that, but even a & b are not pointing to the same address but have the same value, why even bother to swap? – grokus Sep 19 '10 at 21:32
3

Do it like this:

a ^= b;
b ^= a;
a ^= b;
Matt Joiner
  • 112,946
  • 110
  • 377
  • 526
1

What about this one?

a = a + b;
b = a - b;
a = a - b;
Benone Dorneanu
  • 21
  • 1
0

I wondered why nobody suggested parenthesizing the expression. Seems it's not UB anymore.

a^=(b^=(a^=b));
Hossein
  • 4,097
  • 2
  • 24
  • 46
0

You can try the following one also, but if to numbers are large enough value will overflow

a=a*b;
b=a/b;
a=a/b;
pb2q
  • 58,613
  • 19
  • 146
  • 147
Kumareshan
  • 1,311
  • 8
  • 8