三向异或功能 [英] Three-way xor-like function

问题描述

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

I'm trying to solve the following puzzle:

Given a stream of numbers (only 1 iteration over them is allowed) in which all numbers appear 3 times, but 1 number appear only 2 times, find this number, using O(1) memory.

我首先想到的是，如果所有数字出现2次，而只有1个数字出现一次，则可以在所有数字之间使用xor运算，结果将是隐身数字.

I started with the idea that, if all numbers appeared 2 times, and 1 number only once, I could use xor operation between all numbers and the result would be the incognito number.

所以我想扩展这个想法来解决这个难题.我需要的只是一个类似xor的函数(或运算符)，在第三个apply上将产生0:

So I want to extend this idea to solve the puzzle. All I need is a xor-like function (or operator), which would yield 0 on the third apply:

SEED xor3 X xor3 X xor3 X = SEED

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

对这种功能有什么想法吗?

Any ideas for such a function?

推荐答案

将XOR视为二进制模(以2为基数)表示的数字的每一位的总和.

Regard XOR as summation on each bit of a number expressed in binary (i.e. a radix of 2), modulo 2.

现在考虑由 tribits 0、1和2组成的数值系统.也就是说，它的基数为3.

Now consider a numerical system consisting of tribits 0, 1, and 2. That is, it has a radix of 3.

运算符T现在可以分解为该基数，并且可以对任何数字进行运算.与在XOR中一样，您需要对位求和，但不同之处在于运算符T以模3形式运行.

The operator T now becomes an operation on any number, decomposed into this radix. As in XOR, you sum the bits, but the difference is that operator T is ran in modulo 3.

对于任何a，您可以轻松地显示a T a T a为零.您还可以显示T既可交换又可关联.这是必要的，因为通常情况下，您的序列将使数字混乱.

You can easily show that a T a T a is zero for any a. You can also show that T is both commutative and associative. That is necessary since, in general, your sequence will have the numbers jumbled up.

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

Now apply this to your list of numbers. At the end of the operation, the output will be b where b = o T o and o is the number that occurs exactly twice.

这篇关于三向异或功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！