[数论] 异或

发布时间:2024年01月02日

异或的性质

异或可抵消

a xor b xor b = a

异或可交换

a xor b xor b = b xor b xor a

异或可以看成模2的加法

遇0不变,遇1则变,双1则不变

所以上面的结果是1

求异或和

先看看加法的前缀和

类比,我们可以得到 范围(L,R)的异或和,设 S_R 表示从1到R的元素异或和,将S_L-1 与S_R异或

来解释一下为什么,展开来看

因为相同两项异或可抵消,所以S_L-1 与S_R异或之后,刚好剩下从 a_L 一直异或到 a_R

S_L-1 = S_L-1 ^ a_L

文章来源:https://blog.csdn.net/weixin_73512213/article/details/135338047
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。