Path: utzoo!attcan!uunet!ginosko!gem.mps.ohio-state.edu!tut.cis.ohio-state.edu!att!cbnewsl!mpl
From: mpl@cbnewsl.ATT.COM (michael.p.lindner)
Newsgroups: comp.lang.c
Subject: Re: Obfuscated SWAP
Summary: based on behavior of exclusive or
Keywords: swap
Message-ID: <1615@cbnewsl.ATT.COM>
Date: 24 Aug 89 18:30:27 GMT
References: <784@skye.ed.ac.uk>
Organization: AT&T Bell Laboratories
Lines: 54

In article <784@skye.ed.ac.uk>, ken@aiai.ed.ac.uk (Ken Johnson) writes:
To: ken@aiai.UUCP
Subject: Re: Obfuscated SWAP
In-reply-to: your article <784@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@attunix.att.com
AT&T Bell Laboratories