Originally posted on medium.

Leveraging the powerful bitwise operator

How to swap two variables in place?

No matter which programming language you are using, the answer is always the XOR trick:

a = 5
b = 7

a = a ^ b
b = a ^ b
a = a ^ b

print(a,b)
# 7 5

If you are a Python developer, you may think that the following way is also in place:

a,b = b,a

In fact, based on the explanation from the official document of Python, this swapping is neither XOR-based nor in-place. It creates a temporary tuple to store the values of a and b before reassigning them.

In most cases, the difference in performance between the XOR-based in-place swapping and the tuple-based swapping in Python is negligible.

However, XOR-based swapping can be useful in some special scenarios. For example, if you have an embedded system with limited memory and need to swap two large buffers and there isn’t room to create a third temporary buffer, the XOR technique makes it possible to do the swap. (Thanks

 for pointing out this and providing the use case.)

The XOR operation may seem intimidating for beginners. But applying it properly can make your programs neater, faster, and better.

This article will help you have a solid understanding of the XOR operator and introduce 5 commonly-used XOR tricks in the programming world.

Background Knowledge: An Overview of the XOR Operator

The XOR, which stands for “exclusive OR”, is a logical operation that is widely used in programming and digital circuit design.

The truth table of XOR operations

The XOR operation takes two inputs and returns a result based on the following truth table:

As the above table shows, the XOR operation returns a 1 if and only if one of the inputs is 1. If both inputs are the same (both 0 or both 1), the XOR operation returns 0.

Key properties of XOR operations

Based on the truth table of XOR, it’s easy to summarise that XOR operations have the following properties:

1. Commutative:

a^b == b^a

2. Associative:

a^(b^c) == (a^b)^c == (a^c)^b.

3. Any number XOR’ed with itself evaluates to 0.

a^a==0

4. Any number XOR’ed with 0 remains unchanged.

a^0 == a

Now, there are some awesome usages of XOR that leverage its properties skillfully.

1. Data Backup with XOR

RAID, which stands for “redundant array of inexpensive disks” is a commonly-used technique for protecting your data. There are different RAID levels to set how much storage will be used for backup.

Under the hood, it’s just based on XOR operations.

For example, you have two files x and y. Of course, the safest way to backup your data is saving two copies for x and y respectively. However, you may not have enough storage space for saving these two copies.

Here comes the XOR trick.

You can save a file z that is equal to x^y.

If you lost x or y, you can always use another one to do the XOR operation with z and get the lost one.

For instance, if we lost y, since z=x^y, so we can get y through x^z=x^x^y=y.

Of course, we cannot restore anything if we lost x and y at the same time. But it’s a lower probability event. The trade-off between storage costs and data protection is the philosophy of RAID.

2. XOR Cipher

The XOR cipher is a classic algorithm in cryptography. Its idea is pretty simple:

Do the XOR operation between plaintext and a key to produce the ciphertext.

text ^ key = cipherText

Do the XOR operation between the ciphertext and the key again to get the original plaintext:

cipherText ^ key = text

Of course, this method itself is too simple, so it’s commonly used as a component in more complex ciphers.

3. Detect Unexpected Data

Data cleaning is an essential skill for data scientists. In some cases, the XOR operations can help you detect unexpected data conveniently.

For instance, there is a list of data, and all its items except one appear twice. What is the fastest way to detect that item?

Without a doubt, the answer is to use the XOR operation.

If we have a list [a,a,d,b,c,b,c], we can just do XOR operations to them all, and the left one in the result is the item that only appears once:

a^a^d^b^c^b^c = 0^d = d

4. Xorshift: An XOR-Based Algorithm for Random Number Generators

The Xorshift algorithm is a classic pseudorandom number generator invented by George Marsaglia.

As its name implies, this generator is based on XOR operations. Due to space limitations, this article will not go into the detailed implementation of this algorithm. Since the original paper describes it perfectly.

5. Swap Two Variables in Place

As mentioned in the beginning, using XOR is a way to swap two variables in place. Let’s zoom in on the details of it.

Here we have two variables a and b.

a = 5
b = 7

And then we need three XOR operations to swap them:

a = a ^ b
b = a ^ b
a = a ^ b

What happened after each XOR operation?

After the first a=a^b, a is 5^7 and b is 7.

After the b=a^b, a is 5^7 and b is 5^7^7.

After the final a=a^b, a is 5^7^5^7^7 and b is 5^7^7.

Based on the XOR properties, we can easily get the 5^7^5^7^7 is 7 and the 5^7^7 is 5.

Therefore, a is 7 and b is 5 now. 👏

Conclusion

XOR (exclusive OR) is a powerful bitwise operation that can be used in a wide variety of scenarios. Some of the most useful XOR tricks include data backup, XOR cipher, unexpected data detection, random numbers generator, and swapping two variables in place.

By understanding XOR properties and some common XOR tricks, making your code more elegant is not a dream. 😎

Source: medium