patternMinor
What other involutions are there besides xor?
Viewed 0 times
xorbesidesinvolutionswhatareotherthere
Problem
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.
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.
Solution
Roll your own.
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.
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.
Context
StackExchange Computer Science Q#69793, answer score: 7
Revisions (0)
No revisions yet.