Monday, January 17, 2011

Swapping two integers without using a temporary variable

This is another interesting algorithm using bit manipulation. For example, let's say we have two integers x = 3 and y = 2. Our goal is to swap x and y values so that x = 2 and y = 3 after the swap.

Traditionally, we just use a temporary variable, called temp for example, to store the swapping values:

void swapIntegers (int x, int y)
{
  int temp = x;
  x = y;
  y = temp;
}

However, the XOR operation can help us accomplish the above with no extra variable needed:

void swapIntegers (int x, int y)
{
  x ^= y;
  y ^= x;
  x ^= y;
}

That's it :) So why does it work? Well because of the property of XOR operation (^). Lets x = 3 and y = 2. The binary form of those two are x = 0011 and y = 0010.

  • First step, x ^= y --> 0011 XOR 0010 makes x = 0001.
  • Second step, y ^= x --> 0010 XOR 0001 makes y = 0011 = 3.
  • Third step, x ^= y --> 0001 XOR 0011 makes x = 0010 = 2.

No comments:

Post a Comment