Integer data types can be swapped with extreme speed using a triple-XOR operation. This operation uses no temporary variables, which is probably a factor in its speed.
XOR means eXclusive OR. In English, "A or B but not both". It is unique among the basic boolean operations in that it preserves information - given any two of A, B, and (A XOR B), the third can be calculated. This is not true with AND, OR, NAND, or NOR; with all of these, a certain value of A (1 for Or/NOR, and 0 for AND/NAND) makes the value of B irrelevant. Not so with XOR.
A useful definition of XOR in this context is this: "If B is true,
flip A, otherwise leave A as it is". Looking at it this way, it is
clear that (A XOR B) XOR B gives you A back again - the
bits that are flipped in the first XOR are flipped back in the
second. The ones that aren't are left alone both times.
So here's the magic fast-swap algorithm:
Simple, no? Three simple logic instructions, and no temporary variables. Using this as an inline function, where A and B are references to integers, increased my quicksort implementation by a lot (several tenths).
Such logic operations are only legal in C for integer values (both signed and unsigned). They are NOT valid for floating-point numbers or pointers.
In practice, you can get away with this with casts, such as
*(int*)&a. That is, get the address of that variable,
cast the resulting pointer to an int pointer, then dereference it
back.
There are problems with doing this.
First, as a matter of principle, it's sneaky, and will make your code harder to read. On the other hand, there's no way to do it nicely for non-ints.
Second, if you cast to a data type of a different size, all hell will break loose, unless you're running Linux, which doesn't have much hell in it. At best, it won't work. Any assumptions about data sizes will probably not hold for all machines. In short, it's not very portable.
Third, if you try it with pointers in a garbage-collecting system, you run a small (but non-zero) risk of royally fucking up garbage collection. In the above sequence, during step 2, the pointer originally known as B does not exist in memory. If GC runs in this brief moment, whatever B pointed to may be freed, and the Demons of Wrongly Freed Memory will rip your arms off next time you dereference B.