Why does the XOR operator work?

Question

In many coding problems, I see applying XOR to the set of values gives the result.

For example : In the game of nim

Let n1, n2, … nk, be the sizes of the piles. It is a losing position for the player whose turn it is if and only if n1 xor n2 xor .. xor nk = 0.

Can somebody explain me why this works? Please give me an idea, so that in the future I'll be able to solve these type of problems.

Answer 1

In nim (in fact, in any finite combinatorial game), the following facts are true:

(1) From a losing position, all moves lead to a winning position.

(2) From a winning position, there is at least one move to a losing position.

(The terms "winning position" and "losing position" are to be interpreted from the point of view of the person whose turn it is to move from the position.)

It is also true that for any finite combinatorial game, there is only one way to decompose the (finite!) set of positions into two classes which satisfy (1) and (2) above.

So, the reason the XOR rule works is that satisfies these conditions: (I write $\oplus$ for XOR.)

(1') From a position where $a_1 \oplus a_2 \oplus \ldots \oplus a_k = 0$, all moves lead to a position where $a_1 \oplus a_2 \oplus \ldots \oplus a_k \ne 0$.

(2') From a position where $a_1 \oplus a_2 \oplus \ldots \oplus a_k \ne 0$, there is at least one move to a position where $a_1 \oplus a_2 \oplus \ldots \oplus a_k = 0$.

To prove (1'), notice that any move can only change one of the $a_i$. If you change a single bit in an XOR of bits, you will change the final result. So if you start with an XOR total of 0, you must end up with an XOR total of $\ne 0$.

To prove (2'), let $a = a_1 \oplus a_2 \oplus \ldots \oplus a_k \ne 0$. In $a$, there is a 1 bit in somewhere. Take the leftmost 1 bit in the total $a$, and look for a 1 bit in that column in one of the $a_i$'s. Say $a_1$ has a 1 bit in that column. Then flip all the bits in $a_1$ corresponding to the 1 bits in $a$. This will make the new XOR total 0, and it is a legal nim move because the highest order bit changed in $a_1$ was changed from 1 to 0, hence the value of $a_1$ decreased as required by the rules of nim. An example with 5 piles:

  *
1 1 0 0 1
0 1 1 1 1
1 0 0 1 1
0 0 0 1 1
0 1 1 0 1
---------
0 1 0 1 1 (the bitwise XOR)

The leftmost 1 bit is in the position indicated by *. The first pile (11001 binary) has a 1 in the * position. We flip all bits in which there is a 1 in the total. So the new first pile is (10010 binary). You can check that this move makes the new XOR total equal to 0, and also we decreased the size of the pile (from 25 to 18).