异或运算的重要性质

核心性质

1. 交换律、结合律

   • 交换律：

     $a \oplus b = b \oplus a$

   • 结合律：

     $(a \oplus b) \oplus c = a \oplus (b \oplus c)$

     这两条保证了多次异或可以任意重排、分组，便于前缀、后缀、分块等技巧。

2. 与“零”的关系

   • 恒等元：

     $a \oplus 0 = a$

   • 自反元：

     $a \oplus a = 0$

     这就意味着“异或一个数两次等于回到原来”，可以用来快速“抵消”已出现的值。

3. 消去律

   $(a \oplus b) \oplus b = a$

   或者更一般地，若已知 $X = A \oplus B$，则

   $A = X \oplus B,\quad B = X \oplus A$

   这让你在已知两个值的异或结果时，可以很快“反算”出原值。

4. 位级独立性

   异或运算，对每一位都是“模 2 加法”：

   $1\oplus1=0,\quad1\oplus0=1,\quad0\oplus0=0$

   因此，它不会产生“进位”，每一位都可以单独看作 GF(2) 上的加法。

5. 与其他位运算的配合

   • 翻转位：

     用全 1 掩码（如 ~0 或 (1<<k)-1）对某段连续 k 位做异或，就能一次性翻转这 k 位。

   • 按位筛选：

     如果你想判断二进制中第 i 位是否为 1，可写

     bool bit = (x >> i) & 1;

     而如果想“清零”最低位的 1，可以用

     x &= x - 1;  // 清除最右侧的 1

     其背后也是因为 $x-1$ 和 $x$ 在最低位 1 之前的所有位都异或发生了变化。

6. 常见小技巧

   • 交换两个变量（无第三变量）：

     a ^= b;
     b ^= a;  // 此时 b = 原 a
     a ^= b;  // 此时 a = 原 b

   • 判断奇偶性：

     多数时候，用 x & 1 就能判断奇偶。但如果想统计区间里“异或和”后最低位是不是 1，就直接看 xor_sum & 1。

7. 前缀／后缀异或

   记 pre[i] = a[1] ^ a[2] ^ … ^ a[i]，由于结合＋消去律：

   $a[l]\oplus … \oplus a[r] = pre[r]\oplus pre[l-1]$

   这是“异或前缀和”技巧的理论基础，也是常见区间查询、子数组计数的核心。