1

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.

SuperStormer
  • 4,997
  • 5
  • 25
  • 35
Fayeure
  • 1,181
  • 9
  • 21
  • XOR swapping is just being so clever you outsmarted yourself. Count the loads, stores, and xor operations, and compare that to "load `a` into `r1`, load `b` into `r2`, store `r2` into `a`, store `r1` into `b`". – Andrew Henle Sep 30 '22 at 22:47
  • 7
    It will fail if someone calls `int x = 5; swap(&x, &x);`. – Steve Summit Sep 30 '22 at 22:48
  • @SteveSummit And undefined behavior results if any of the signed `int` values is an overflow. – Andrew Henle Sep 30 '22 at 22:50
  • @SteveSummit Oh yeah, it's true in the first statement `*a = *a ^ *b` it just sets `*a` (and `*b`) to 0 – Fayeure Sep 30 '22 at 22:52
  • 2
    @AndrewHenle What do you mean by overflow ? How could it overflow since we're just modifying the bits ? – Fayeure Sep 30 '22 at 22:53
  • 1
    Andrew might have been thinking of the [alternative swap formulation involving subtraction](https://stackoverflow.com/questions/58462258) instead of XOR. – Steve Summit Sep 30 '22 at 22:54
  • @Fayeure [Some operators (the unary operator ~, and the binary operators <<, >>, &, ^, and |, collectively described as bitwise operators) are required to have operands that have integer type. These operators yield values that depend on the internal representations of integers, **and have implementation-defined and undefined aspects for signed types**.](http://port70.net/~nsz/c/c11/n1570.html#6.5p4) For example, something like `~INT_MAX` might very well be a trap representation. You out-clevered yourself when you decided to be obscure with code. – Andrew Henle Oct 05 '22 at 00:09

1 Answers1

4

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?

Steve Summit
  • 45,437
  • 7
  • 70
  • 103
  • No there wasn't any particular reason, it was just for my personnal knowlege and because I saw this method in a book and I liked it. So if I just add `if (a == b) return ;` at the beginning it should work then ? – Fayeure Sep 30 '22 at 22:59
  • @Fayeure As far as I know that would have worked. – Steve Summit Sep 30 '22 at 23:08
  • If `a[i] > a[j]`, surely `i != j` (for integers anyway). – Nelfeal Sep 30 '22 at 23:10
  • @Nelfeal Ah, yes. I guess I really meant `>=`. Fixed, thanks. – Steve Summit Sep 30 '22 at 23:20
  • Well, now if `a[i] == a[j]`, there is no point in swapping the values. I guess the code must be poorly written to end up in such a situation. – Nelfeal Sep 30 '22 at 23:28
  • 1
    @Nelfeal Exactly. Thus, "mediocrely-written". (But: my goal was to present *a* scenario under which the posted `swap()` function could fail, not a *good* one! :-) ) – Steve Summit Sep 30 '22 at 23:31