Suppose you have two binary integers A and B.<\/p>\n\n\n\n
You want to swap them so that A becomes B and B becomes A, but you don’t have any extra memory. If you start with A=B<\/strong> , for instance, the information that was in A is lost.<\/p>\n\n\n\n Can this be done? Surprisingly, yes, using the XOR swap <\/a>algorithm:<\/p>\n\n\n\n A = A XOR B;<\/strong> A is first changed to be a bitwise XOR of itself and B. As long as B is still available, the information in A could be recovered by repeating the operation.<\/p>\n\n\n\n Next, B is XORed with the new value of A. This leaves B with the information that was originally in A. Since A still contains the combination, both pieces of information are still recoverable. <\/p>\n\n\n\n Finally, A is XORed with B. Since B contains the original value that was in A, A will now contain the other half of the information — the value originally in B.<\/p>\n\n\n\n Now, for the story behind the story…<\/p>\n\n\n\n The idea, once known, is easy enough to prove — but I wanted to know who had come up with it. I tried asking ChatGPT, and it knew exactly the algorithm I was talking about, and rephrased what it does. It then very confidently said that it was discovered by Richard Hamming<\/a> in the 1950s, and gave textbook and paper citations of his to back it up.<\/p>\n\n\n\n Very impressive — except it seems to be a hallucination. Maybe Hamming did<\/em> discover the XOR swap. It wouldn’t surprise me at all. (After all, he’s the Hamming in “Hamming codes.” But the two references ChatGPT gave were duds. Hamming does mention XOR in his book on communications, but only briefly, where it is relevant to error-correcting codes.<\/p>\n","protected":false},"excerpt":{"rendered":" Swap two binary integers, without using a temporary variable. Not magic — XOR. Continue reading
B = B XOR A;<\/strong>
A = A XOR B;<\/strong><\/p>\n\n\n\n