function - 三路异或类函数

Question

我正在尝试解决以下难题:

给定一个数字流(只允许对其进行 1 次迭代)，其中所有数字出现 3 次，但 1 个数字仅出现 2 次，使用 O(1) 内存找到该数字。

我的想法是，如果所有数字出现 2 次，而 1 个数字只出现一次，我可以在所有数字之间使用xor 运算，结果将是隐身号码。

所以我想扩展这个想法来解决这个难题。我所需要的只是一个类似异或的函数(或运算符)，它在第三次应用时会产生 0:

SEED xor3 X xor3 X xor3 X = SEED

X xor3 Y xor3 SEED xor3 X xor3 Y xor3 Y xor3 X = SEED

对于这样的功能有什么想法吗？

Answer 1

将 XOR 视为对以二进制(即基数 2)表示的数字的每一位求和，模 2。

现在考虑一个由三位 0、1 和 2 组成的数值系统。也就是说，它的基数为 3。

运算符T现在成为对任意数字的运算，分解为该基数。与 XOR 一样，您对位求和，但不同之处在于运算符 T 以模 3 运行。

您可以轻松证明对于任何a，a T a T a 都为零。您还可以证明 T 既可交换又可结合。这是必要的，因为一般来说，您的序列中的数字会变得困惑。

现在将其应用到您的号码列表中。操作结束时，输出将为 b，其中 b = o To 且 o 是恰好出现两次的数字。