# XOR is commutative, associative, and its own inverse. Are there any other such functions?

In particular, I was musing on this trick for swapping two values in a program without allocating any new variables. Wikipedia proves its correctness, and the proof picqued my curiosity.

It relies on the following four properties of XOR:

• Commutativity: $A \oplus B = B \oplus A$
• Associativity: $(A \oplus B) \oplus C = A \oplus (B \oplus C)$
• Identity exists: there is a bit string, 0, (of length N) such that $A \oplus 0 = A$ for any $A$
• Each element is its own inverse: for each $A$, $A \oplus A = 0$.

I suspect that it'd be trivial to construct another group for which those four properties of XOR hold, so I'm not interested in the assertion that other such groups exist. Instead, I ask:

Are there any other functions over bit strings that satisfy these same properties? If so, what are some examples? If not, can we prove that?

(For example, my first thought was $|x - y|$ while interpreting the binary strings as integers, which satisfies commutativity, identity existence, and each element being its own inverse, but not associativity.)

• (Incidentally, I don't know enough about abstract algebra to know if it's the correct tag, but the tag's description sounded reasonable. Feel free to retag as you see fit—thanks!) – Matchu Oct 6 '14 at 22:02
• Also, it's easy to show that XOR is the only operation to satisfy these properties over the domain $\{0, 1\}$, so anything that works on a bit-by-bit level is definitely right out. I suspect that, if the answer is "yes", mapping to some other domain will be the easiest way to show it… – Matchu Oct 6 '14 at 22:07
• Hmm. XOR is also the only satisfactory choice for two-bit strings. All operations that include the identity $00$ are predefined, as are all operations between a value and itself, so we're left with the operations $a \oplus b$ such that $a \neq b$ and $00 \notin \{a, b\}$. $a \oplus b$ must not be the identity or $a$ or $b$ in order to satisfy the properties (the proof of which I'll leave to you; you end up with the contradiction that $a = b$ or that $00 \in \{a, b\}$), so there's only one valid result, and it's the result that XOR chooses, too. – Matchu Oct 6 '14 at 22:24
• Any elementary $2$-group satisfies the request, that is a group $G$ such that $g^2=1$ for all $g\in G$. These groups can also be seen as the vector spaces over the field with two elements. – egreg Oct 6 '14 at 22:37
• Incidentally, the last three conditions of the four given imply the first one. – rschwieb Mar 19 '15 at 12:12