[数论] 异或

2024-01-02 16:43:49

异或的性质

异或可抵消

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
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。