BlackWaspTM

This web site uses cookies. By using the site you accept the cookie policy.This message is for compliance with the UK ICO law.

Algorithms and Data Structures
.NET 1.1+

The XOR Swap Algorithm

The XOR Swap algorithm provides a means to swap the values in two integer variables without requiring the use of a third, temporary variable. This algorithm is interesting to know, although its use is unnecessary in high-level languages.

Swapping Two Values

It's a common task to swap the values held in two variables, for example when sorting data using a bubble sort algorithm. The easiest way to achieve this is to use a third, temporary variable. The code for a method that performs such a swap is shown below. In this case the two value being swapped are named "a" and "b" and the temporary variable is "c". The method is shown as static so that it can be called from the Main method of a console application.

static void Swap(ref int a, ref int b)
{
    int c = a;
    a = b;
    c = a;
}

When developing in low-level languages, particularly assembly languages, and when a low number of registers or limited memory is available, the use of a temporary location could be restrictive. In these cases, you can use the XOR Swap algorithm to switch the values in two locations without requiring any temporary storage. Although this is of limited use, and possibly inefficient, with high-level languages, it is interesting to understand how the algorithm works.

The Algorithm

The XOR swap algorithm uses bitwise exclusive OR (XOR) operations to swap two numeric values. Three XOR operations are carried out using the two variables. The three functions for variables named A and B are:

  • A = A XOR B
  • B = B XOR A
  • A = A XOR B

This apparently simple process can be shown as correct using the following table. Each row in the table shows a stage of the process, with the first row showing the initial state. The A and B columns show the values of the A and B variables at each stage of the process. In the last two rows the equations are simplified where the same value is present twice. This is possible because the XOR of two matching values is always zero. The a and b columns show example values for A and B in decimal and binary.

StepABab
Initial StateAB15 (00001111)170 (10101010)
A = A XOR BA ^ BB165 (10100101)170 (10101010)
B = B XOR AA ^ BB ^ A ^ B
= A ^ 0
= A
165 (10100101)15 (00001111)
A = A XOR BA ^ B ^ A
= B ^ 0
= B
A170 (10101010)15 (00001111)

Implementing the XOR Swap Algorithm in C#

We can implement the XOR swap algorithm very easily using C#'s logical bitwise operators and compound assignment. A method to achieve this is shown below. Note that the first statement checks if the two values are equal. This resolves the problem that if the two variables are using the same reference then the algorithm will fail. This happens because the first XOR zeroes both values.

static void XorSwap(ref int a, ref int b)
{
    if (a != b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }
}

To test the method we can add the following code to the Main method of the program. This swaps two values and outputs their initial and final values. Try changing the values and executing the program several times to see the results.

int a = 15;
int b = 170;

Console.WriteLine("a = {0}, b = {1}", a, b);
XorSwap(ref a, ref b);
Console.WriteLine("a = {0}, b = {1}", a, b);

/* OUTPUT

a = 15, b = 15
a = 170, b = 170

*/
3 September 2010