I am conducting research in Combinatorial Game Theory (CGT). Although I have done a considerable amount of reading, I do not completely understand why the bit-xor function also known as the nim-sum appears in Nim. To be more clear, I will explain my current level of understanding. I completely grasp the mechanics of the proofs of both Bouton's Theorem and the Sprague-Grundy Theorem. However, I am looking for an intuitive explanation. 


I understand that the binary representations arise as a natural extension of the parity-mirroring arguments in two-heap Nim. However, I would like to know what particular properties of the bit-xor function allow it to work. For example, the bitwise-and would not work for Nim in the same way the bit-xor works; is there some functional equation that the bit-xor fulfills that makes it so ubiquitous?


Note that I am not asking for the motivation for the Sprague Grundy Theorem as in [Motivation and Intuition for Sprague-Grundy Theorem](https://mathoverflow.net/questions/126083/motivation-and-intuition-for-sprague-grundy-theorem?rq=1). I am asking about the xor function in particular.


Thank you in advance.


By the way, this is my first question, so if anything is wrong, please critique me.


I feel that it it would be helpful to mention further context. I was reading [A paper of Fraenkel and Kontorovich](http://%3Chttp://www.wisdom.weizmann.ac.il/~fraenkel/Papers/sierpinski.pdf%3E) which used the bitwise and to explore Nim.



Why does the bitxor function appear in Nim?
There's something of a good explanation. You accept the Sprague-Grundy theorem, which implies in particular that Nim positions must form a group - any two Nim positions are equivalent to one Nim position, and each Nim position plus itself gets you back to the identity.


OK, but which group? I guess you also know it's a 2-torsion group, so which 2-torsion group?


Well the answer is really simple. Because of how Sprague-Grundy works, each element is the first thing it can possibly be.


So 0 is the identity, because the group has to have one of those. 1 can't be the identity, so it's some other element. 1 is 2-torsion, so now we have a complete group. The next element, 2 must not be in that group, so it's a new element. No we don't have a complete group - we're missing 1+2. So that goes to 3. Now we have a complete group again, so 4 must be a new element. To generate a group from those, we need 4+1, 4+2, 4+3. Those again just go to the first element - 4+1=5, 4+2=6, 4+3=7 and so on.


So choosing the first possible element gets you the xor operation. Conway has generalized this with multiplicative structure, which in fact exists on origi nal numbers, that he calls the "first field" (formerly "nim field") - there each additively new element gets expressed in the simplest way as a product of previous elements, unless the existing numbers already form a complete ring, in which case it forms a new element satisfying the simplest possible polynomial equation, which for finite numbers is always quadratic.


