关于异或

定义

对两个数的二进制位逐位求异或，如果位相同则取 $0$ ，否则取 $1$

例如 $5\ xor\ 3 = 6$

基本性质

  • $0 \ xor\ n = n$
  • $n \ xor\ n = 0$
  • $a \ xor\ b \ xor\ b = c$
  • $a\ xor\ b\ xor\ c = a\ xor (b\ xor\ c)$

特殊性质

  • 对一个二进制位反复取反，等于它反复地异或 $1$
  • 对于 $1 - n$ 之间所有的数求异或，结果呈现以下特点 a = [x, 1, x + 1, 0] 对于 $x mod4$ 的结果取对应的位数， 例如 $xor[1..4] = a[0] = 4;xor[1..6] = a[2] = 7$
  • 异或的差分和前缀和和普通加减法一致，只不过，异或的逆运算，仍然是异或

由上述性质，我们现在可以得到

  • 任何连续区间的异或和
  • 随机数字的连续异或和（使用前缀和）
  • 区间异或，单点查询的异或（使用差分）