# What other involutions are there besides xor?

There is a classic problem of finding the only number that occurs an odd number of times in a list. The solution is to xor everything and the result is the requested number.

The key properties used here are the involution of xor (i.e. a number's inverse is the same number) and the closure over integer range of the variable.

Now, are there any other operations that could be used for this? I could only find 1/x which, unfortunately, cannot be used due to precision erros.

• How would you use 1/x for non-zero rational numbers? ​ (They avoid the precision errors.) ​ ​ ​ ​ – user12859 Feb 3 '17 at 13:22
• The question is equivalent to asking a description of all automorphism on Boolean group of each size. – Billiska Feb 3 '17 at 13:31
• @RickyDemer Multiply all the inverses in the list. The inverse of the result is what you are looking for, but this is very hard to implement in practice since you have to deal either with performing the divisions (thus rounding errors) or with simplifications (thus not very effificent). – Paul92 Feb 3 '17 at 14:35
• When your list is [1/2,1/2,1/2], multiplying "all the inverses in the list" gives either 1/8 or 8 depending on what you mean by that. ​ ​ ​ The inverses of ​ 1/8 , 8 ​ are ​ 8 , 1/8 ​ respectively, but neither of those is 1/2, which is "the only number that occurs an odd number of times in" [1/2,1/2,1/2]. ​ ​ ​ ​ ​ ​ ​ – user12859 Feb 3 '17 at 14:43

Take an arbitrary bijection $f$ from the integers to integers. This is a permutation of the integers.
Then, take the conjugate of XOR ($\oplus$): $$g(x,y) = f^{-1}(f(x) \oplus f(y))$$ We then have $$g(x,x) = f^{-1}(0)$$ which now acts as the "new zero" (neutral element) $$g(x,f^{-1}(0)) = x$$ We also have that $g$ is associative and commutative $$g(x,y) = g(y,z) \qquad g(g(x,y),z) = g(x,g(y,z))$$ So, we still have an abelian group where $x^{-1}=x$. The trick on arrays mentioned by the OP still works.