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