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:
0011 ^ 0101 = 0110
... continue reading