logic - 如果给出了array(XOR)array[1:]，则查找一个数组

Question

考虑我们有数组 a，第二个数组 b = a[1:]（只是删除了 a 的第一个元素）。我们得到数组 c，它是 XOR 的结果，c[i] = a[i]*b[i] (0<=i<len(b))。如果我们知道 c ，我们能找到数组 a 吗？我们也得到 [0:7]

Answer 1

证明你做不到很简单。

c比 少一个元素a。如果以完全可恢复的方式c表示相同的信息，则可以以相同的方式一次又一次地压缩，直到只剩下一个元素。显然，转换是有损的。ac

反过来说，根据 XOR 来选择一对数字并没有唯一的方法。无论您选择哪个数字作为配对中的第一个，都有一个解决方案。

但是，给定c和 的任何元素a，您都可以完全恢复a。鉴于(x ^ y) ^ y = x ^ (y ^ y) = x, 和c[i] = a[i] ^ a[i + 1], 很容易展开a给定 any的值a[i]。

不失一般性，让我们假设你是给定的a[0]。既然c[0] = a[0] ^ a[1]，我们明白了a[1] = c[0] ^ a[0]。现在可以找到a[2] = c[1] ^ a[1]了，以此类推a[i]。