Yeah, this is really cool :)
A favorite of mine is the xor-swap: While not useful in pratice for me, you can get quite stunned faces if you tell your friends, that a swap is possible without a third variable.
x = x xor y
y = x xor y
x = x xor y
It's also possible to use addition and subtraction instead of xor.FWIW, pretty much every 3rd (penultimate) year engineering student in India knows the xor-swap, I should think (only they might not call it that, because they've just memorised the procedure, and have very little idea why it works... /cynical)
This is one of the most common questions in 'technical interviews' when big IT companies are recruiting fresh grads.
I am not sure where your cynicism or contempt is coming from. There is not much to a deeper understanding of xor-swap. If one knows the xor truth table one knows why it works, and knowing the truth table is essentially an act of memorization. I hope they are exposed to digital logic way before 3rd year. On the other hand cases where this will not work in the current form, perhaps needs a somewhat deeper understanding of bit lay out. Say if one were to swap two unicode characters from void * pointers to them.
My cynicism (not contempt - I know that the students are under various sorts of pressures) stems from personal experience.
It's not much good explaining how simple it is to understand the xor-swap - it doesn't change the fact that the majority of engineering students go to the link like the one I posted, compile a list of questions and answers, and rattle off answers before the question is even completed in the interviews.
It's like knowing [any interesting method] can be used to accomplish a task, without knowing why said method works.
edit: I realise all this is OT, but I was downvoted for my earlier post and felt the need to defend it.
Am I the only one that thinks this would be a really BAD interview question? There'd be no way to tell if the candidate had memorised the answer or had worked it out on the fly.
Re:Wikipedia: Making of Doom
by JeanPierre on Friday July 22, 2011 @07:51AM
(#2793132)
To elaborate on its usefullness: An XOR-swap is only useful when you do not have space for a new pointer, otherwise, making a new temporary variable will on most processors be faster than XOR-swapping.
Re:Wikipedia: Making of Doom
by onemoreact on Friday July 22, 2011 @10:10AM
(#2793558)
I would assume you need to be using regesters for three XOR's to be slower than a temperary variable.
been used in many-a-obfuscate-a-bug-contests for what happens when x == y.
I am sure there are many more such bit twiddling and magic number hacks, but nothing quite as useful to me than this magic to compute the reciprocal of a square root. The only other floating point operations that comes up this frequently in what I do are log and exp.
In my day to day coding (not that I code every day, far from it) I have nothing to do with game engines, yet inverse square root shows up in almost every corner (pun intended) in the vector manipulation code, for example in finding the cosine similarity between two documents.
Does not work for double precision, 64 bit, and nothing I write is so performance critical that it demands the use of this trick, but its still fun
Taken from the wikipedia article http://en.wikipedia.org/wiki/Fast_inverse_square_root has the fuller story.