异或运算是位运算，不产生进位，也不会对其他bit产生影响。一般用XOR表示，在C语言中，异或用‘^‘表示。

异或运算法则与无进位的二进制加法一致：0^0=0，1^0=1，0^1=1，1^1=0（同为0，异为1）

对任意元素a, 令其二进制位第k位为a[k]，

真值表：

异或运算有如下规律：

1) 交换律 a ^ b = b ^ a

　　由真值表, 对任意k，有a[k] ^ b[k] = b[k] ^ a[k]。因为异或不对其他位产生影响，可得a ^ b = b ^ a。

2) 恒等律 a ^ 0 = a

　　同上

3) 归零律 a ^ a = 0

　　同上

4) 结合律 (a ^ b) ^ c = a ^ (b ^ c)

第一种方法，列出a[k],b[k], c[k] 和 (a[k] ^ b[k]) ^ c[k] = a[k] ^ (b[k] ^ c[k])真值表即可。

第二种方法，由异或基本性质：a[k] ^ b[k] = (a[k] + b[k]) % 2 

 (a[k] ^ b[k]) ^ c[k] = ((a[k] + b[k]) % 2 + c[k]) % 2 = (a[k] + b[k] + c[k]) % 2

同理，a[k] ^ (b[k] ^ c[k]) = (a[k] + b[k] + c[k]) % 2, 得证。

简单应用：原地交换两个数：

a = a ^ b 

b = a ^ b

a = a ^ b

假设原来的a, b 表示为ak, bk

第一步：a = ak ^ bk

第二步：b = a ^ bk = (ak ^ bk) ^ bk = ak ^ (bk ^ bk) = ak ^ 0 = ak

第三步：a = a ^ b = (ak ^ bk) ^ ak = ak ^ (ak ^ bk) = (ak ^ ak) ^ bk = 0 ^ bk = bk ^ 0 = 0

得证。

异或运算