IT-блоги • Understanding XOR-based-value Swapping

Table of contents

• Objectives
• Introduction
• Understanding XOR
• Proof of the 3 XOR operations
• Conclusion

Objectives

1. Understanding XOR operations
2. Understanding why the 3 special XOR operations swap two numbers in place

Introduction

Given two numbers x=5 and y=10, we can switch these two numbers in place by using a temporary variable as the C code below;

#include <stdio.h>

int main(void) {
    int x = 5;
    int y = 10;
    printf("Before reassignment\n");
    printf("x: %d\n", x);
    printf("y: %d\n", y);

    printf("-----------------------\n");

    // Assign y to a temporay variable
    int temp = y;
    y = x;
    x = temp;

    printf("After reassignment\n");
    printf("x: %d\n", x);
    printf("y: %d\n", y);

}

There is also another way to do this by using Exclusive OR (XOR). This does not need a temporary variable and will switch the values in place.
It involves 3 XOR operations.

#include <stdio.h>

int main(void) {
    int x = 5;
    int y = 10;

    printf("Before reassignment\n");
    printf("x: %d\n", x);
    printf("y: %d\n", y);

    printf("-----------------------\n");

    // XOR is represented by ^
    // The 3 XOR operations
    y = x ^ y;
    x = x ^ y;
    y = x ^ y;

    printf("After reassignment\n");
    printf("x: %d\n", x);
    printf("y: %d\n", y);
}

The above code changes the two variables without using a temporary variable. When you do those 3 XOR operations, the variables will switch places but why?
To understand that, let's first understand what Exclusive OR (XOR) is.

Understanding XOR

XOR is a logical operator that returns True only if one of its inputs is True. For example: Given two inputs if both input A and input B are True then the XOR of both will be False.
If both are False then the XOR will also be False. XOR will only be True if one of them is True and the other is False.
To use 0s and 1s to represent our inputs, we can say True is 1 and False is 0. Thus, an XOR operation between the two inputs will give us the table below;

XOR between binary numbers

This means if we XOR two binary numbers, A(1011) and B(0110), we are going to get 1101.

   A:    1 0 1 1
   B:    0 1 1 0
----------------
Result:  1 1 0 1

If we also XOR two binary numbers, A(1011) and B(1011), we are going to get 0000

   A:    1 0 1 1
   B:    1 0 1 1
----------------
Result:  0 0 0 0

We can see both binary numbers are the same and we know XOR outputs 0 if both inputs are the same, ergo A ^ A = 0.
We can also also establish that XOR between A and B where A=0 will output B.

   A:    0 0 0 0
   B:    0 1 1 0
----------------
Result:  0 1 1 0

This means 0 ^ B = B.

Given:

A ^ A = 0 and 
0 ^ B = B
We can say;
(A ^ A) ^ B = B
This is associative and can also be written as;
A ^ A ^ B = B

Proof of the 3 XOR operations

Let's go back to our 3 operations that change x and y in place;

y = x ^ y
x = x ^ y
y = x ^ y

Let's use the various rules we've established so far to see if we can prove that after these 3 operations x=y and y=x.
We have the first 2 operations;

y = x ^ y and 
x = x ^ y

We can replace y in the 2nd operation with its value in the first: x ^ y, ergo our second operation can be expanded to;

x = x ^ y
x = x ^ (x ^ y) 
x = x ^ x ^ y

We have already established that A ^ A ^ B = B thus,

x = x ^ x ^ y = y
x = y

So x is now y on the 2nd operation.

We can now represent our 3 operations as;

y = x ^ y
x = y
y = x ^ y

We can then proceed to expand our 3rd operation by replacing x whose current value is now y and y whose current value is x ^ y;

y = x ^ y
Replacing x with y and y with x ^ y;
y = y ^ (x ^ y) 
y = y ^ x ^ y 
y = y ^ y ^ x
y = x

After the 3 operations, we have x = y and y = x.

Conclusion

We've been able to prove why 3 special XOR operations lead to the swapping of two values without using a temporary variable.
Although this algorithm does not offer any significant improvement over swapping two values using a temporary variable, understanding it gives us a better understanding of bit operations and their properties.