swap(x,y)

[Daniel E. Platt]

In article <MYwDEFy00WB842JEUx at andrew.cmu.edu>, tg1e+ at andrew.cmu.edu (Timothy R. Gottschalk) writes:
> 
>        To swap two variables x,y in C without using a temporary variable:
> 
>        /* begin swap */
>        x += y;
>        y = x - y;
>        x -= y;
>        /* end swap */
> 
>        Just curious...(this looks pretty valid) does anyone know an even
> simpler method?  I would never program this way -- it's more of a theory
> question.  I've been told that it can't be done (???).
> Tim Gottschalk
> Pgh, PA


One way that works with bit patterns is:

x ^= y;
y ^= x;
x ^= y;

(If I'm not mistaken, ^ is exclusive or.  If not, that's what I mean
in the above expression.)

For a proof:

x ^ (x ^ y) = (x ^ x) ^ y = 0 ^ y = y.
y ^ (x ^ y) = x ^ (y ^ y) = x ^ 0 = x.

Then,

x ^= y;  /* x now contains x ^ y */
y ^= x;  /* y now contains y ^ (x ^ y) = x */
x ^= y;  /* x now contains x ^ (x ^ y) = y */

Is this what you had in mind?

By the way, this is a trick commonly used in processing bitmapped
graphics -- such as in X11 or Macintosh stuff.

Dan Platt
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
||                                     1(914)945-1173            ||
||        Dan Platt                    1(914)941-2474   		 ||
||        Watson (IBM)                 PLATT at YKTVMV.BITNET       ||
||                           ..!uunet!bywater!scifi!ndla!platt   ||
||                                                               ||
||     The opinions expressed here do not necessarily reflect    ||
||                   those of my employer!                       ||
||                                                               ||
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-