cww.blog!

I've been wondering something for a long time and have never bothered to research the answer. It's a really useful trick in computer programming, though from an application programming standpoint, there are other ways to do it that are just as good (the Assembly XCHG operator on most machines these days, for example). It's also a really useful thing to know if you're about to walk into an interview for a programming position.

The question is this: given two integers, how do you swap their values without using temporary storage?

The answer is this: xor the second into the first, xor the first into the second, then xor the second into the first again.

I wrote a little C program to make sure it worked. :)

#include <stdio.h>

  

int main(int argc, char *argv[])

{

  int a = 123456;

  int b = 654321;

  

  a ^= b;

  b ^= a;

  a ^= b;

  

  /* output: 654321 123456 */

  printf("%i %i\n", a, b);

  

  return 0;

}

Technically, this works because of the symmetric difference property of the logical exclusive disjunction. The symmetric difference property also does other interesting things about which I already knew, like making an xor operation look exactly like an addition modulo 2 and like being the only reason RAID 6 maintains parity integrity.

I came across this while looking for ways to express the xor function in boolean algebra other than the normal way, (a' b) + (a b'). The expression I ended up using, by the way, is (a' + b')(a + b). It is already in conjunctive normal form, which is what I need for my application.

Wow, wasn't that an exciting post?

It's definitely leftover Thai red curry time.