Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.


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:

Rendered by QuickLaTeX.com

3.1. Hardware Implementation

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

XOR SCEHMATICS

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:

Two Way Encryption Using XOR

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:

Rendered by QuickLaTeX.com

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:

Rendered by QuickLaTeX.com

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.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!