1. 異或運算
在數字邏輯中败许，邏輯算符互斥（exclusive or）是對兩個運算元的一種邏輯分析類型慈省，符號為XOR或EOR或⊕。
a⊕b = (?a ∧ b) ∨ (a ∧?b)
其真值表如下：
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
總結：
如果兩個二進制位相同抢蚀，就返回0地沮，表示false；否則返回1嘉汰，表示true丹禀。
真值結果是無進位的二進制加法得到的結果。
2. 異或運算的特性
-
交換律：
結合律：
- 恒等律：
- 歸零律：
- 自反律：
以上均可根據a⊕b = (?a ∧ b) ∨ (a ∧?b)的算法定義進行證明鞋怀。
3.應用
- 快速比較兩值是否想等
r = a xor b
if a==b
r == 0
else
r != 0
檢驗一個數字中1的個數的奇偶（奇偶校驗）
求10100001中1的個數
1 ^ 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1
按位進行異或運算得到的結果等于1双泪，結果為奇數，得到的結果為0密似，結果為偶數不使用中間變量焙矛，交換兩個變量的值
a = a ^ b;
b = a ^ b; //a ^ b ^ b = a ^ 0 = a;
a = a ^ b;
- 面試題：一個整型數組里除了一個數字之外，其他的數字都出現了兩次残腌，找出這個數字
對于數組{a, a, b, b, c, c, d}村斟，找出只出現了一次的數字d
a^a^b^b^c^c^d
= 0 ^ 0 ^ 0 ^d
= 0 ^ d
= d
時間復雜度為O(N), 空間復雜度為O(1)
- 在密碼學中的應用
message XOR key // cipherText
cipherText XOR key // message
明文 XOR 密鑰 --> 密文
密文 XOR 密鑰 --> 明文
以上特性很好地對應了加密和解密的過程。所以目前很多加密算法都利用了異或算法的這個特性來做最后的密文打亂的工作废累。
參考資料：
http://www.ruanyifeng.com/blog/2017/05/xor.html
https://www.lijinma.com/blog/2014/05/29/amazing-xor/
https://zh.wikipedia.org/wiki/%E9%80%BB%E8%BE%91%E5%BC%82%E6%88%96
