swap(x,y)

[Tom Karzes]

In article <40 at dgis.daitc.mil> generous at dgis.daitc.mil (Curtis Generous) writes:
>tg1e+ at andrew.cmu.edu (Timothy R. Gottschalk) writes:
>>       To swap two variables x,y in C without using a temporary variable:

Here are some ways to do it:

    1.  x += y      y = x - y   x -= y
    2.  x -= y      y += x      x = y - x
    3.  x = y - x   y -= x      x += y
    4.  x ^= y      y ^= x      x ^= y

In each case, the operation used is such that given the value of x op y,
along with either x or y, one can recover the original value of the other
variable.

This reminds me of an old space saving trick for doubly linked lists.  One
can create a linked list which may be traversed in either direction using
a single pointer field.  In that field, store the xor (or the sum, or the
difference) of the predecessor and successor addresses.  (I know this isn't
legal C, so don't bother flaming.  The point is that it works on normal
computer hardware.)  All you have to do to traverse the list in a given
direction is keep the value of the previous node around and xor it with
the pointer field in the current node.  In fact, the code which does this
doesn't even have to know the direction in which it's going.  You just
have to keep pointers to the first and last elements, and seed the walk
at either end with a zero previous pointer.  The catch is that this
method only works for walking the list from the head or the tail.  You
can't start in the middle because you don't have any adjacent address
to get you started.  For example, you can't delete an element from the
list if all you have is its address; some additional context is needed.