Problem

Write a function to swap two number in place without temporary variables.

Solution

Method1 - The XOR or Exclusive trick

In C this should work:

a ^= b ^= a ^= b;

to simplify :

a=a^b;
b=a^b;
a=a^b;

OR

a^=b;
b^=a;
a^=b;

Following are operations in XOR

  • 0^0=0
  • 0^1=1
  • 1^0=1
  • 1^1=0

Hence, we have:

  • a=a^b: ‘a’ will save all the bits that a differs from b: if the bit that ‘a’ and ‘b’ differ, it gets 1, otherwise 0.
  • b=a^b: ‘b’ will compare to the difference between a and b: for the bit that ‘b’ and ‘a’ differ, it means a have 1 at this position and the result of a^b will assign that bit to 1; for the bit that ‘b’ and ‘a’ agree, it means a have 0 at this position and the result of a^b will assign that bit to 0.
  • a=a^b:  same logic

Although the code above works fine for most of the cases, it tries to modify variable ‘a’ two times between sequence points, so the behavior is undefined. What this means is it wont work in all the cases. This will also not work for floating-point values. Also, think of a scenario where you have written your code like this

Now, if suppose, by mistake, your code passes the pointer to the same variable to this function. Guess what happens? Since Xor’ing an element with itself sets the variable to zero, this routine will end up setting the variable to zero (ideally it should have swapped the variable with itself). This scenario is quite possible in sorting algorithms which sometimes try to swap a variable with itself (maybe due to some small, but not so fatal coding error). One solution to this problem is to check if the numbers to be swapped are already equal to each other.

Code

C
swap(int *a, int *b) {
  if (*a != *b) {
    *a ^= *b ^= *a ^= *b;
  }
}
Java

In Java, rules for subexpression evaluations are clearly defined. The left hand operand is always evaluated before right hand operand (See this for more details). In Java, the expression x ^= y ^= x ^= y; doesn’t produce the correct result according to Java rules. It makes x = 0. However, we can use x = x ^ y ^ (y = x); Note the expressions are evaluated from left to right. If x = 5 and y = 10 initially, the expression is equivalent to x = 5 ^ 10 ^ (y = 5);.

x = x ^ y ^ (y = x);
Python

Python is simpler:

x, y = y, x

Method 2 - Simple addition and subtraction (All languages)

This method is also quite popular

a=a+b;
b=a-b;
a=a-b;

OR

a =((a = a + b) - (b = a - b));

But, note that here also, if a and b are big and their addition is bigger than the size of an int, even this might end up giving you wrong results.