Why does the bitxor function appear in Nim? 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. 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 which used the bitwise and to explore Nim.
 A: Here's my understanding of the Nimbers and of your question.  Actually, you'll see that I do need to beg the question somewhere, but since you do know a proof of the bitxor rule, perhaps that's allowed --- then my answer can be understood as a proof that your proof implies your proof is natural.  (Said that way it sounds like an application of Lob's theorem, or perhaps a converse....)
By "Nimbers" I mean Nim games with Conway's game addition (put two games next two each other; on your turn, you choose one of the two boards to play on) modulo the second-player-win Games.  By definition, a "game" is one where you lose when you cannot make a turn.  The Nimbers are the classes of single-column Nim games.
The zeroth observation is that addition (henceforth "$+$") is commutative, and that for any game $g$, the game $-g$ in which the roles are reversed is its inverse.
The first observation, then, is that impartial games, and multi-column Nim games in particular, are 2-torsion: for any Nim game $g$, we have $g + g = 0$.  Thus the group generated by the Nimbers is a vector space over $\mathbb F_2$.
The next ingredient I don't really have an a priori reason for, which is that the sum of any two Nimbers is a Nimber. Actually, proving this is probably just about the same as finding the bitxor formula, so perhaps my whole story is question-begging.  But let's assume that this second ingredient is just an "observation".
The third observation is the following.  Let $G_k$ denote the group generated by the Nimbers $1,\dots,k$.  If you allow the second observation, then it is not hard to see that if $n \in G_k$, then for every $m < n$, $m\in G_k$.  Indeed, if $n\in G_k$, then I can write $n = \sum a_i$ for some sum of Nimbers with $a_i \leq k$.  Let's play the game $n + \sum a_i$, which is a second-player win by assumption.  Being magnanimous, I'll go first.  On my turn I turn $n$ into $m$.  Now you definitely have a move the return the sum to $0$.  It definitely doesn't involve the pile I touched, so it must involve dropping one of the $a_i$s to an $a_i' < a_i$.  But $a_i$ was one of our generators in $1,\dots,k$, and so $a_i'$ is also one of those generators.
Now we can put the observations together to describe the structure of the Nimbers.  We have $G_0 = \{0\}$ and $G_1 = \{0,1\}$ is the group of order $2$.  By induction, the set of Nimbers $G = \{0,1,\dots,2^k-1\}$ is closed under Nimber addition.  Consider $G_{2^k}$.  It is an $\mathbb F_2$-vector space generated by $G$, which has $2^k$ elements, and by one more element.  Thus $|G_{2^k}| = 2^{k+1}$.  Thus $G_{2^k} = \{0,\dots,2^{k+1}-1\}$.  The induction can then continue.
So the Nimbers are naturally organized as an $\mathbb N$-filtered $\mathbb F_2$-vector space: $$\{0\} \subset \{0,1\} \subset \{0,1,2,3\} \subset \{0,1,2,3,4,5,6,7\} \subset \dots \subset \{0,\dots,2^{k-1}\} \subset \dots.$$
This doesn't completely pin down the addition, but it makes bitxor seem very likely.  For example, it implies that if $m,n \in \{2^{k-1},\dots,2^k-1\}$, so that they have the same leading digit mod $2$, then their sum $m+n < 2^{k-1}$, and on the other hand if $m < 2^{k-1}$ and $n \in \{2^{k-1},\dots,2^k-1\}$, then $m+n \in \{2^{k-1},\dots,2^k-1\}$.  This gives the bitxor rule in the leading digit.
Of course, this analysis still allows lots of group structures on $\{0,\dots,2^k-1\}$.  The rule is only that the structure has to extend the one on $\{0,\dots,2^{k-1}-1\}$.  You can write down ad hoc group structures by twisting the given one by any permutation of $\{2^{k-1},\dots,2^k-1\}$.  To completely pin down the bitxor group law requires playing a bit more with the third observation, I think.  Let's see if we can do it.  We know that the bitxor rule applies to Nimbers $N < 2^k$, by induction.  We also know that $2^k + 2^k = 0$, so it applies to $N \leq 2^k$.  To prove the claim, it suffices to prove that the Nimber of height $2^k+2^j$ for $j<k$ is equal to the Nim addition $2^k + 2^j$.  Everything else will follow from linear algebra.  But now all I need to do is to tell you a second-player-win strategy for the three-column Nim game with heights $2^j$, $2^k$, and $2^k+2^j$.  Well, let's suppose you play on column $2^j$.  Then I have such a strategy by induction in $j$ (and linear algebra).  Suppose you play on column $2^k$.  Then you make it into something in $\{0,\dots,2^k-1\}$, and adding $2^j$ keeps me in that group, so I just need to drop the column of height $2^k+2^j$ to match.  Finally, suppose you play on column $2^k+2^j$.  If you leave it above $2^k$, I'll play on column $2^j$ to match, and use induction in $j$ to know that that works.  If you take it below height $2^k$, I'll drop the $2^k$-column to make the sum come out, using bitxor in the group $\{0,\dots,2^k-1\}$.
Perhaps this is the proof you already know.  It certainly is a follow-your-nose proof.
A: 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.
A: The sum of two games means a turn consists of playing in either game. Then by the mirror strategy, for any impartial game $G$, $G+G=0$, a second player win. That means that under this sum, equivalence classes of impartial games form an abelian group of exponent $2$, or an $F_2$-vector space. XOR describes the additions with respect to any basis, not just the standard one.
You can change the connection with XOR by changing the sum operation. If in a collection of games, you must play in at least one, but up to $k$ games, then the Grundy values of the components matter, but the second-player wins correspond to collections whose sums without carries have all digits divisible by $k+1$. This was observed by Moore where the games are Nim piles. Of course, this is related to your other question. There are other generalizations possible, where you are allowed to play in other collections of multiple games, and you don't simply XOR the Grundy-values of the components. 
