有人能解释以下XOR属性吗？

Question

在一个论坛上提到，给定长度为n的数列：n numbers。

arr[0........n-1]

以下条件成立，^是xor操作符。

f(l,r) = f(0,r) ^ f(0,l-1)

其中f(l,r) = arr[l]^arr[l+1]^........arr[r]

我检查了上述内容，使用不同的数组和l、r值，是正确的。但我不明白为什么？

有人能解释一下背后的逻辑吗？

- J J

---

写出 f(0,r) ^ f(0,l-1) 的展开式，然后约分。 - Oliver Charlesworth

Answer 1

使用XOR的最简单属性

f(0,r) ^ f(0,l-1) = f(l,r)
=> (f(0,r) ^ f(0,l-1)) ^ f(0,l-1) =  f(0,l-1) ^ f(l,r)
=> f(0,r) = f(l,r) ^ f(0,l-1) [Since XOR is associative f(0,l-1) ^ f(0,l-1) = 0 and x ^ 0 = x]  
=> f(0,r) = (arr[0]^...arr[l-1])^(arr[l]^...^arr[r])

这是关于f(0,r)的定义。

- Shashwat Kumar

Answer 2

数字 arr[0...r] 可以看作两部分 arr[0...l-1], arr[1...r]，因此 f(0,r) = f(0,l-1) ^ f(l,r)，通过单独处理这两个部分。

在 f(l,r) = f(0,r) ^ f(0,l-1) 中，f(0,l-1) 与 f(0,r) 相消得到 f(l,r)。

- David Johnston