In this article, we will begin with a brief introduction of what the XOR operation is, followed by its syntax in C++ and XOR applications such as memory-optimized doubly linked lists, swapping, XOR ciphers, Comparing two values, Gray codes and Partiy check.

We will be covering the following Applications of XOR operation in depth:

1. Making memory efficient Doubly Linked Lists aka XOR Linked Lists
2. Swapping using with XOR
3. Encryption with XOR: The XOR Cipher
4. Comparing two numbers using XOR
5. Conversion of binary values to gray code using XOR
6. Checking parity of a number using XOR

Let's begin with the basics of XOR operation followed by the above applications!

XOR for binary numbers

XOR is a bit-wise operator denoted by the ^ symbol. When two binary numbers are XOR'ed, the bits at the corresponding positions are manipulated as:

i.e the output is 1 if the bit values are different.

In C++, we can implement the XOR operation as follows-

#include<bits/stdc++.h>
using namespace std;
using bin = bitset<12>;

int main()
{
    bin x{ "000001011010" };
    bin y{ "111100111100" };
    bin z = x^y;
    cout<< z;
    return 0;
}

Output is: 111101100110.

Some important properties of XOR

• X ^ 0 = X i.e. when any value is XOR'ed with NULL or 0, the result is the same value.
• X ^ X = 0 i.e. when any value is XOR'ed with itself, 0 or NULL is the result.
• X ^ Y = Y ^ X i.e. XOR is commutative. The order of the values doesn't affect the result.

Making memory efficient Doubly Linked Lists aka XOR Linked Lists

We are already familiar with the concepts of linked lists and doubly linked lists. Doubly Linked lists are linear data structures with non-contiguous memory allocation, where elements are stored in nodes, connected to their preceding and succeeding elements via pointers prev and next respectively. We need to maintain two pointers for every element in the list, which takes up more space. However, the XOR operation can help in optimizing the memory required per node. This is implemented in XOR Linked Lists.

In XOR linked lists, each node maintains only one pointer prevxornext which contains the XOR'ed value of the pointers prev and next. So, each node looks like this:

struct node
{
    int data;
    node* prevxornext;
};

To calculate the XOR value of the two pointers, we will first need to typecast the pointers in intptr_t, then take the XOR, finally returning them again in pointer form. So, we have the following function defined-

node* ptrXOR(node* x, node* y) {
    return (node*)((intptr_t)(x) ^ (intptr_t)(y));
}

Now, we need a function to insert values into our linked list. We shall call it insertnode() which takes the head node and the int value data to be inserted as parameters. It creates a new node with the data, then attaches it at the head of the list. So, the current head node's prevxornode pointer has to be XOR'ed with the pointer value of the new node we created. When the updates are made, we assign the new node to the head. So, let's see the function-

void insertnode(node* &head, int data)
{
    // create new node
    node* newnode = new node();
    newnode->data = data;

    // The prevxornext field of the new node is ptrXOR of the current head and nullptr
    // since a new node is being inserted at the beginning
    newNode->prevxornext = ptrXOR(head, nullptr);
    // since, XOR with a nullptr yields the same value, we can directly assign the head value as well. 

    // update prevxornext value of the current head node if the linked list is not empty
    if (head)
    {
        // 'head->prevxornext' is XOR of null and address of the next node. So, it basically contains the next node's address. Here, we are skipping the ptrXOR with nullptr.
        
        head->prevxornext = ptrXOR(newNode, head->prevxornext);
    }

    // update the head pointer
    head = newNode;
}

We can add some values to our XOR linked list, now. So, in the main function of the program, we have:

int main()
{
    // input keys
    vector<int> keys = {1,2,3,4,5,6,7,8,9};

    node* head = nullptr;
    for (int i = keys.size() - 1; i >=0; i--) {
        insertnode(head, keys[i]);
    }
// more code will be added here for traversal
}

Since, we are adding elements to the head node, the first element inserted will be at the end of the list. Hence, we are inserting the items from the rear end of the vector.

Our XOR linked list is ready. Let's see how we can traverse through it. In the traverse function, we will need 3 pointers prev,curr and next. The head node is passed as a parameter in the function, and curr is first initialised with it. prev is a null pointer. While the curr pointer is not nullptr, we iterate through the list. After accessing the data, the pointers are updated to move to the next node. The next node is found by XOR of the node we previously visited prev and the prevxornext value of the current node curr. Now, to iterate, the current node becomes the previous and next becomes the current.

So, in code-

void traverse(node* head)
{
    node* curr = head;
    node* prev = nullptr;
    node *next;

    while (curr != nullptr)
    {
        cout << curr->data << " -> ";
        next = ptrXOR(prev, curr->prevxornext);
        
        prev = curr;
        curr = next;
    }
    cout << "End of list";
}

Now,this function can be called in the main function. So, our overall code looks like:

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int data;
    node* prevxornext;
};
node* ptrXOR(node* x, node* y) {
    return (node*)((intptr_t)(x) ^ (intptr_t)(y));
}
void traverse(node* head)
{
    node* curr = head;
    node* prev = nullptr;
    node *next;

    while (curr != nullptr)
    {
        cout << curr->data << " -> ";
        next = ptrXOR(prev, curr->prevxornext);
        
        prev = curr;
        curr = next;
    }

    cout << "nullptr";
}

void insertnode(node* &head, int data)
{
    node* newnode = new node();
    newnode->data = data;

    // The prevxornext field of the new node is ptrXOR of the current head and nullptr
    // since a new node is being inserted at the beginning
    newNode->prevxornext = ptrXOR(head, nullptr);
    // since, XOR with a nullptr yields the same value, we can directly assign the head value as well. 

    // update prevxornext value of the current head node if the linked list is not empty
    if (head)
    {
        // 'head->prevxornext' is XOR of null and address of the next node. So, it basically contains the next node's address. Here, we are skipping the ptrXOR with nullptr.
        
        head->prevxornext = ptrXOR(newNode, head->prevxornext);
    }

    // update the head pointer
    head = newNode;
}

int main()
{
    // input keys
    vector<int> keys = {1,2,3,4,5,6,7,8,9};
    node* head = nullptr;
    for (int i = keys.size() - 1; i >=0; i--) {
        insertnode(head, keys[i]);
    }
    traverse(head);
    return 0;
}

Thus, we have our memory efficient implementation of doubly linked lists using the XOR operator aka XOR linked lists.

Swapping using with XOR

Our next application of the XOR operator is swapping of two values! This works as follows:

#include<bits/stdc++.h>
using namespace std;
using bin = bitset<12>;

int main()
{
    bin x{ "000001011010" };
    bin y{ "111100111100" };
    
    //Swapping procedure:
    x=x^y; //1
    y=x^y; //2
    x=x^y; //3
    
    cout<< x;
    return 0;
}

Let's see the details of this logic using the properties we learned earlier.

In step 1, we have x=x^y. Let us call this new value X to differentiate it. 
In step 2, we have y=X^y. So, substituting from step 1, we have y=(x^y)^y => y=x. Let's call this new value Y.
In step 3, we have 
    x=X^Y
  =>x=(x^y)^x 
  =>x=y.
Hence, the values of x and y have been swapped.

The swapping can also be done in a swap() function which takes the two values as parameters and implements the same logic. The output of the above program will be 111100111100.

Encryption with XOR: The XOR Cipher

Encryption and data security which are very important aspects of data sharing and working on the Internet in general can also find use of the XOR operator. We're going to now understand how a basic XOR cipher works.

By now, we are already familiar with the following property of the XOR operator: (X ^ Y) ^ Y= X i.e. if we XOR some value with the same element twice, the same value is returned. This property forms the basis of the XOR cipher.

We select a random key. Then, every character of our message is XOR'ed with a character from the key. This modified string can now be shared with the person you wish to communicate with. At the receiver's end, they can run our XOR function again, thus nullifying the effects of the key and gaining back the raw message. C++ code:

#include<bits/stdc++.h>
using namespace std;

void XORCipher(string &Message)
{
	// Define XOR key
	string xorKey = "QPhhd123xi";

	int len = Message.size();
    int keylen=xorKey.size();

	for (int i = 0; i < len; i++)
	{
		Message[i] = Message[i] ^ xorKey[i%keylen];
		cout<<Message[i];
	}
}

int main()
{
	string sample;
    cout<<"input: "<<endl;
    getline(cin,sample);
	// Encrypt the string
	cout<<"On Encryption: ";
	XORCipher(sample);
	cout<<endl;

	// Decrypt the string
	cout<<"On Decryption: ";
	XORCipher(sample);

	return 0;
}

Output:

input: 
Applications of XOR
On Encryption: RSG◄♠?#H☻◄j|*ing: ► ↑♦
On Decryption: Applications of XOR

In this way, a simple XOR Cipher can be implemented. XOR is usually a very common element in other complex encryption techniques which are used in various applications across networks.

Comparing two numbers using XOR

Another really simple application of XOR is comparing two values. We are already aware that X ^ X = 0. This can easily be used to find out if two values are equal. If they are unequal, we can compare them and find out the smaller/greater number by making use of right shift operator >>, AND operator &, OR operator | and the XOR opeartor ^. The details of this application has already been discussed in detail here. In brief, we XOR the numbers and find the most significant bit(MSB) that differs in the two numbers. Then, we check both the numbers to check which number has the bit set in the MSB position. If it is present, the number is greater; otherwise the number is smaller in value.

Conversion of binary values to gray code using XOR

Gray code has the feature that two consecutive numbers differ by only one bit. As a result, Gray code may cycle between many states with low effort and is utilized in K-maps, error correction, communication, and other applications. XOR is imperative for conversion of binary values to Gray code. Let's see how the conversion works.

Every digit in the gray code is the XOR of the corresponding bit in the binary number and the bit next to it in the right. Example:

 0  0  1  0  //Binary representation 2
 | \| \| \|  //The bits have been XOR'ed to obtain the result bit
 0  0  1  1  //2 in Gray code

Let's write this a little differently.

 0  0  1  0  //Binary representation 2
    0  0  1//The next right bit with which the bit is XOR'ed
 0  0  1  1  //2 in Gray code

Observe the bits in the second line. They form the value we will obtain if the number given is right-shifted once. So, essentially, Gray code can be obtained by XOR'ing a number with the value obtained by shifting all its bits to the right by 1 position. Code:

#include<iostream>
using namespace std;
int togray(int n)
{
    return (n^(n>>1));
}

int main() {
int b=2;
cout<<togray(b);
}

The output 3 is returned.

Checking parity of a number using XOR

Parity of a number refers to the number of set bits that are present in the binary representation of the number. Essentially, if the number of 1's in a binary number is odd, then the number is said to have odd parity. If the number of 1's in a binary number is even, then it's said to have even parity. Ex.

155=10011011 in binary form. Since the number of 1's is 5, which is odd, the parity is odd. 

156=10011100 in binary form. Since the number of 1's is 4, which is even, the parity is even.

Let us see the code for this in c++:

#include <bits/stdc++.h>
using namespace std;

bool Parity(int x)
{
	int y = x ^ (x >> 1);
	y = y ^ (y >> 2);
    y = y ^ (y >> 4);
    y = y ^ (y >> 8);
    y = y ^ (y >> 16);

	// Rightmost bit of y holds the parity value
	// if (y&1) is 1 then parity is odd else even
	if (y & 1)
            return 1;
	else 
            return 0;
}

// Driver code
int main()
{
	if(findParity(155)==0){cout<<"Even Parity\n";}
	else cout<<"Odd Parity\n";

	if(findParity(156)==0){cout<<"Even Parity\n";}
	else cout<<"Odd Parity\n";
	return 0;
}

The output of this program is

Odd Parity
Even Parity

Let's see how this code works in finding the parity of a number.

Step 1:

int y = x ^ (x >> 1);

Suppose we are working on 155 i.e. 10011011.
   x:    1  0  0  1  1  0  1  1
x>>1:    0  1  0  0  1  1  0  1 
   y:    1  1  0  1  0  1  1  0

We know that for odd number of 1's, XOR returns 1, whereas for even numbers of 1's, XOR returns 0.

So, when we are XOR'ing x with (x>>1), we are finding the parity of every pair of consecutive bits.

So, the LSB of y is 0 as the parity of the last two bits of x is 1.
Let us index the bits as follows: 7 6 5 4 3 2 1 0.

So now, Y contains the parity of the bits as follows

y:     1   1   0   1   0   1   1   0
      8-7 7,6 6,5 5,4 4,3 3,2 2,1 1,0

Here, the bits in Y represent the parity of the digits of x mentioned below the bits.

Step 2:

y = y ^ (y >> 2);
Now, y=1  1  0  1  0  1  1  0. So, we have

      (8,7|7,6|6,5|5,4|4,3|3,2|2,1|1,0)
   y:   1   1   0   1   0   1   1   0
y>>2:   0   0   1   1   0   1   0   1
Result: 1   1   1   0   0   0   1   1
       10-7 9-6 8-5 7-4 6-3 5-2 4-1 3-0          

In this stage, the result bits represent the parity of 4 consecutive bits, because we did the double shift.

Step 3:

y = y ^ (y >> 4);
At this point, y=11100011. So, we have
     y: 1   1   1   0   0   0   1   1
  y>>4: 0   0   0   0   1   1   1   0
result: 1   1   1   0   1   1   0   1
       ---------------10-3 9-2 8-1 7-0
      and so on.

So, we see that the least significant bit of the result now contains the parity of all 8 bits of the number.

Step 4:

y = y ^ (y >> 8);
y = y ^ (y >> 16);

These steps work the same way as the earlier ones.

Since our most significant bit is at the 7th index, these operations won't make any difference to our last bit overall.

However since int has 16 bits, so we need these steps for greater numbers.

Now that all these steps have been done, we come to our if condition:

if (y & 1)
   return 1;
else 
   return 0;

Since our parity is found at the least significant bit, so we AND it with 1 to check its value.

If the value is 1, the parity is odd. If the value is 0, the parity is even.

And so we have reached the end of this article at OpenGenus where we have covered XOR linked lists, XOR Ciphers, Comparisons, Gray code conversion and parity checking. Keep learning!