Path: utzoo!utgpu!water!watmath!clyde!cbosgd!ihnp4!ptsfa!ames!amdahl!dlb!megatest!djones
From: djones@megatest.UUCP (Dave Jones)
Newsgroups: comp.lang.c
Subject: XOR-trick and PUZZLE (was comma-operator)
Message-ID: <226@goofy.megatest.UUCP>
Date: 23 Jan 88 00:19:59 GMT
References: <269@vsi1.UUCP>
Organization: Megatest Corporation, San Jose, Ca
Lines: 51


 SWARBRICK FRANCIS JOHN writes:
>
> #define swap(a,b) ((a) = ((b) = ((a) = (a) ^ (b)) ^ (b)) ^ (a))
>
> Try that, and tell me what you think.  A super-genius friend of mine figured
> it out.  He says it will work for anything (int, char *, etc.).  But it
> sure boggles my mind...
>

Of course, I can't be sure, but I rather suspect that your super-genius friend
may have been just a little lax about attributing sources.  I found out
about the XOR trick in 1979, but it is much older. I don't know who,
if anybody, is credited with having discovered it first.

In lay-hacker's terms, the reason it works is that A ^ B works like a 
"diff" file.  It sets a bit in each position where A and B differ.
Thus if you have A and (A^B) sitting around, you can recover B.
And guess what?  The XOR also acts like "sed" in recovering the old
value from the new value and the diff.

Mathematically speaking,

  for all (A,B) in 0..1 X 0..1

	(A^B)^A = B

There are only four cases to verify.  Check it out.


PUZZLE for those lucky enough not to have seen it previously:

How can you use the XOR trick to keep a doubly linked list, using only
one field for in each record, to code for finding both the following and 
the previous record?  

(Please do not post solutions to the net.  If you can't get
it and want the spoiler, send me email directly, and I'll be happy to
spoil it.)

Have fun XORing.

		Dave Jones
		Megatest Corp.
		880 Fox Lane
		San Jose, CA.
		95131

		(408) 437-9700 Ext 3227
		UUCP: ucbvax!sun!megatest!djones
		ARPA: megatest!djones@riacs.ARPA