真實(shí)世界的異或運(yùn)算

對(duì)于底層開發(fā)來說，位運(yùn)算是非常重要的一類操作。而對(duì)于位運(yùn)算來說，最有意思的，應(yīng)該就是異或運(yùn)算（XOR）了。

提到異或運(yùn)算，很多同學(xué)可能首先想到的就是一個(gè)經(jīng)典的，和異或運(yùn)算相關(guān)的面試問題：

給你一個(gè)包含有 n - 1 個(gè)元素的數(shù)組，其中每個(gè)數(shù)字在 [1, n] 的范圍內(nèi)，且不重復(fù)。也就是從 1 到 n 這 n 個(gè)數(shù)字，有一個(gè)數(shù)字沒有出現(xiàn)在這個(gè)數(shù)組中。編寫一個(gè)算法，找到這個(gè)丟失的數(shù)字。

誠然，這樣的問題可以考察大家是否真正理解異或運(yùn)算，但其實(shí)這種問題沒什么意義。

是的，可能大家發(fā)現(xiàn)了，作為一個(gè)喜歡算法，經(jīng)常玩兒算法，每天在慕課網(wǎng)的課程問答區(qū)回答大家算法問題的老師，我卻經(jīng)常懟各種算法問題沒有什么意義...?

因?yàn)槲覀冊趯?shí)際編程中，很難遇到這樣的場景：有一個(gè)數(shù)組，有 n - 1 個(gè)元素，其中恰好其中一個(gè)元素丟失了...

但在這篇文章中，你將看到，真實(shí)世界的異或運(yùn)算是被怎樣應(yīng)用的。

1.

為了文章的完整性，我們先簡單來看一下，什么是異或運(yùn)算？

非常簡單：相同為 0，不同為 1。

大多數(shù)編程語言使用符號(hào) ^ 來表示異或運(yùn)算。

如果我們使用真值表來表示的話，異或運(yùn)算是這樣的：

在這里，大家可以仔細(xì)體會(huì)一下，什么叫相同為 0；不同為 1。

異或運(yùn)算真值表的第 1 行和第 4 行在說：相同為 0。

異或運(yùn)算真值表的第 2 行和第 3 行在說：不同為 1。

相同為 0，是異或運(yùn)算的最重要的性質(zhì)之一。即：

x ^ x = 0

而異或運(yùn)算最重要的性質(zhì)之二，可以通過這個(gè)真值表的前兩行看出來。就是 0 和任何一個(gè)數(shù)字（y）異或的結(jié)果，都是這個(gè)數(shù)字本身。即：

0 ^ y = y

當(dāng)然，我們通過這個(gè)真值表，可以很輕易看出來，異或運(yùn)算滿足交換律，即：

x ^ y = y ^ x

所以，上面的性質(zhì)，我們也可以說成是：任意一個(gè)數(shù)字(x)，和 0 異或的結(jié)果，還是這個(gè)數(shù)字本身。即：

x ^ 0 = x

好了，了解了異或運(yùn)算的這些性質(zhì)，我們就已經(jīng)完全可以理解絕大多數(shù)異或的應(yīng)用了。

2.

在具體看異或邏輯更加實(shí)際的應(yīng)用之前，我們還是先來簡單分析一下文章開始，那個(gè)經(jīng)典的面試問題，來做一做熱身。

給你一個(gè)包含有 n - 1 個(gè)元素的數(shù)組，其中每個(gè)數(shù)字在 [1, n] 的范圍內(nèi)，且不重復(fù)。也就是從 1 到 n 這 n 個(gè)數(shù)字，有一個(gè)數(shù)字沒有出現(xiàn)在這個(gè)數(shù)組中。編寫一個(gè)算法，找到這個(gè)丟失的數(shù)字。

如果使用異或解決的話，只需要首先計(jì)算出從 1 到 n 這 n 個(gè)數(shù)字的異或值，然后，再將數(shù)組中的所有元素依次和這個(gè)值做異或，最終得到的結(jié)果，就是這個(gè)丟失的數(shù)字。

寫成式子就是：

1 ^ 2 ^ 3 ^ ... ^ n ^ A[0] ^ A[1] ^ A[2] ^ ... ^ A[n - 2]

這個(gè)算法為什么是正確的？

因?yàn)樵谶@個(gè)式子中，除了丟失的那個(gè)數(shù)字只出現(xiàn)了一次，其他數(shù)字都出現(xiàn)了兩次。

所以，兩個(gè)相同的數(shù)字做異或，結(jié)果為 0；最終只出現(xiàn)一次的那個(gè)數(shù)字，和 0 做異或，結(jié)果就是這個(gè)丟失的數(shù)字。

值得一提的是，對(duì)于這個(gè)問題，我們完全可以不使用異或運(yùn)算，也設(shè)計(jì)出一個(gè)時(shí)間復(fù)雜度是 O(n)，空間復(fù)雜度是 O(1) 的算法。方法是，先計(jì)算出 1?到?n 的和，再用這個(gè)和，依次減去數(shù)組中的數(shù)字就好了。

而 1?到?n 的和，可以通過等差數(shù)列求和公式直接計(jì)算出：

(1 + n) * n / 2 - A[0] - A[1] - A[2] - ... - A[n - 2]

但是，這個(gè)方法有一個(gè)問題，就是如果 n 比較大的話，1?到?n 的數(shù)字和會(huì)超出整型范圍，導(dǎo)致整型溢出。

實(shí)際上，當(dāng) n 到達(dá) 7 萬這個(gè)規(guī)模的時(shí)候，1 到 n 的數(shù)字和就已經(jīng)不能使用 32 位 int 表示了。當(dāng)然，我們可以使用 long 來表示，但使用 long 做運(yùn)算，性能是比使用 int 慢的。

使用異或，則完全沒有這個(gè)問題。

這個(gè)經(jīng)典的面試問題，可以很容易地被改變成如下版本：

多余的數(shù)：給你一個(gè)包含有 n + 1 個(gè)元素的數(shù)組，其中每個(gè)數(shù)字在 [1, n] 的范圍內(nèi)，且 1 到 n 每個(gè)數(shù)字都會(huì)出現(xiàn)。也就是從 1 到 n 這 n 個(gè)數(shù)字，有一個(gè)數(shù)字在這個(gè)數(shù)組中出現(xiàn)了兩次。編寫一個(gè)算法，找到這個(gè)多余的數(shù)字。

相信理解了上面的問題，這個(gè)問題就很簡單了。答案是首先計(jì)算出從 1 到 n 這 n 個(gè)數(shù)字的異或值，然后，再將數(shù)組中的所有元素依次和這個(gè)值做異或，最終得到的結(jié)果，就是這個(gè)多余的數(shù)字。

是的，算法一模一樣。只不過現(xiàn)在，第二部分有 n + 1 個(gè)元素，而非 n - 1 個(gè)元素而已：

1 ^ 2 ^ 3 ^ ... ^ n ^ A[0] ^ A[1] ^ A[2] ^ ... ^ A[n]

這個(gè)算法為什么是正確的？

因?yàn)樵谶@個(gè)式子中，除了多余的那個(gè)數(shù)字出現(xiàn)了三次，其他數(shù)字都出現(xiàn)了兩次。所以，其他數(shù)字通過異或，結(jié)果都為 0，而一個(gè)數(shù)字和自己做 3 次異或運(yùn)算，結(jié)果還是它自己：

x ^ x ^ x = 0 ^ x = x

據(jù)此，我們可以非常簡單地得到結(jié)論：

一個(gè)數(shù)字和自己做偶數(shù)次異或運(yùn)算，結(jié)果為 0；

一個(gè)數(shù)字和自己做奇數(shù)次異或運(yùn)算，結(jié)果為 1。

3.

異或運(yùn)算最典型的一個(gè)應(yīng)用，是做兩個(gè)數(shù)字的交換。

傳統(tǒng)的兩個(gè)數(shù)字的交換，是使用這樣的三個(gè)賦值語句：

int t;x = t;x = y;y = t;

這樣做的問題是，需要一個(gè)額外的臨時(shí)變量 t。為一個(gè)新的變量開空間，是性能的損耗，哪怕這只是一個(gè) int 值而已。這一點(diǎn)，在高級(jí)編程語言中體現(xiàn)不出來，但是在底層開發(fā)中，就會(huì)有影響。

而我們使用異或運(yùn)算，完全可以不使用這個(gè)額外的臨時(shí)變量。只需要這樣就好：

x ^= y;y ^= x;x ^= y;

為了理解這個(gè)過程為什么是正確的，我們可以畫如下的示意圖：

初始的時(shí)候，x 里就是 x；y 里就是 y：

第一句話 x^=y，實(shí)際上，讓 x 里放的是 x ^ y：

第二句話 y^=x，實(shí)際上，讓 y 和當(dāng)下 x 里存放的值：x ^ y 進(jìn)行了異或：

注意，此時(shí)，y 里有一個(gè) x 和兩個(gè) y 。兩個(gè) y 異或的結(jié)果就是 0，所以，此時(shí) y 里存放的是 x：

最后，第三句話，再一次 x ^= y，但因?yàn)楝F(xiàn)在 x 里存放的是 x^y，y 里存放的是 x，所以，這句話以后，x 中是 (x^y)^x：

此時(shí)，x 里有兩個(gè) x 和一個(gè) y 。兩個(gè) x 異或的結(jié)果就是 0。所以此時(shí)，x 里存放的是 y 的值：

至此，x 和 y 的交換完成了。

4.

大多數(shù)資料關(guān)于使用異或運(yùn)算進(jìn)行兩個(gè)數(shù)字的交換，介紹到此，就結(jié)束了。而實(shí)際上，這個(gè)算法是有 bug 的。

這個(gè) bug 在 2005 年，第一次被 Iain A. Fleming 發(fā)現(xiàn)。

在上面的演示中，如果?x 和 y 是兩個(gè)不同的地址，才成立。

但如果?x 和 y 是同一個(gè)地址呢？比如，我們調(diào)用的是 swap(A[i], A[j])，其中?i == j。此時(shí)，上面的算法是錯(cuò)誤的。

因?yàn)?，在這種情況下，我們第一步做的 x ^= y，實(shí)際上就是 A[i] ^= A[i]。這將直接讓 A[i] 中的元素等于 0，而丟失原本存在 A[i] 中的元素。后續(xù)，這個(gè)元素就再也找不回來了。

針對(duì)這個(gè) bug，解決方案是，在做這個(gè)交換之前，判斷一下 x 和 y 的地址是否相同。

由于在一些語言中，拿到變量的地址并不容易（甚至沒有這個(gè)能力），所以，可以把邏輯改變?yōu)椋袛嘁幌?x?和?y 是否相同。如果相同，則什么都不做。

因?yàn)槿绻?x?和?y 的地址一樣，x?和?y 的值肯定也一樣，什么都不做，則避免了這個(gè) bug；

即便 x?和?y 的地址不一樣，但如果 x?和?y 的值相同，什么都不做也是正確的。

所以，我們的邏輯變成了這樣：

if(x != y){        x ^= y;        y ^= x;        x ^= y;}

因?yàn)樵诘讓泳幊讨校?/span>if?判斷也是比較耗費(fèi)性能的，所以，一個(gè)更優(yōu)雅的寫法是這樣的（C / C++）：

(x == y) || ((x ^= y), (y ^= x), (x ^= y))

在這個(gè)寫法中，巧妙地使用了邏輯短路，如果第一個(gè)表達(dá)式 x == y?成立，后面的交換過程就不會(huì)被執(zhí)行了；否則，運(yùn)行后面的交換邏輯。

這樣寫，整個(gè)邏輯中沒有了 if 判斷。

在極端情況下，即使在高級(jí)語言編程中，沒有 if 運(yùn)算也將大大提升程序性能?？梢詤⒖嘉抑暗奈恼拢?/span>用簡單的代碼，看懂 CPU 背后的重要機(jī)制

值得一提的是，2009 年，Hallvard Furuseth 提出，下面的寫法性能更優(yōu)，因?yàn)楸磉_(dá)式 x^y 可以被緩存重復(fù)利用：

(x ^ y) && (y ^= x ^= y, x ^= y)

在 2007 年和 2008 年，Sanjeev Sivasankaran 和 Vincent Lefèvre 提出，這個(gè)交換過程也可以使用加減運(yùn)算完成：

(&a == &b) || ((a -= b), (b += a), (a = b - a))

篇幅原因，在這里，我就不對(duì)這個(gè)邏輯做模擬了。感興趣的同學(xué)，可以使用文章中的方法，自行模擬，驗(yàn)證這個(gè)算法的正確性：）

5.

異或運(yùn)算的另一個(gè)直接應(yīng)用，是編譯器的優(yōu)化，或者是 CPU 底層的優(yōu)化。

舉個(gè)簡單的例子，在很多編譯器的內(nèi)部，判斷?if(x != y)

本質(zhì)是在判斷：if((x ^ y) != 0)

很多同學(xué)可能會(huì)從數(shù)學(xué)的角度，認(rèn)為判斷 x 是否等于 y，是看 x - y 的結(jié)果是否為 0。

但實(shí)際上，減法是一個(gè)比異或操作復(fù)雜得多的操作。如果學(xué)習(xí)過數(shù)字電路的同學(xué)會(huì)知道，設(shè)計(jì)一個(gè)減法器，并不容易。

但是，兩個(gè)數(shù)字按位異或，就非常容易了。

另一方面，在計(jì)算機(jī)底層，異或的一個(gè)重要的應(yīng)用，是清零。

因?yàn)樽约汉妥约寒惢虻慕Y(jié)果是零，所以，近乎所有的 CPU 指令中，清零操作都是使用異或完成的。

xor same, same

還記得之前說的，兩個(gè)元素交換的 bug 嗎？這個(gè) bug 的本質(zhì)，就是當(dāng)兩個(gè)元素的地址一樣的時(shí)候，相當(dāng)于對(duì)這個(gè)地址做清零了。

當(dāng)然，從體系結(jié)構(gòu)的角度，這個(gè)清零不僅僅可以發(fā)生在內(nèi)存，也可以發(fā)生在寄存器。

xor reg, reg

對(duì)于這個(gè)問題，在 stackoverflow 上有一個(gè)非常好的討論。感興趣的同學(xué)可以閱讀一下：

https://stackoverflow.com/questions/33666617/what-is-the-best-way-to-set-a-register-to-zero-in-x86-assembly-xor-mov-or-and

What is the best way to set a register to zero in x86 assembly: xor, mov or and?

6.

真正讓異或運(yùn)算大獲異彩的，其實(shí)是在密碼學(xué)領(lǐng)域，尤其是在對(duì)稱加密領(lǐng)域。

實(shí)際上，異或運(yùn)算近乎被應(yīng)用在了所有的對(duì)稱加密算法中。

系統(tǒng)地講解密碼學(xué)已經(jīng)遠(yuǎn)超這篇文章的范疇了。在這里，我只給出一個(gè)簡單的例子，讓大家可以直觀地理解，為什么異或運(yùn)算可以用在對(duì)稱加密算法中。

比如說，我們有一個(gè)密文。這個(gè)密文就是 hi?吧。它所對(duì)應(yīng)的二進(jìn)制是：

01101000 01101001

下面，我們可以生成一個(gè)秘鑰。為了簡單起見，我們假設(shè)生成的秘鑰和密文是等長度的。比如密鑰是 66，對(duì)應(yīng)的二進(jìn)制是這樣的：

00110110 00110110

那么，我們將密文和秘鑰做異或操作，得到的結(jié)果，就是加密后的信息：

01101000 01101001 (密文)異或00110110 00110110 (秘鑰)=01011110 01011111 (加密信息)

這個(gè)加密信息，對(duì)應(yīng)的字符串是 ^_

這個(gè)字符串顯然沒有意義。但是，如果你知道秘鑰 66?的話，將這個(gè)加密信息和秘鑰 66?再做異或運(yùn)算，就可以恢復(fù)原先的密文 hi。

相信看到這里，這背后的原理，大家都已經(jīng)了解了。是異或運(yùn)算性質(zhì)最基本的應(yīng)用，其實(shí)非常簡單。

當(dāng)然，生產(chǎn)環(huán)境的對(duì)稱加密沒有這么簡單，但這是最基礎(chǔ)的原理。

如果有興趣的同學(xué)，可以搜索學(xué)習(xí)一下 DES（Data Encryption Standard） 和 AES（Advanced Encryption Standard），就會(huì)看到異或運(yùn)算在其中所起的重要作用。

實(shí)際上，在編碼學(xué)領(lǐng)域，特別是各類糾錯(cuò)碼和校驗(yàn)碼，異或運(yùn)算也經(jīng)常出現(xiàn)。

比如奇偶校驗(yàn)，比如 CRC 校驗(yàn)，比如 MD5 或者 SHA256，比如 Hadamard 編碼或者 Gray 碼（格雷碼）。

格雷碼可能很多同學(xué)都聽說過，一般在離散數(shù)學(xué)或者組合數(shù)學(xué)中會(huì)接觸。

最近力扣有一次周賽的問題，本質(zhì)其實(shí)是格雷碼和對(duì)應(yīng)二進(jìn)制數(shù)字之間的轉(zhuǎn)換，有興趣的同學(xué)可以了解一下：

如果明白格雷碼的原理，這個(gè) Hard 問題就是 Easy 問題，一通異或運(yùn)算就解決了?

7.

最后，說一個(gè)我最喜歡的異或的應(yīng)用。

使用異或，可以編寫更加節(jié)省空間的雙向鏈表，被稱為是異或雙向鏈表（XOR linked list）。

在維基百科中，專門收錄了這個(gè)詞條：

這種雙向鏈表，由 Prokash Sinha 在 2004 年第一次提出，并且發(fā)表在了 Linux Journal 上。被稱為是：A Memory-Efficient Doubly Linked List（一種更有效利用空間的雙向鏈表）。

感興趣的同學(xué)，可以在這里閱讀這篇文章：

https://www.linuxjournal.com/article/6828

在原文中，作者對(duì)相關(guān)的數(shù)據(jù)結(jié)構(gòu)進(jìn)行了代碼級(jí)別的定義。

實(shí)際上，這種數(shù)據(jù)結(jié)構(gòu)的原理非常簡單。

在通常的雙向鏈表中，每一個(gè)節(jié)點(diǎn)需要有兩個(gè)指針，一個(gè) prev，指向之前的節(jié)點(diǎn)；一個(gè) next，指向之后的節(jié)點(diǎn)。

但是，異或雙向鏈表中，只有一個(gè)指針，我們可以管它叫 xor_ptr。這個(gè)指針指向的地址，是 prev 和 next 兩個(gè)地址異或的結(jié)果。其中，頭結(jié)點(diǎn)的 prev 地址取 0；尾結(jié)點(diǎn)的 next 地址取 0。

這樣一來，如果我們需要獲得一個(gè)節(jié)點(diǎn)的 next 的地址，只需要 xor_ptr ^ prev 就好；

如果我們需要獲得一個(gè)節(jié)點(diǎn)的 prev 的地址，只需要 xor_ptr ^ next 就好。

我們之所以可以這么做，是因?yàn)閷?duì)于雙向鏈表，所有的查詢操作，肯定是從頭到尾，或者從尾到頭進(jìn)行的，而不可能直接從中間進(jìn)行。也就是所謂的鏈表不支持隨機(jī)訪問。

因此，在我們遍歷異或雙向鏈表的過程中，如果我們是從頭到尾遍歷的話，我們就可以一直跟蹤每一個(gè)節(jié)點(diǎn)的?prev??值。用這個(gè)值和?xor_ptr 做異或操作，拿到每一個(gè)節(jié)點(diǎn)的 next；

同理，如果我們是從尾到頭遍歷的話，我們就可以一直跟蹤每一個(gè)節(jié)點(diǎn)的 next 值。用這個(gè)值和?xor_ptr 做異或操作，就可以拿到每一個(gè)節(jié)點(diǎn)的 prev 。

我強(qiáng)烈建議感興趣的同學(xué)，自己動(dòng)手編程實(shí)現(xiàn)一個(gè)異或雙向鏈表，是一個(gè)很有意思，也很酷的編程練習(xí)：）

8.

文章的最后，聊一個(gè)我第一次接觸異或運(yùn)算，產(chǎn)生的疑問，相信很多同學(xué)都有。

那就是，異或運(yùn)算，為什么叫異或？這個(gè)名稱命名的來源，顯然和或運(yùn)算（or）有一些關(guān)系，但是這個(gè)關(guān)系到底是什么？

答案是，異或運(yùn)算可以表示成這樣：

x ^ y = (!x and y)? or (x and !y)

右邊的式子也很好理解。因?yàn)楫惢蜻\(yùn)算就是 x 和 y 不同為真。

所以，!x and y 表示 x?和?y 不同，其中 x 為 0，y 為 1；

x and !y 也表示 x?和?y 不同，其中 x 為 1，y 為 0；

這兩種情況的任何一個(gè)，在異或的定義下，都是真。所以，這兩種情況，是或的關(guān)系。

看，異或這個(gè)概念就被這樣對(duì)應(yīng)起來了：

異，就是 x?和?y 不同；或，就是這兩種情況取或的關(guān)系。

是不是很酷？

大家加油?。海?/strong>