Thread: bitwise hack for swapping

Looking at how to use the bitwise operators, I ran across the following technique for swapping two values, which I think should work for any primitive data type (as long as a and b have distinct memory locations), and which doesn't require creating an extra variable:

Code:

/*
code that determines (primitive) datatypes of a and b and assigns values
*/
a ^= b;   // now a has a bit set only in those spots where 1 of a and b had a bit set
b ^= a;  // now b is set to the value of the original a
a ^= b;  // now a is set to the value of the original b

Isn't this technique invariably faster (in addition to conserving a little memory, which presumably doesn't really matter) than the normal technique of using a temporary variable?

nice, tx!
i do think i'll start using xor method as default here. seems a little neater--and why not gain that little bit of extra speed?

Hmmmm... well, after that I tried it with signed int and long and it worked, but refused to compile using Netbeans (gnu) under Windows for double.

Sorry, I don't see the point.

only useful for certain circumstances

O_o

You said a mouthful.

For example, I've never seen a single valid use.

Soma

The XOR method introduces data dependency on each step. The CPU won't be able to execute them in parallel.

Each instruction requires the result of the previous instruction.

Code:

t = a;
a = b;
b = t;

Also 3 instructions, but the only dependency is the third instruction must occur after the first. The CPU can execute first 2 instructions in parallel, using register renaming ("ghost" registers to speed things up). With clever renaming, it may even be possible to do it in 1 instruction cycle (renaming both registers, and copy from old registers at the same time), but that I'm not sure.

When not constrained by the number of available registers, the tmp method will most certainly be faster.

What makes you think the xor method is faster? Because it's more cryptic?

Salem, if, assuming a and b are in different memory locations (that's critical), i don't see why the only issue isn't whether xor is defined for the given data type. if it is, then the swap clearly works.

i'm also not seeing the decrease in dependencies for possible parallel processing either. for
t = a;
a = b;
b = t;

clearly step 3 must also occur after step 2, or else a didn't get changed.

i do see the dangers in using it with dereferenced pointers, as in one of the threads Salem mentioned in his first post.

as to the standard for when you can use them, i'm not finding it. but the following links seem to indicate legitimacy for an integer type (but not floating point):
Bitwise Operators in C
Cprogramming.com - Tutorials - Bitwise Operators and Bit Manipulations in C and C++
i do find a cautionary statement in king's c book about using shift operations on signed integers (p. 510), and it's pretty obvious why that's the case specifically for bitwise shifting: you're shifting the sign bit, too, with no protection.
i don't see why that would pose problems with xor, though (?).

A modern optimizing compiler will probably do a better job making these kinds of optimization decisions than you can. They're quite good! Let's look at how different compiler optimization flags can affect the outcome of this program:

Code:

#include <Windows.h>
#include <iostream>
using namespace std;


int main()
{
    DWORD oldtick;
    unsigned int count, x, y, temp;

    //
    //  XOR swap
    //
    count = 0xFFFFFFFF;
    x = 0x00000000;
    y = 0xFFFFFFFF;
    oldtick = GetTickCount();
    while (count--)
    {
        x ^= y;
        y ^= x;
        x ^= y;
    }
    cout << "XOR swap time: " << (GetTickCount() - oldtick) << " ms" << endl;

    //
    //  Tmp swap
    //
    count = 0xFFFFFFFF;
    x = 0x00000000;
    y = 0xFFFFFFFF;
    oldtick = GetTickCount();
    while (count--)
    {
        temp = x;
        x = y;
        y = temp;
    }
    cout << "Temp swap time: " << (GetTickCount() - oldtick) << " ms" << endl;

    return 0;
}

(With MSVC)
Optimizations disabled

Code:

XOR swap time: 21497 ms
Temp swap time: 11154 ms

Optimize for speed

Code:

XOR swap time: 3807 ms
Temp swap time: 2527 ms

Full optimization

Code:

XOR swap time: 9906 ms
Temp swap time: 9267 ms

Optimize for size

Code:

XOR swap time: 3791 ms
Temp swap time: 2543 ms

Another XOR trick is to use it to zero-out memory, but guess what? Optimizing compilers use that too!

i'm also not seeing the decrease in dependencies for possible parallel processing either. for
t = a;
a = b;
b = t;

clearly step 3 must also occur after step 2, or else a didn't get changed.

They can happen at the same time, using register renaming. While b is being copied to a, the CPU can assign another physical register to be the "new b" from now on, and copy t to the new b at the same time. It's a "fake" dependency.

In the XOR thing, all dependencies are "real". You can't start the next XOR until you have the result of the previous XOR.