cbitwise-xor

Is there a case where bitwise swapping won't work?


At school someday several years ago I had to do a swap function that swaps two integers, I wanted to do this using bitwise operations without using a third variable, so I came up with this:

void swap( int * a, int * b ) {
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

I thought it was good but when my function was tested by the school's correction program it found an error (of course when I asked they didn't want to tell me), and still today I don't know what didn't work, so I wonder in which case this method wouldn't work.


Solution

  • I wanted to do this using bitwise operations without using a third variable

    Do you mind if I ask why? Was there a practical reason for this limitation, or was it just an intellectual puzzle?

    when my function was tested by the school's correction program it found an error

    I can't be sure what the correction program was complaining about, but one class of inputs this sort of solution is known to fail on is exemplified by

    int x = 5;
    swap(&x, &x);
    printf("%d\n", x);
    

    This prints 0, not 5.

    You might say, "Why would anyone swap something with itself?" They probably wouldn't, as I've shown it, but perhaps you can imagine that, in a mediocrely-written sort algorithm, it might end up doing the equivalent of

    if(a[i] < a[j]) {
        /* they are in order */
    } else {
        swap(&a[i], &a[j]);
    }
    

    Now, if it ever happens that i and j are the same, the swap function will wrongly zero out a[i].

    See also What is the difference between two different swapping function?