[[434244]]

大家可能比較熟悉 "與" 運(yùn)算 和 "或" 運(yùn)算 ，相對(duì)而言， "異或" 運(yùn)算 平常使用較少，存在感也不強(qiáng)，如果不是刻意提起，可能還想不到它

其實(shí)，"異或" 運(yùn)算也非常重要，它在加密、備份、算法等方面都有應(yīng)用，每一位開發(fā)的同學(xué)都應(yīng)該花點(diǎn)兒時(shí)間掌握它的特點(diǎn)和規(guī)律，以便在日常工作中能靈活的運(yùn)用

接下來將介紹異或運(yùn)算的一些基礎(chǔ)知識(shí)以及在實(shí)際中的一些應(yīng)用

基礎(chǔ)知識(shí)

異或是計(jì)算機(jī)中一種二元邏輯運(yùn)算， 運(yùn)算符號(hào)是 ^，它按照二進(jìn)制位進(jìn)行異或運(yùn)算，結(jié)果為 真 或 假， 它的運(yùn)算法則如下

表格 第一列 和 第二列 是異或運(yùn)算的兩個(gè)操作數(shù)，第三列是異或運(yùn)算的結(jié)果，1 表示真，0 表示假

由表格可知：如果參與運(yùn)算的兩個(gè)二進(jìn)制位相同，則結(jié)果為 0 ，否則為 1

也就是說，異或主要用來判斷兩個(gè)值是否相同

重要的性質(zhì)

下面列出異或運(yùn)算一些重要的性質(zhì)，1 表示真，0 表示假， 具體的驗(yàn)證過程比較簡(jiǎn)單，這里就省略了

1、一個(gè)數(shù)與自身異或，總是為 0

x ^ x = 0 

2、 一個(gè)數(shù)與 0 異或，總是其自身

x ^ 0 = x 

3、 交換性

x ^ y = y ^ x 

4、 結(jié)合性

x ^ ( y ^ z ) = ( x ^ y ) ^ z 

常見應(yīng)用

異或運(yùn)算本身比較簡(jiǎn)單，重點(diǎn)還是在應(yīng)用層面，上面列出的性質(zhì)，在很多方面都有應(yīng)用

• 判斷兩個(gè)數(shù)是否相等

一個(gè)數(shù)與自身異或，總是為 0，我們可以使用這一點(diǎn)來判斷兩個(gè)變量是否相等

( a ^ b ) == 0 

當(dāng) a 和 b 相等時(shí)，表達(dá)式為真，否則為假

• 不使用臨時(shí)變量交換兩個(gè)數(shù)的值

要交換兩個(gè)數(shù)的值，通常做法是借助一個(gè)臨時(shí)變量，然后再進(jìn)行交換，比如：tmp 是臨時(shí)變量，現(xiàn)需要交換 a 和 b 兩個(gè)變量值，過程如下

tmp = a 
a = b 
b = tmp; 

利用異或的一些性質(zhì)，不用臨時(shí)變量也能實(shí)現(xiàn)交換兩個(gè)數(shù)的值，具體過程如下

a = a ^ b 
 
b = a ^ b 
 
a = a ^ b 

假如初始時(shí)，a = 1、b = 2

第一個(gè)等式 a = a ^ b 結(jié)果是 a = 1 ^ 2 = 3

緊接著第二個(gè)等式 b = a ^ b 結(jié)果是 b = 1 ^ 2 ^ 2 = 1 ^ 0 = 1

最后一個(gè)等式 a = a ^ b 結(jié)果是 b = 1 ^ 2 ^ 1 = 1 ^ 1 ^ 2 = 0 ^ 2 = 2

可以看到，最終 a = 2、 b = 1 ，它們的值實(shí)現(xiàn)了交換

上面的三條語句還可以進(jìn)一步優(yōu)化成一條，結(jié)果如下

a ^= b ^= a ^= b 

• 簡(jiǎn)化表達(dá)式

根據(jù)交換性，可以優(yōu)化表達(dá)式中重復(fù)變量的異或運(yùn)算，比如：表達(dá)式 a ^ b ^ c ^ a ^ b 可以做如下簡(jiǎn)化

a  ^  b  ^  c  ^  a  ^  b                   # 根據(jù) x ^ y  = y ^ x 
 
=  ( a  ^  a )  ^  ( b  ^  b )  ^  c        # 根據(jù) x  ^ x = 0 
 
=  0  ^  0  ^  c                            # 根據(jù) x ^ 0 = x 
 
= c 

• 加密

利用異或運(yùn)算加密是很常見的加密手段，它涉及到三個(gè)變量：明文、密鑰、密文，假如它們分別記為 plain_text、 encrypt_key、 cipher_text

明文和密鑰進(jìn)行異或運(yùn)算，可以得到密文

plain_text ^ encrypt_key = cipher_text 

密文和密鑰進(jìn)行異或運(yùn)算，可以得到明文

cipher_text ^ encrypt_key  
= ( plain_text  ^  encrypt_key ) ^ encrypt_key 
= plain_text  ^ ( encrypt_key ^ encrypt_key )   # 根據(jù) x ^ ( y ^ z ) = ( x ^ z ) ^ y 
= plain_text  ^  0                              # 根據(jù) x ^ x = 0 
= plain_text 

• 備份

根據(jù)異或的性質(zhì)，異或運(yùn)算還可以用于文件的備份

現(xiàn)有兩個(gè)文件 filea 和 fileb，它們進(jìn)行異或運(yùn)算，會(huì)產(chǎn)生一個(gè)新的備份文件 bakfile

bakfile = filea ^ fileb 

根據(jù)異或的性質(zhì)，可以通過 bakfile 和 filea 得到 fileb，或者通過 bakfile 和 fileb 得到 filea

后面無論是 filea 或 fileb 文件損壞了，只要不是兩個(gè)文件同時(shí)損壞，都可以通過兩者中未損壞的文件 和 bakfile 文件，還原得到另一個(gè)文件

當(dāng) filea 文件損壞了，可以通過 fileb 和 bakfile 進(jìn)行異或運(yùn)算得到完好的 filea 文件

fileb  ^  bakfile 
=  fileb  ^ ( filea  ^  fileb ) 
=  fileb  ^  filea  ^  fileb        # 根據(jù) x ^ ( y ^ z ) = ( x ^ z ) ^ y 
=  fileb  ^  fileb  ^  filea        # 根據(jù) x ^ x = 0 
=  0  ^ filea                       # 根據(jù) x ^ 0 = x 
=  filea 

同樣，當(dāng) fileb 文件損壞了，可以通過 filea 和 bakfile 進(jìn)行異或運(yùn)算得到完好的 fileb 文件

f

filea  ^  bakfile 
=  filea  ^ ( filea  ^  fileb ) 
=  filea  ^  filea  ^  fileb        # 根據(jù) x ^ ( y ^ z ) = ( x ^ z ) ^ y  
=  filea  ^  filea  ^  fileb        # 根據(jù) x ^ x = 0 
=  0  ^ fileb                       # 根據(jù) x ^ 0 = x 
=  fileb 

解算法題

有些算法可以利用異或的思路進(jìn)行求解，下面列出力扣上的一道算法題來說明，題目如下：

一個(gè)長(zhǎng)度為 n-1 的遞增排序數(shù)組中的所有數(shù)字都是唯一的，并且每個(gè)數(shù)字都在范圍 0 ～ n-1 之內(nèi)， 
 
在范圍 0 ～ n-1 內(nèi)的 n 個(gè)數(shù)字中有且只有一個(gè)數(shù)字不在該數(shù)組中，請(qǐng)找出這個(gè)數(shù)字 
 
 
示例 1: 
 
輸入: [ 0,1,3 ] 
 
輸出: 2 
 
 
示例 2: 
 
輸入: [ 0,1,2,3,4,5,6,7,9 ] 
 
輸出: 8 

最快捷的解決方法是把數(shù)組的所有元素以及 0 到 n-1 之間的整數(shù) 全部進(jìn)行異或運(yùn)算

arry[0] ^ arry[1] ^ arry[2] ... ^ arry[n-2] ^ 0 ^ 1 ^ 2 .... ^ (n-1) 

由于數(shù)組元素值范圍在 0 到 n-1，且所有元素值都沒有重復(fù)

所以，上述的計(jì)算式子中，0 到 n-1 每個(gè)數(shù)會(huì)出現(xiàn)兩次，只有缺少的那個(gè)數(shù)僅出現(xiàn)一次，根據(jù)異或的性質(zhì) x ^ x = 0 可知，相同值之間的異或運(yùn)算等于 0，因此算式的結(jié)果其實(shí)就是缺少的那個(gè)數(shù)

下面給出測(cè)試文件 test.cpp，代碼是用 C++ 實(shí)現(xiàn)的，可以自行用其他語言實(shí)現(xiàn)

#include <stdint.h> 
#include <iostream> 
using namespace std; 
 
int32_t find_missing(int32_t *ary, int32_t len) 
{ 
    //數(shù)組長(zhǎng)度小于等于1，直接返回 -1 
    if(len <= 1) 
    { 
        return -1; 
    } 
    //結(jié)果 
    int32_t result = 0; 
    //result 和 數(shù)組中每一個(gè)元素值進(jìn)行異或運(yùn)算 
    for (int32_t i = 0; i < len; i++) 
    { 
        result ^= ary[i]; 
    } 
    //result 和 0 到 n 中每一個(gè)值進(jìn)行異或運(yù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 命令編譯，接著運(yùn)行程序，結(jié)果如下：

[root@localhost test]# ./test  
result = 2 

當(dāng)然，這道題目還有其他的解法，比如：利用加法來解，大家自己去思考下，這里不做介紹了

題目鏈接 https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/

小結(jié)

通過上文，我們可以看到，異或運(yùn)算在很多方面都有應(yīng)用，其實(shí)，它的應(yīng)用遠(yuǎn)不止文中介紹的方面，所以，我們花時(shí)間去掌握它是非常值得做的一件事