Extending the usefulness of xor for identifying items not in a sequence.

Question

Given the sequence [0 .. 255]

If a single value is removed, the xor of the remaining values produces that missing value.

However, if two values are removed, This no longer works.

A. Why does this happen for the single-value case?

B. Can this be extended to quickly find one of N missing?

I came across this question while working on a application that uses a bit field to give every value a unique bit to flip. I was curious if a more optimal/efficient solution existed to find gaps. My observation was based on generating full sequence with a single gap.

Let g be the sequence [0..255] with a single missing value q

Fold(x xor y, g) = q

Let h be the g with another missing value r

Fold(x xor y, t) = distance between q and r

So if r or q is 0 it does result in a correct answer.

Distance here is in a modular 256 sense.

I found it interesting that the single missing value seems to just drop out. But for two values all I get is the delta.

So a very efficient solution exists for a single missing value. No bit field or searching required. But when two or more values are missing finding one of them using this method no longer works.

Answer 1

In order, the bit patterns you are XORing are as shown in the following table:

$$ \begin{array}{r|c} 0 & 00000000\\ 1 & 00000001\\ 2 & 00000010\\ 3 & 00000011\\ 4 & 00000100\\ 5 & 00000100\\ \vdots &\vdots\\ 252 & 11111100\\ 253 & 11111101\\ 254 & 11111110\\ 255 & 11111111 \end{array} $$

In each column of bits there are $128$ $0$s and $128$ $1$s. Since XOR is commutative, writing $\frown$ for XOR, the XOR of all the bits in any one of the columns is $$ \underbrace{0 \frown 0 \frown \dots \frown 0}_{\text{$128$ $0$s}} \frown \underbrace{1 \frown 1 \frown \dots \frown 1}_{\text{$128$ $1$s}} = 0 \frown 0 = 0 \tag*{(*)} $$ because as is easy to prove by induction, the XOR of any number of $0$s is $0$ while the XOR of an even number of $1$s is $0$. Also, the XOR of an odd number of $1$s is $1$. So, if you remove one of the $0$s or $1$s from the left-hand side of the equation (*), the XOR will be the same as the bit you removed. That's why your method A works: the XOR of the rows of bits in the table after removal of one row will be equal to the row you removed.

In equation (*) if you remove a $0$ and a $1$ you get $1$, while if you remove two $0$s or two $1$s you get $0$, i.e., the result is the XOR of the bits you removed. So, if you remove between $2$ and $254$ of the rows in the table, all you can recover is the XOR of the rows you have removed. (The same is true if you remove $255$ of the $256$ rows, but, in that case, it is easy to find out what has been removed: it's just all the rows other than the one you are left with.) This is why your method B doesn't let you find out which rows have been removed. Taking the XOR of the remaining 254 rows after two have been removed doesn't give enough information to determine what rows were removed.