異或運算常見的應用
大家可能比較熟悉 "與" 運算 和 "或" 運算 ，相對而言， "異或" 運算 平常使用較少，存在感也不強，如果不是刻意提起，可能還想不到它
其實，"異或" 運算也非常重要，它在加密、備份、算法等方面都有應用，每一位開發的同學都應該花點兒時間掌握它的特點和規律，以便在日常工作中能靈活的運用
接下來將介紹異或運算的一些基礎知識以及在實際中的一些應用
基礎知識
異或是計算機中一種二元邏輯運算， 運算符號是 ^，它按照二進制位進行異或運算，結果為 真 或 假， 它的運算法則如下
| x | y | x^y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
表格 第一列 和 第二列 是異或運算的兩個操作數，第三列是異或運算的結果，1 表示真，0 表示假
由表格可知：如果參與運算的兩個二進制位相同，則結果為 0 ，否則為 1
也就是說，異或主要用來判斷兩個值是否相同
重要的性質
下面列出異或運算一些重要的性質，1 表示真，0 表示假， 具體的驗證過程比較簡單，這里就省略了
1、一個數與自身異或，總是為 0
- x ^ x = 0
2、 一個數與 0 異或，總是其自身
- x ^ 0 = x
3、 交換性
- x ^ y = y ^ x
4、 結合性
- x ^ ( y ^ z ) = ( x ^ y ) ^ z
常見應用
異或運算本身比較簡單，重點還是在應用層面，上面列出的性質，在很多方面都有應用
- 判斷兩個數是否相等
一個數與自身異或，總是為 0，我們可以使用這一點來判斷兩個變量是否相等
- ( a ^ b ) == 0
當 a 和 b 相等時，表達式為真，否則為假
- 不使用臨時變量交換兩個數的值
要交換兩個數的值，通常做法是借助一個臨時變量，然后再進行交換，比如：tmp 是臨時變量，現需要交換 a 和 b 兩個變量值，過程如下
- tmp = a
- a = b
- b = tmp;
利用異或的一些性質，不用臨時變量也能實現交換兩個數的值，具體過程如下
- a = a ^ b
- b = a ^ b
- a = a ^ b
假如初始時，a = 1、b = 2
第一個等式 a = a ^ b 結果是 a = 1 ^ 2 = 3
緊接著第二個等式 b = a ^ b 結果是 b = 1 ^ 2 ^ 2 = 1 ^ 0 = 1
最后一個等式 a = a ^ b 結果是 b = 1 ^ 2 ^ 1 = 1 ^ 1 ^ 2 = 0 ^ 2 = 2
可以看到，最終 a = 2、 b = 1 ，它們的值實現了交換
上面的三條語句還可以進一步優化成一條，結果如下
- a ^= b ^= a ^= b
- 簡化表達式
根據交換性，可以優化表達式中重復變量的異或運算，比如：表達式 a ^ b ^ c ^ a ^ b 可以做如下簡化
- a ^ b ^ c ^ a ^ b # 根據 x ^ y = y ^ x
- = ( a ^ a ) ^ ( b ^ b ) ^ c # 根據 x ^ x = 0
- = 0 ^ 0 ^ c # 根據 x ^ 0 = x
- = c
- 加密
利用異或運算加密是很常見的加密手段，它涉及到三個變量：明文、密鑰、密文，假如它們分別記為 plain_text、 encrypt_key、 cipher_text
明文和密鑰進行異或運算，可以得到密文
- plain_text ^ encrypt_key = cipher_text
密文和密鑰進行異或運算，可以得到明文
- cipher_text ^ encrypt_key
- = ( plain_text ^ encrypt_key ) ^ encrypt_key
- = plain_text ^ ( encrypt_key ^ encrypt_key ) # 根據 x ^ ( y ^ z ) = ( x ^ z ) ^ y
- = plain_text ^ 0 # 根據 x ^ x = 0
- = plain_text
- 備份
根據異或的性質，異或運算還可以用于文件的備份
現有兩個文件 filea 和 fileb，它們進行異或運算，會產生一個新的備份文件 bakfile
- bakfile = filea ^ fileb
根據異或的性質，可以通過 bakfile 和 filea 得到 fileb，或者通過 bakfile 和 fileb 得到 filea
后面無論是 filea 或 fileb 文件損壞了，只要不是兩個文件同時損壞，都可以通過兩者中未損壞的文件 和 bakfile 文件，還原得到另一個文件
當 filea 文件損壞了，可以通過 fileb 和 bakfile 進行異或運算得到完好的 filea 文件
- fileb ^ bakfile
- = fileb ^ ( filea ^ fileb )
- = fileb ^ filea ^ fileb # 根據 x ^ ( y ^ z ) = ( x ^ z ) ^ y
- = fileb ^ fileb ^ filea # 根據 x ^ x = 0
- = 0 ^ filea # 根據 x ^ 0 = x
- = filea
同樣，當 fileb 文件損壞了，可以通過 filea 和 bakfile 進行異或運算得到完好的 fileb 文件
f
- filea ^ bakfile
- = filea ^ ( filea ^ fileb )
- = filea ^ filea ^ fileb # 根據 x ^ ( y ^ z ) = ( x ^ z ) ^ y
- = filea ^ filea ^ fileb # 根據 x ^ x = 0
- = 0 ^ fileb # 根據 x ^ 0 = x
- = fileb
解算法題
有些算法可以利用異或的思路進行求解，下面列出力扣上的一道算法題來說明，題目如下：
- 一個長度為 n-1 的遞增排序數組中的所有數字都是唯一的，并且每個數字都在范圍 0 ～ n-1 之內，
- 在范圍 0 ～ n-1 內的 n 個數字中有且只有一個數字不在該數組中，請找出這個數字
- 示例 1:
- 輸入: [ 0,1,3 ]
- 輸出: 2
- 示例 2:
- 輸入: [ 0,1,2,3,4,5,6,7,9 ]
- 輸出: 8
最快捷的解決方法是把數組的所有元素以及 0 到 n-1 之間的整數 全部進行異或運算
- arry[0] ^ arry[1] ^ arry[2] ... ^ arry[n-2] ^ 0 ^ 1 ^ 2 .... ^ (n-1)
由于數組元素值范圍在 0 到 n-1，且所有元素值都沒有重復
所以，上述的計算式子中，0 到 n-1 每個數會出現兩次，只有缺少的那個數僅出現一次，根據異或的性質 x ^ x = 0 可知，相同值之間的異或運算等于 0，因此算式的結果其實就是缺少的那個數
下面給出測試文件 test.cpp，代碼是用 C++ 實現的，可以自行用其他語言實現
- #include <stdint.h>
- #include <iostream>
- using namespace std;
- int32_t find_missing(int32_t *ary, int32_t len)
- {
- //數組長度小于等于1，直接返回 -1
- if(len <= 1)
- {
- return -1;
- }
- //結果
- int32_t result = 0;
- //result 和 數組中每一個元素值進行異或運算
- for (int32_t i = 0; i < len; i++)
- {
- result ^= ary[i];
- }
- //result 和 0 到 n 中每一個值進行異或運算
- for (int32_t j = 0; j <= len; j++)
- {
- result ^= j;
- }
- return result;
- }
- //編譯: g++ -g -o test test.cpp
- int32_t main(int32_t argc , char *argv[])
- {
- int32_t ary[] = { 0, 1, 3 };
- int32_t result = find_missing(ary, sizeof(ary) / sizeof(int32_t));
- std::cout << "result = " << result << std::endl;
- return 0;
- }
使用 g++ -g -o test test.cpp 命令編譯，接著運行程序，結果如下：
- [root@localhost test]# ./test
- result = 2
當然，這道題目還有其他的解法，比如：利用加法來解，大家自己去思考下，這里不做介紹了
題目鏈接 https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
小結
通過上文，我們可以看到，異或運算在很多方面都有應用，其實，它的應用遠不止文中介紹的方面，所以，我們花時間去掌握它是非常值得做的一件事
