This is a beginner-friendly introduction to the concept of the Exclusive OR, also known as XOR. It is denoted in Maths by the ⊕ symbol, and in Python by the ^ symbol.

I ran into it while trying to solve problem 136 on LeetCode. My solution used brute force and was very inefficient, so I checked online and saw the weird xor ^= num statement coming up without explanations. I then checked the Solutions tab on LeetCode and ran into this explanation from Satyam Sinha, which prompted me to do some further research on the Exclusive OR operator.

Here's my spin on what I learnt from this brief exploratory journey.

What is "Exclusive OR"?

Exclusive OR does exactly what it says on the tin. It is an operation that exclusively accepts one entity or the other in a statement, never accepting two copies of the same entity. It is a binary "or" operation on bits of memory (hence, a bitwise operation), and has a Boolean value. What this means is that it checks for the presence of 1 or 0 when comparing two binary numbers, but never 1 twice nor 0 twice. It then returns true (1 in binary) if there is an "exclusive or" relationship between the two binary numbers, or returns false (0 in binary) if both binary numbers are 0 or both binary numbers are 1. Note that XOR is a Boolean operator: it gives you True or False, just like "OR" & "AND" operators.

Use Cases

Comparing Boolean Values

To further illustrate this concept, there are cases where this operation is simple and straightforward, such as when comparing two Boolean values.

When checking if two Boolean values have an exclusive OR relationship, we are simply checking for instances where there is only one True and one False. So, if our two Boolean values in the input are a = True and b = False, then a ^ b = True. If a = False and b = True, then we'll have a ^ b = True and b ^ a = True. Note that Boolean operations don't care about which value is put first or second. They just check the relationship. In the same vein, a = True and b = True will lead to a ^ b = False. If a = False and b = False, then a ^ b = False. As a reminder, a ^ b means "a XOR b".

LeetCode's Single Number Problem

In a more complex example, XOR can be used to find the single integer in an array in which all other numbers have duplicates. Let's put a solution to LeetCode's Single Number problem on VSCode to see how it works:

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # Exclusive OR
        temp = 0
        for num in nums:
            print(f"{temp} ^ {num} = {temp ^ num}")
            temp ^= num
        return temp

nums = [3,1,5,3,5,6,6]
ob1 = Solution()
print(ob1.singleNumber(nums))

The print statement isn't part of the solution we'll put on the LeetCode editor, but it's helpful to see exactly how XOR works to find the single number out of the list of doubles. This is what got printed in the terminal:

➜  LeetCode python3 single_num.py
0 ^ 3 = 3
3 ^ 1 = 2
2 ^ 5 = 7
7 ^ 3 = 4
4 ^ 5 = 1
1 ^ 6 = 7
7 ^ 6 = 1
1

So, what's happening here? Let's run through some of the lines printed in the terminal.

We initialized the temporary temp variable to 0, as 0 ^ [any number] will always give that other number. This will be clearer in the next step. To explain what's happening behind the scenes in the XOR statements printed out, let's convert both numbers in each statement to binary, and work through them - bit by bit - on a spread-out table. Each unit in a binary column (1, 2, 4, 8, etc) is stored in one bit of memory. XOR works with these bits, comparing two values to see if there is only one true and one false (XOR = True), or if we have the same value in both bits (XOR = False). A reminder: in Boolean, True is 1 and False is 0. This way, we can convert any two decimal integers into binary and compare their binary values, then convert the result back to base 10. The '8' column is here because there is a possibility of 8 or 9 as a decimal integer, so the '8' bit might be needed when converted to binary. The '8' column will be 0 in all our examples because we didn't put 8 or 9 in the nums list/array.

Int | 8 | 4 | 2 | 1

first line: 0 ^ 3 = 3
 0    0   0   0   0
 3    0   0   1   1
Comparing each bit always gives the value other than 0, explaining why 0 was used to initialize temp (it's harmless):
 3    0   0   1   1

second line: 3 ^ 1 = 2
 3    0   0   1   1
 1    0   0   0   1
Note that we have 1 and 1 in the "1" binary column, so XOR evaluates to False (0) for that line:
 2    0   0   1   0

third line: 2 ^ 5 = 7
 2    0   0   1   0
 5    0   1   0   1
Now, XOR gives true (1) for the three columns, adding up to 7:
 7    0   1   1   1

Note that none of this makes sense in decimal/base-10 format. It's not meant to, as it is a bitwise operation and only happens on each bit in binary. It's not an addition or subtraction; it's a comparison.

Back to LeetCode 136. How does this help us find the only single number in an array/list of doubles? Well, a little abstraction is needed here, and then it makes sense. Every duplicated number will run into itself eventually. This is what the temp variable does for us, as we keep assigning the new XOR decimal result to it. This makes it a running comparison that iterates through the entire list of numbers. It's like saying 3 ^ 1 ^ 5 ^ 3 ^ 5 ^ 6 ^ 6, which will give the only number that is True once and False once, which is the number 1. The binary form of the duplicated numbers will be True once and then True a second time, cancelling each other out in the iteration.

This part was the hardest for me to wrap my head around, but doing it myself is what made it make sense. Please try it out and think it through.

See Satyam's LeetCode solution for other ways of tackling this problem, including my initial brute force approach that only beat 5% of Python users for speed. More uses of the XOR operator can be found in Rahul's Scaler article.

Conclusion

Thanks for reading my first tech article! 💜

There's a lot more to follow, here in Austin's Space. Please share this article with fellow code enthusiasts, especially those interested in data structures and algorithms.

Follow me on Hashnode, GitHub and Twitter for more insights from my tech journey.

✨ Cheers to making more magic! ✨

Credits

• Satyam's LeetCode Solution

• Rahul's XOR Tutorial on Scaler

• Didi's Technical Writing lectures at AltSchool