How two swap two values (was: Brain Teaser)

[Mark Harrison]

In article <10289 at wpi.wpi.edu>, oesterle at wpi.wpi.edu (Shawn H. Oesterle) writes:
> 
> Problem:
> 	Swap two pointers without using a third pointer.
> 	[...]
> 	Make a piece of code which has the same effect as this, but without
> 	using the 'tmp' variable (in C, of course).

In the assembler world, it is common to see this piece of code to swap two
values:

	a ^= b;
	b ^= a;
	a ^= b;

(Of course, it is more common to see it in assembler than c ;-))  If you
are wanting to swap pointers, you will have to cast them to the appropriate
integral type.

The proof can be derived by three methods:

	1.  Try it, it works!

	2.  Using the XOR truth table for the possible 1-bit combinations
	    of a and b: (0,0),(1,0),(0,1),(1,1).  Since it works for one
	    bit, and the XOR operator works on sets of bits (ie ints),
	    it works for ints.

	3.  An elegant proof that I don't know about... If you know it
	    please send it to me!

Proofs are, of course, left as an exercise to the reader.


-- 
Mark Harrison             harrison at necssd.NEC.COM
(214)518-5050             {necntc, cs.utexas.edu}!necssd!harrison
standard disclaimers apply...