How to swap two integers without a temporary

This question is sometimes asked in interviews and it boils down to whether you know about and understand binary XOR.

Binary XOR

Binary XOR behaves in a slightly non intuitive way. Bits are compared between the two values and if they are the same the result is a 0 if they are different it is a 1.

e.g.   1 0 1 0 1 1
       0 0 1 1 1 1
     = 1 0 0 1 0 0

Now the way that you can use this to swap two numbers is due to the following property:
If you XOR two numbers A and B and get a result C, then XORing C with either A or B will give the other.

e.g. A ^ B = C
     C ^ A = B
     C ^ B = A

Using XOR to do the swap

So, the core idea of this swapping is to overwrite one of the two variables with the XOR result of both and then to use the remaining value to generate (using XOR) the value that was overwritten.
e.g.


  int A = 77;
  int B = 121;

  A = B ^ A; // A = C 
  B = B ^ A; // B = C ^ B = A
  A = B ^ A; // A = C ^ A = B

  std::cout << "A = " << A << "  -  B = " << B << std::endl;

This technique is not of much practical use but as a purely theoretical exercise I still find it somewhat interesting.

FacebookTwitterGoogle+RedditDeliciousLinkedInEvernoteSlashdot

Leave a Comment