That XOR Trick (2020)

Summary

There are a whole bunch of popular interview questions that can be solved in one of two ways: Either using common data structures and algorithms in a sensible manner, or by using some properties of XOR in a seemingly hard to understand way. While it seems unreasonable to expect the XOR solutions in interviews, it is quite fun to figure out how they work. As it turns out, they are all based on the same fundamental trick, which we will derive in a bottom-up way in this post. Afterwards we will look at a bunch of applications of that XOR trick ™, such as solving this popular interview question: You are given an array of n - 1 integers which are in the range between 1 and n. All numbers appear exactly once, except one number, which is missing. Find this missing number. Of course, there are a number of straightforward ways to solve this problem, but there is also a perhaps surprising one using XOR. XOR XOR is a logical operator that works on bits. Let’s denote it by ^. If the two bits it takes as input are the same, the result is 0, otherwise it is 1. This implements an exclusive or operation, i.e. exactly one argument has to be 1 for the final result to be 1. We can show this using a truth table: x y x ^ y 0 0 0 0 1 1 1 0 1 1 1 0 Most programming languages implement ^ as a bitwise operator, meaning XOR is individually applied to each bit in a string of bits (e.g. a byte). For example: since 0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0 Because of this, we can apply XOR to anything, not just booleans. Deducing Some Useful Properties We can derive a bunch of properties from the previous definition. Let’s go through them one by one, and then compose them to solve the interview questions previously mentioned. XOR and 0: x ^ 0 = x If one of the two arguments to XOR is 0, then the remaining argument is the result. This directly follows from the truth table by checking the rows where y = 0, namely the first and third row. x y x ^ y 0 0 0 0 1 1 1 0 1 1 1 0 XOR on the same argument: x...