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).

Answer 2

My answer is quite straightforward. Here being n1 xor n2 xor .. xor nk = 0 means the pattern is "balanced" (i.e, XOR sum of the binary representation of the numbers are zero).

The player who cannot make any move will loss the game, right? So if you notice carefully you will find that the loser player cannot make any move because the all the piles' sizes are zero and which is also a "balanced" pattern (as, 0 XOR 0 XOR...XOR 0 = 0). So if you can make sure that the opponent always gets this balanced pattern than eventually s/he will get this last balanced pattern as well where all the piles' sizes are zero and the opponent will loss the game!

Now we can transform our problem a little bit. As we are sure to win if the opponent always gets the balanced pattern, now let's find out how to ensure that.

Let's have a look on this little example: say we have 3 piles and at some point you got the piles like this state:

1  0  1  0    (10)
0  1  1  0    (6)
1  0  0  1    (9)
--------------------------
0  1  0  1    (5)   (After taking XOR columnwise...that is "XOR sum")

Here we are getting the XOR sum = 5 (0101) and we want to pick such number of element(s) from a single pile such that it becomes 0 (0000) i.e, balanced when the opponent gets his/her turn after my removal.

Here I am mentioning an XOR operation: if "A" is a number therefore,

A XOR A = 0

So if we could XOR the result=5 (0101) with its itself than it would become 0 (i.e, 5 XOR 5=0). But we cannot directly change the result like this but we are allowed to do XOR operation with any of the operands (i.e, with 10,6 or 9) which has the same impact of doing XOR with the result. Here we will use this trick. So we will do XOR operation of 5 with 6 (0110) and we get:

5(0101) XOR 6(0110) = 0011(3)

Now after that, the XOR sum will be zero like this,

1  0  1  0    (10)
0  0  1  1    (6 XOR 5 = 3)
1  0  0  1    (9)
--------------------------
0  0  0  0    (0)   (Now the XOR sum is zero)

Here by doing this XOR operation two purposes are served:

(1) XOR sum becomes zero again which makes the pattern balanced and now we are ensuring that the opponent is getting the balanced state, and

(2) After XOR operation the value of that pile decreased (from 6 it becomes 3...so we can say like, we are removing 3 elements from second pile (as 6 - 3 = 3)...so here you have to ensure the thing that you are XORing with that pile number which decreases after making XOR operation (as you are only allowed to remove item and not to add any and it is guaranteed you will find such one).

Now once you have managed to provide the opponent a balanced state you are sure to win (if you play optimally..i.e, ensuring this criteria) as the opponent is getting the balanced state. So s/he will make it unbalanced again (i.e, XOR sum != 0) whenever removing elements (as it will change the binary pattern of the value of that pile's value). And getting this unbalanced pattern you will make it balanced again for the opponent by removing elements maintaining this criteria. So eventually your opponent at some point will get the all emptied piles as it is also a balanced pattern (as 0 XOR 0 XOR....XOR 0 = 0) and loss the game.

Here additionally I want to mention some facts:

(1) Here the opponent is getting the balanced pattern and it is impossible to make it balanced again for the opponent as it will require to change more than one row to compensate to the change in binary pattern he/she made while removal which is not allowed. So you are surely getting a unbalanced pattern to make it balanced again.

(2) It is always possible for you to make this unbalanced pattern a balanced pattern...follow the mentioned criteria while removal of elements.

And finally:

You are not bound to use XOR operation here. You can do it in some other ways like manually checking if the pattern is balanced or not. But XOR is used as luckily XOR has the same property which we want here and it makes the calculation easier. But it is not mandatory to use XOR here if you can manage to do it in some other way...just make sure your opponent is getting the balanced state.

But if you get this balanced state and your opponent plays optimally (that is the opposite scenario) than you will surely loss the game and it is impossible to prevent:(