The XOR Operation | Baeldung on Computer Science

1. Introduction

In this tutorial, we’ll study the exclusive OR operation, which is also called XOR.

XOR is widely used in many fields such as cryptography, genetic algorithms, and digital signal processing.

2. Bit Operations

XOR is a bit operation. Bit operations are mathematical functions we perform on individual bits of input numbers. They are very fast and robust because they use fewer CPU cycles and are carried out in only one CPU register. In contrast, most arithmetic instructions use more than one register, so they spend more time moving the arguments and intermediate results between the registers.

There are two types of bit operations in computer programming: unary and binary.

Unary operations take only one input. NOT is one of the most popular unary operators. It negates the input bit, so if $x=1$ , then $\mathrm{NOT}(x) = 0$ , and vice versa.

Binary operations take two inputs. OR, AND and XOR are some of the most popular binary bit operations. For instance, AND gives as output 1 if both the operands have their bit set as 1, else it gives as output 0. So, if $x_{1}=1$ and $x_{2}=0$ , then $\mathrm{AND}(x_{1}, x_{2}) = 0$ .

3. XOR Operation

XOR accepts two operands and compares their values. If they’re the same, it evaluates to 0 (or False). Otherwise, if both operands have different values, it outputs 1 (or True). Here’s its truth table:

3.1. Hardware Implementation

The following figure shows the internal implementation of the XOR operation at the hardware level:

As we see, hardware uses 5 gates (2 ANDs, 2 NOTs, and one OR) to implement XOR $(x_1, x_2)$ , where $x_1$ and $x_2$ are our input bits.

Firstly, we feed $x_{2}$ to one NOT gate. Its output along with $x_{1}$ then flows to the first AND gate. Similarly, we feed $x_{1}$ to the other NOT gate and forward its output along with $x_{2}$ to the second AND gate. The outputs of both AND gates are then fed to the OR gate.

We get the result of the XOR operation for the inputs $x_{1}$ and $x_{2}$ as the output of the OR gate.

Why do we implement XOR like this? If we look at its truth table, we’ll see that this implementation enumerates the cases where XOR is True: $x_1=1, x_2=0$ and $x_1=0, x_2=1$ .

4. XOR in Cryptography

In this section, we explore the use of XOR in cryptography.

4.1. XOR in Encryption Schemes

We can use XOR in two-way encryption algorithms that are executed at both the sender’s and the receiver’s ends. The sender and the receiver both have the same cipher key. The sender uses this key to encrypt the message and send it to the receiver. The receiver gets this encoded message and decrypts it with the same to get the original message back.

The following diagram depicts this flow:

4.2. Example

Let’s suppose our cipher key $C$ is 11001001 and our message $P$ is 11100101. We apply XOR to $C$ and $P$ to get an encoded message $ENC$ :

$\begin{matrix} C & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ P & 1 & 1 & 1 & 0& 0 & 1 & 0 & 1 \\ \hline ENC & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \end{matrix}$

On the receiver side, we apply XOR to $C$ and $ENC$ to get our original message $P$ back:

$\begin{matrix} ENC & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ C & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ \hline P & 1 & 1 & 1 & 0& 0 & 1 & 0 & 1 \end{matrix}$

4.3. Advantages of XOR in Cryptography

XOR offers two big advantages here. First, XOR doesn’t leak information about the original message. Why? Well, if $\mathrm{XOR}(x_{1}, x_{2})=1$ , we cannot be sure about the exact values of $x_{1}$ and $x_{2}$ . They can be either (1, 0) or (0, 1). The same goes if the result is 0: the arguments can be either (1, 1) or (0, 0).

In contrast, AND and OR leak information. If $\mathrm{AND}(x_1, x_2)=1$ , we know that $x_1=x_2=1$ . If $\mathrm{OR}(x_1, x_2)=0$ , we can be sure that $x_1 = x_2 = 0$ .

Secondly, XOR is an involutory function. Formally, a function $f$ is involutory if $f(f(x)) = x$ whenever $f(x)$ is defined. Thus, if we apply XOR twice, we’ll get the original plain text back. In other words:

$\mathrm{XOR}(C, \mathrm{XOR}(C, P)) = P$

The inner XOR acts as the encryption operation whereas the outer XOR decrypts the message.

5. XOR Use Cases

There are many things we can use XOR for. For instance, to generate parity bits for error checking and fault tolerance, or to swap two values without auxiliary storage.

5.1. Swapping Without Using XOR

Traditionally, we swap the values of two variables using temporary storage as shown in the following pseudocode:

algorithm SwapWithoutXOR(a, b):
    // INPUT
    //     a, b = two variables to swap
    // OUTPUT
    //     a and b swap their values

    tmp <- a
    a <- b
    b <- tmp

This way, we need additional storage for the temporary variable temp.

5.2. Swapping Using XOR

Now, let’s use the XOR operation to swap two values. As shown in the peudocode, we don’t use any additional storage:

algorithm SwapUsingXOR(a, b):
    // INPUT
    //     a, b = two variables to swap
    // OUTPUT
    //     a and b swap their values
    
    a <- a XOR b
    b <- b XOR a
    a <- a XOR b

Does this work? Let’s check.

Let’s say that, initially, $a=6$ and $b=10$ . In the binary representation, $a=0110$ and $b=1010$ .

Now, the first XOR updates the value of $a$ :

$\begin{matrix} a &0 & 1 & 1 & 0 \\ b & 1 & 0 & 1 & 0 \\ \hline a & 1 & 1 & 0 & 0 \end{matrix}$

Then, by applying XOR to $b$ and the new value of $a$ , we recover the old $a$ and assign the result to $b$ :

$\begin{matrix} b & 1 & 0 & 1 & 0 \\ a &1 & 1 & 0 & 0 \\ \hline b & 0 & 1 & 1 &0 \end{matrix}$

Finally, using the updated value of $b$ from the above step, the third XOR recovers the initial value of $b$ , so we assign it to $a$ :

$\begin{matrix} a &1 & 1 & 0 & 0 \\ b & 0 & 1 & 1 & 0 \\ \hline a & 1 & 0 & 1 & 0 \end{matrix}$

In the decimal representation, we get $a=10$ and $b=6$ . As we see, the values have been swapped, which is what we wanted to achieve.

6. Conclusion

In this article, we studied the XOR operation in computer programming. XOR is used in many encryption algorithms because it doesn’t leak information and can recover the original message after encryption. Further, XOR is faster than most arithmetic operations as it runs fewer instructions and mostly uses a single CPU register for execution.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex