关于异或

发布于 7 天前  21 次阅读


因为每次做异或的题都感觉不好下手, 然而异或是一种性质非常多的奇妙运算.所以写一篇总结

异或和数据结构

口胡一下子,可以套线性基,01trie

异或的性质

异或可以看做是一种不进位的加法,有这样一些性质(统一用\oplus符号表示异或运算)

归零律

a \oplus a = 0

恒等律

a \oplus 0 = a

交换律

a \oplus b = b \oplus a

重要推论: 当 a \oplus b = c 时, a \oplus c = b , b \oplus c = a 同样成立

自反性

a \oplus b \oplus a = b

前缀异或

其实我也不知道这个叫前缀异或还是异或差分,反正讲的应该是一个东西.

基本上就是记一个 sum 数组,其 sum_1 = a_1, sum_i = sum_{i-1} \oplus a_i

那么这个玩意儿有什么用呢

a_i \oplus a_{i+1} \oplus a_j = sum_j \oplus sum_{i -1}

好了没了


朴实沉毅