[C] XOR Challenge
 

Free cookie to the first person who can figure out what this little piece of C code is trying to accomplish:

What are the contents of x and y after this piece of code has run?

Warning: Submitter does not have any actual cookies to give out. Respondants will have to suffice with Submitter's admiration and respect. Void where prohibited.

Edit: This has already been answered below by HFrankenstein. Don't read any further if you want to do this challenge by yourself.

Here goes...

To make it easier to look at, stick some parens in there (though I believe it will produce a syntax error) [edit]VC++ doesn't seem to mind.[/edit]

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

The innermost statement (x ^= y) will set x = 100(bin) = 4(dec)

Then, the middlemost(?) statement (y ^= (x ^= y)) sets y = (101 ^ 100) = 1

Finally, the outermost statement x ^= (y ^= (x ^= y)) sets x = (100 ^ 001) = 101(bin) = 5(dec)

In effect, it switches x and y. I could show the algebra that proves that this works for any x and y, but I'm lazy, so bleh.

HFrankenstein, you have my admiration and respect, especially for such a detailed answer. :)

Yes indeed, it is a swapping algorithm that doesn't require a tertiary (temporary) variable. I believe it only works on integers (i.e. not floating points), and it should work for any combination of numbers (both positive and negative). As an additional benefit, the compiler can translate it into 3 simple XOR assembler statements, making it much more efficient to execute.

cute :)

Well, it "only works" on integers 'cause the compiler won't let you do anything else. This method can be used on anything that has a binary representation. On a computer, that's everything. C let's you do anything you want (it's popularity is probably largely due to this), so you can simply cast your floats and do your thing...

entertainment was writing that up on the whiteboard in the lab and watching the freshman scratch their heads. :D ;) thx for the day's amusement!!

wow, that has to be the coolest piece of code I have seen in a long time, thanks.

Can someone explain to me how this works? I don't understand the ^= at all.

Thanks

"x ^= y" is the same as "x = x ^ y". ^ is XOR.

does it return 0?

See my original answer (second post). It switches x and y.

I remember this peice of code... funny thing is this operation uses more lines of assembly code (4 instead of 3 if i remember correctly) and the same number of registers than a simple snippet like this:

int x = 5;
int y = 1;
int temp;

temp = x;
x = y;
y = temp;


So it is less efficient even though you can write it on one line. The code using XOR is also much harder for people to glance at and understand.
So remember kids, writing slick code like this isn't necessarily better.

Yeah it looks like it's a couple of cycles slower per swap. Unless there is some crazy x86 instruction I don't know about to do it better.

vs.

But these are of course the human-written versions; the Visual Studio compiler generates 9 xors and movs for the first one and 6 for the second.

Well, yes and no. The xor code isn't necessarily for everyone, but when you get down to writing hardcore assembly for systems level programming, you'll use the XOR version.

Also, as an amusing note, here's a funny bit:
Why XOR instead of movl $0,%eax? Because the XOR version is faster. :D