[comp.lang.c] Obfuscated SWAP

ken@aiai.ed.ac.uk (Ken Johnson) (08/23/89)

Well, I tried it and it works, at least in the example I chose.  This
code

main( )
{
	int x, y;

	x = 12;
	y = 3;

	x ^= y ^= x ^= y;	/* Swap X and Y over */

	printf("x = %d\ny = %d\n",x,y);
}

produces this output:

x = 3
y = 12

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

-- 
Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN
E-mail ken@aiai.ed.ac.uk, phone 031-225 4464 extension 212
`I have read your article, Mr.  Johnson, and I am no wiser than when I
started.' -- `Possibly not, sir, but far better informed.'

mpl@cbnewsl.ATT.COM (michael.p.lindner) (08/25/89)

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

ccdn@levels.sait.edu.au (DAVID NEWALL) (08/25/89)

In article <784@skye.ed.ac.uk>, ken@aiai.ed.ac.uk (Ken Johnson) writes:
> Well, I tried it and it works
>
>       x ^= y ^= x ^= y;       /* Swap X and Y over */
>
> I don't understand how it works


The intent of this code is clear.  It is intended to work like this:

Given the variables x and y, which have initial values a and b respectively.
Then:

       x ^= y ^= x ^= y
       |    |    |    |
       |    |    |    x = a, y = b
       |    |    |
       |    |    x = a ^ b, y = b
       |    |
       |    y = b ^ (a ^ b) = (b ^ b) ^ a = a, x = a ^ b
       |    => y = a, x = a ^ b
       |
       x = (a ^ b) ^ a = (a ^ a) ^ b = b, y = a
       => x = b, y = a

(You realise, of course, that ^ is the exclusive or operator)


David Newall                     Phone:  +61 8 343 3160
Unix Systems Programmer          Fax:    +61 8 349 6939
Academic Computing Service       E-mail: ccdn@levels.sait.oz.au
SA Institute of Technology       Post:   The Levels, South Australia, 5095