有人可以解释以下 xor 属性吗

Question

我在论坛上提到给定的n数字数组：

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]

我检查了上面的数组数量和不同值landr和YES，这是真的。但我不明白怎么办？

有人可以解释一下这背后的逻辑吗？

Answer 1

使用最简单的异或属性

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)。

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(0,l-1) 相消留下 f(l,r) 。