Weird XOR swap behavior while zeroing out data

Question

Thanks Doug. Here's the fix:

void swap(int& a, int& b) {
    if (&a == &b) // added this check to ensure the same address is not passed in
        return;

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

I am implementing quicksort for fun in C++, and I am using integers for dummy data. I had been using the XOR swapping algorithm to swap two values in place, but I noticed my sort was screwing up. I changed my swapping algorithm and it worked. I added some debugging statements, and found that the XOR swap was doing something weird.

I printed the data before and after I swapped it, and this is what it printed:

...

swapping -5, -3
swapped  -3, -5

swapping -5, -5
swapped  0, 0     <---- What?

swapping -2, -4
swapped  -4, -2

...

Here is my code:

// this might not be that great or even work as intended but it doesn't really matter for this problem
int av3index(int a[], int indx1, int indx2, int indx3) {
    if (a[indx3] <= max(a[indx1], a[indx2]) && a[indx3] >= min(a[indx1], a[indx2]))
        return indx3;

    if (a[indx2] <= max(a[indx1], a[indx3]) && a[indx2] >= min(a[indx1], a[indx3]))
        return indx2;

    if (a[indx1] <= max(a[indx2], a[indx3]) && a[indx1] >= min(a[indx2], a[indx3]))
        return indx1;
}

void swap(int& a, int& b) {
    /*
    This works
    int tmp = b;
    b = a;
    a = tmp;*/

    cout << "swapping " << a << ", " << b << endl;

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

    cout << "swapped  " << a << ", " << b << endl << endl;
}

void zqsort(int a[], int len) {
    if (len <= 1)
        return;

    int pivot = av3index(a, 0, len / 2, len - 1);

    swap(a[pivot], a[0]);

    int i = 1, j = len - 1;

    while (i <= j) {
        if (a[i] > a[0]) {
            while (i <= j && a[j] > a[0])
                --j;

            if (i <= j)
                swap(a[i], a[j]);
        }

        ++i;
    }

    swap(a[0], a[j]);

    zqsort(a, len / 2);
    zqsort(a + len / 2, len - len / 2);
}

int main() {
    int values[] = {5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5};

    int len = sizeof(values) / sizeof(int);

    int* arr = new int[len];

    for (int i = 0; i < len; ++i)
        arr[i] = values[i];

    zqsort(arr, len);

    cout << "sorted array:" << endl;
    for (int i = 0; i < len; ++i)
        cout << arr[i] << endl;

    cin.get();
}

I didn't use any references for the quicksort code so it might be wrong, but I don't think that's germane to the problem.

Using this XOR might actually be slower than the usual two value swap using a temp variable; the fact that you are writing through references suggests you are forcing the compiler to do 3 memory (ok, cache line) writes, whereas temp-style swamp should only do two memory write (any intelligent compiler will put the temp in the registers). Adding the conditional check surely makes it slower. So while this might be fun, it probably isn't a practical thing to do in a sort. — Ira Baxter, Apr 26 '11 at 02:23
true, but xor swap isn't meant to speed up, but to avoid temporary. In this case, I'd say the ultimate reason is to have fun. — Michael Krelin - hacker, Apr 26 '11 at 10:16

Doug Currie · Accepted Answer · 2011-04-26T02:07:22.363

17

Your swap a and b are the same location. The XOR hack only works when they are different locations.

I think in C; here's a table:

           &a != &b  &a == &b
           *a   *b   *a   *b
           -5   -5   -5   -5
*a ^= *b;   0   -5    0    0
*b ^= *a;   0   -5    0    0
*a ^= *b;  -5   -5    0    0

edited Apr 26 '11 at 02:07

answered Apr 26 '11 at 01:59

Doug Currie

40,708
1
95
119

Paul R · Answer 2 · 2011-04-26T12:13:16.990

1

In addition to the existing answers, I'll just add that if you're going to do a test before swapping then you might as well change:

if (&a == &b) // added this check to ensure the same address is not passed in
    return;

to:

if (a == b) // check that values are different
    return;

This will handle the case where &a == &b and also the case where a == b, which may save some unnecessary swapping.

edited Apr 26 '11 at 12:13

answered Apr 26 '11 at 06:33

Paul R

208,748
37
389
560

score 0 · Answer 3 · answered Apr 26 '11 at 01:59

0

Anything xor'd with itself is zero.

answered Apr 26 '11 at 01:59

Jeff Paquette

7,089
2
31
40

Weird XOR swap behavior while zeroing out data

3 Answers3

Linked