Obfuscated SWAP

[michael.p.lindner]

In article <784 at skye.ed.ac.uk>, ken at aiai.ed.ac.uk (Ken Johnson) writes:
To: ken at aiai.UUCP
Subject: Re: Obfuscated SWAP
In-reply-to: your article <784 at skye.ed.ac.uk>
News-Path: att!tut.cis.ohio-state.edu!gem.mps.ohio-state.edu!ginosko!uunet!mcsun!ukc!edcastle!aiai!ken

>       x ^= y ^= x ^= y;       /* Swap X and Y over */
>
> I don't understand how it works, but I do now understand why C
> programmers have a reputation for going around showing each other bits
> of paper and saying `I bet you can't guess what this does!'
>
> Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN

Why does it work?  Well, "op=" operators associate right to left, so

	x ^= y ^= x ^= y;

is the same as

	x ^= (y ^= (x ^= y));

which is the same as

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

or, finally (bear with me now)

	x = x ^ y;	/* equation a */
	y = y ^ x;	/* equation b */
	x = x ^ y;	/* equation c */

Now, let's do some substitutions:
	substituting a for x in b, we get:
		y = y ^ (x ^ y)
	which is
		y = y ^ (y ^ x)
	which is
		y = (y ^ y) ^ x
	which is
		y = 0 ^ x
	which is
		y = x	/* equation d */

	Subtituting a for x in c, and d for y in c, we get:
		x = (x ^ y) ^ x
	which reduces, as above, to
		x = y

Mike Lindner
attunix!mpl or mpl at attunix.att.com
AT&T Bell Laboratories