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.)
Best Answer
Let's assume the strings have n bits and the zero string is the identity element. Then the number of different operations is (2^n-1)! divided by the number computed by the formula in this link with p=2. In the case of n=2 the answer is that XOR is unique as mentioned by Matchu, but in general there are many, many different operations that satisfy the conditions. For example, for n=5 there are 822,336,494,953,469,303,808,000,000 different operations.
Every commutative, associative, self-inverse binary operation on a finite set is essentially XOR on bit strings of a fixed length, by the classification of finite abelian groups. As egreg says, this turns the set into a vector space of dimension n over the field with two elements. Any two groups of this type with the same size are isomorphic so any function from the set of bit strings to itself that is one-to-one, onto, and fixes 0 gives another operation, which is possibly the same.
The operation is the same if and only if the function is an automorphism of the vector space, and the group of such automorphisms is called the general linear group, in this case of a vector space of dimension n over the finite field with two elements.
The group of all permutations of the nonzero elements, which has (2^n-1)! elements, acts on the set of satisfactory binary operations, and the stabilizer of an operation, which is a subgroup of the group of such permutations, has the same size as the general linear group. By the orbit-stabilizer theorem, the number of different operations is (2^n-1)!/(size of the general linear group).