Does this trick always work?

Question

Possible Duplicate:
Potential Problem in “Swapping values of two variables without using a third variable”

I recently read in a community that we can easily swap two numbers without using third using a XOR trick.

m^=n^=m^=n; trick was mentioned.

What do you guys think? Is this trick always useful?

No, it does not. Here you go: http://stackoverflow.com/questions/3741440/potential-problem-in-swapping-values-of-two-variables-without-using-a-third-vari/3741450 — codaddict, Oct 03 '10 at 08:22

score 5 · Answer 1 · answered Oct 03 '10 at 08:22

the way you have written it, it is undefined behavior. This is because you are modifying a variable more than once in the same sequence point. However if you rewrite it as follows:

m ^= n;
n ^= m;
m ^= n;

then it is safe. However, "useful" is another question, it is rarely "useful" and sometimes it is actually slower than actually using a temp!

Also you need to be careful with aliasing (pointers/references) because if you try to swap something with itself, then you end up accidentally zeroing your value. For example:

#define SWAP(m, n) { m ^= n; n ^= m; m ^= n; }

int x[] = { 1, 2, 3, 4 };
int i = 0;
int j = 0;
SWAP(x[i], x[j]); // whoops, x[0] == 0 now, not 1!

a more traditional swap implementation doesn't have this issue.

Mark Byers · Answer 2 · 2010-10-03T08:29:59.503

No, it is undefined behaviour in both C and C++. It may work sometimes, but you should not rely on it.

Also even the "fixed" variation doesn't always work:

m ^= n;
n ^= m;
m ^= n;

This fails if m and n are references to the same variable. In this case it sets the value to zero.

C doesn't have references but even in C there are still dangers lurking if you try to use this trick:

You may try to put the "working" version into a macro SWAP, but that can fail if called with SWAP(x, x), setting x always to zero.
You may try to extend the trick to swapping two values in an array, but again this can fail if you use the same index:
```
a[m] ^= a[n];
a[n] ^= a[m];
a[m] ^= a[n];
```

Now if m == n again the value of a[m] is set to zero.

Please don't use "clever" tricks like this. Use a temporary variable to swap two values.

score 1 · Answer 3 · answered Oct 03 '10 at 08:28

1

with that trick, you save an extra memory location to save a temporary value. It may be efficiant for integers, but is that readable ? Your last generation optimizer may do the same.

answered Oct 03 '10 at 08:28

Marc

11
1

Modern CPU's do better with a temporary. They can execute the two assignments in parallel, but they must stall for the XOR version. – GManNickG Oct 03 '10 at 08:47
@GMan: you mean instruction pairing? But which assignments can be paired in this case? – Nick Dandoulakis Oct 03 '10 at 09:05
@Nick: With `int temp = x; x = y; y = temp;`, the latter two. – GManNickG Oct 03 '10 at 09:20
@GMan: doesn't `y` add a dependency between the 2 instructions? Thus, no pairing due to a read after being written. The same also applies to the first 2 instructions, unless I'm missing something :) – Nick Dandoulakis Oct 03 '10 at 09:34
@GMan: yep, those last two can be paired :) I guess `mov x, y;` is a typo. It should be `mov x reg1;`. – Nick Dandoulakis Oct 03 '10 at 10:00
@Nick: In psuedo-assembly: `mov reg0, x; mov reg1, y; mov x, reg1; mov y, reg0;`. Two cycles does four-moves, two each. EDIT: I ninja'd you, sorry. :) – GManNickG Oct 03 '10 at 10:01

score 0 · Answer 4 · answered Oct 03 '10 at 08:21

It's often more of a danger (in your case it's actually undefined behavior; plus if one number is zero, things go wrong). Unless you're cripplingly low on memory, it's better to just use a temp variable (or the stl swap function). This is more clear about what you're doing and easier to maintain.

Does this trick always work?

4 Answers4