我在一个论坛上提到给定的 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]
我检查了上面的数组数量和l
和r
的不同值以及YES,这是真的。但是我不明白怎么办?
谁能解释一下这背后的逻辑?
最佳答案
使用最简单的异或性质
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)
的定义。
关于algorithm - 有人可以解释以下异或属性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38833308/