Swap Variable Values ​​Without a Temporary Variable

The problem

One of the first problems that we learned in computer science is how to sort data. There are a lot of well known algorithms to achieve that.

To solve this problem, one of the things that we must do is swap values within a collection.

For the sake of simplicity, we will use the simplest sorting algorithm known as Bubble Sort.

#include <stdio.h>

void swap(int* a, int* b) {

  int temp = *a;
  *a = *b;
  *b = temp;

  return;

}

void bubbleSort(int* arr, int size) {

  for(int i = 0; i < size; ++i) {

    for(int j = 0; j < size-i-1; ++j) {

      if(arr[j] > arr[j+1]) {
        swap(&arr[j], &arr[j+1]);
      }

    }

  }

  return;

}

int main(void) {

  int size = 8;

  int arr[8] = { 5, 4, 8, 7, 1, 2, 6, 3 };

  bubbleSort(arr, size);

  for(int i = 0; i < size; ++i) {
    printf("%d\n", arr[i]);
  }

  return 0;

}

In this code, we wrote a swap method that uses a temporary variable to support the swap operation.

Bitwise XOR

Bitwise XOR is an operation that returns true only when the operation is done with a true and false values, otherwise, the operation results into a false value.

Note that this operation is done to each bit in the variable.

Let's look at a XOR's table:

Input	Input	Result
true	false	true
false	true	true
true	true	false
false	false	false

With that in mind, let's look at an example:

Input	0 0 0 1 1 0 1 0
Input	0 1 0 1 1 1 0 1
Result	0 1 0 0 0 1 1 1

Now, let's rewrite our swap function using XOR operations. In C, the XOR operator is the ^.

void swap(int* a, int* b) {

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

  return;

}

Let's suppose that we are calling this method by passing the values 0001(1) and 0010(2).

The first operation that happens is a = a ^ b

0 0 0 1
0 0 1 0
0 0 1 1

The second operation that happens is b = a ^ b

0 0 1 1
0 0 1 0
0 0 0 1

The third operation that happens is a = a ^ b

0 0 1 1
0 0 0 1
0 0 1 0

This article showed that with bitwise XOR, we can swap the values ​​of the variables without using a third variable to support the operation.