algorithm - 或通过对列表中的所有数字进行异或运算而形成的所有对。

Question

或通过对列表中的所有数字进行异或运算而形成的所有对。

例如:10,15,17

ans = (10^15)|(15^17)|(10^17) = 31 。我做了一个 o(n*k) 算法，但需要比这更好的东西(n 是条目数，k 是每个数字中的位数)。

Answer 1

在这里消极地思考可能是最容易的。

XOR 基本上是“不等于”——即，当且仅当两个输入位彼此不相等时，它才会产生结果 1。

由于您将所有这些结果进行 OR 运算，这意味着在至少有两个输入在该位位置具有不同值的任何地方，您都会在结果中得到一个 1 位。

相反，这意味着我们在结果中得到一个零仅，其中每个输入在该位位置具有相同的值。

为了计算我们可以累加两个中间值。首先，我们将所有输入加在一起。这将为我们提供每个输入都有一个的位置。另一方面，我们反转每个输入，并将所有这些结果组合在一起。这将告诉我们所有输入的值为 0 的每个位置。

或将它们加在一起，我们得到一个值，其中每个输入都相等，值为 1，否则为 0。

反转它，我们得到了想要的结果:0 表示所有输入都相等，1 表示所有输入不同。

这让我们可以用线性复杂度计算结果(假设每个输入值适合一个单词)。