上一篇文章讲了基本的位运算知识，其实位运算中最神奇的莫过于异或了，来看一下异或运算的性质。
异或满足交换律，结合律，恒等律，归零律，以及有自反性质。
下面详细列举一下：
- 交换律： $A\oplus B=B\oplus A$
- 结合律： $A\oplus (B\oplus C)=(A\oplus B)\oplus C$
- 恒等律： $X\oplus 0=X$
- 归零律： $X\oplus X=0$
- 自反： $A\oplus B\oplus B = A\oplus 0 = A$
- 推论：如果 $a\oplus b=c$, 那么 $a\oplus c=b,b\oplus c=a$, 推广到 n 个数仍然成立
体会一下逆运算
交换变量：swap(a, b) <-> a = a+b; b = a-b; a = a-b;
把 + 号和 - 号都换成 $\oplus$ 符号：$a = a\oplus b; b = a\oplus b; a = a\oplus b;$
第 1 步：$a = a\oplus b, b = b$
第 2 步：$a = a\oplus b, b = (a\oplus b)\oplus b = a$
第 3 步：$a = (a\oplus b)\oplus a = b, b = a$
合成一步用C语言写：a^=b^=a^=b这个方法能够防止溢出，但是有缺点(&a != &b)。
上面的推论推论可以应用于数据备份，RAID 5 用奇偶校验实现冗余。如果阵列中的一块磁盘出现故障，工作磁盘中的数据块与奇偶校验块一起来重建丢失的数据。
假设 A1、A2、A3 代表三块磁盘，Ap 用于备份。假设 A1 = 00000111、A2 = 00000101 以及 A3 = 00000000。A1、A2、A3 异或得到的 Ap 等于 00000010。如果第二个磁盘出现故障，A2 将不能被访问，但是可以通过 A1、A3 与 Ap 的异或进行重建：
A1$\oplus$A3$\oplus$Ap = 00000101
利用异或的逆运算是本身，可以进行简单的对称加密。
异或在集合中用 $\bigtriangleup$ 表示
与，或分别代表集合运算中的交，并而异或则代表对称差，证明如下：
$$
A\bigtriangleup B=(A-B)\cap (B-A)=(A\cup B)-(A\cap B)
$$
来看一道题：
有一列数，每个数字都出现了偶数次，只有一个数出现了一次，怎样在 O(1) 的空间复杂度内找到这个数？
这是一道基于交换律和归零律衍生出来的题，解法比较巧妙，这列数异或得到的结果便是那个只出现一次的数，因为相同的数在异或偶数次之后都变为 0 了。
倘若现在问题难度提高，有两个甚至更多个不同怎么办呢？网上有解到 3 个的，但是我认为从二进制的末位开始枚举，对序列不断的进行划分，问题的难度会不断的下降，最终退化为 1 个的情况，得解。
异或的一个重要应用便是格雷码（Gray code）：格雷码是任意两个相邻数的代码只有一位二进制数不同的 BCD 码，它与奇偶校验码同属可靠性编码，它最初的出现是为了解决讯号传送错误。
格雷码的生成方式有三种：
- 直接生成：以二进制为 0 值的格雷码为第零项，第一步改变最右边的位元，第二步改变右起第一个为 1 的位元的左边位元，第三、四步重复第一、二步，即可排列出 n 个位元的格雷码。
- 镜射生成：n 位元的格雷码可以从 n-1 位元的格雷码以上下镜射后加上新位元的方式快速的得到。
- 二进制生成：G(N) = (B(n)/2) XOR B(n) (G：格雷码 B：二进制码)
有三个开关，如何在最短的步数内遍历所有的状态呢？
三位数格雷码的顺序是：000 -> 001 -> 011 -> 010 -> 110 -> 111 -> 101 -> 100
在三维空间中于相当于沿着立方体的棱不重不漏地经过每一个顶点：
当然，格雷码还可以做很多别的事情，比如分割集合、解汉诺塔，九连环。
我们进行下一题：
假设函数 $f(n)$ 是自然数 $1, 2, 3,…, n$ 的所有数的异或，即 $f(n)=f(n-1)\oplus n=1\oplus 2\oplus 3\oplus …\oplus n$，那么，任意的 $n$（$n$ 为自然数），我们能够很快的计算出 $f(n)$ 的值
神奇么？我们可以先试探着写几个值：$f(0)=0$, $f(1)=1$, $f(2)=3$, $f(3)=0$, $f(4)=4$, $f(5)=1$, $f(6)=7$, $f(7)=0\ldots$ 发现 0 重复出现，可能有周期性，猜想答案为：
$$
\begin{cases}
f(4n)=4n \\
f(4n+1)=1 \\
f(4n+2)=4n+3 \\
f(4n+3)=0
\end{cases}
$$
这个答案可由数学归纳法得出，粗略的证明如下：
当 $n = 0$ 时显然成立
当 $n = k$ 时假设成立
当 $n = k+1$ 时：$f(4(k+1))=f(4k+3)\oplus 4(k+1)=0\oplus 4(k+1)=4(k+1)$
$f(4(k+1)+1)=f(4(k+1))\oplus (4(k+1)+1)=4(k+1)\oplus (4(k+1)+1)=1$（因为 $4(k+1)$ 的二进制末位一定是 $0$，所以 $4(k+1)$ 与 $4(k+1)$ 只有末位不同）
$f(4(k+1)+2)=f(4(k+1)+1)\oplus (4(k+1)+2)=1\oplus (4(k+1)+2)=4(k+1)+3$（因为 $4(k+1)+2$ 的二进制末两位一定是 $10$，所以 $1$ 与 $4(k+1)+2$ 异或后末两位为 $11$）
$f(4(k+1)+3)=f(4(k+1)+2)\oplus (4(k+1)+3)=4(k+1)+3\oplus (4(k+1)+3)=0$
参考
文档信息
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
本文链接：www.snovey.com/2016/08/xor.html