For a certain algorithm, I need a function $f$ on integers such that
$a_1 \oplus a_2 \oplus \, \cdots\,\oplus a_n = 0 \implies f(a_1) \oplus f(a_2) \oplus \, \cdots\,\oplus f(a_n) \neq 0$
(where the $a_i$ are pairwise distinct, non-negative integers and $\oplus$ is the bitwise XOR operation)
The function $f$ should be computable in $O(m)$, where $m$ is the maximum number of digits of the $a_i$. Of course the simpler the function is, the better. Preferrably the output of the function would fit into $m$ digits as well.
Is there something like this? It would also be okay to have a family of finitely many functions $f_n$ such that for one of the functions the result of the above operation will be $\neq 0$.
My own considerations so far were the following:
- If we choose the ones' complement as $f$, we can rule out all cases where $n$ is odd.
- If $n$ is even, this means that for every bit, an even number of the $a_i$ has the bit set and the rest has not, therefore taking the ones' complement before XORing doesn't change the result.
So the harder part seems to be the case where $n$ is even.