真實世界的異或運算

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

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

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

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

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

因為我們在實際編程中，很難遇到這樣的場景：有一個數(shù)組，有 n - 1 個元素，其中恰好其中一個元素丟失了...

但在這篇文章中，你將看到，真實世界的異或運算是被怎樣應用的。

1.

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

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

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

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

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

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

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

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

x ^ x = 0

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

0 ^ y = y

當然，我們通過這個真值表，可以很輕易看出來，異或運算滿足交換律，即：

x ^ y = y ^ x

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

x ^ 0 = x

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

2.

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

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

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

寫成式子就是：

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

這個算法為什么是正確的？

因為在這個式子中，除了丟失的那個數(shù)字只出現(xiàn)了一次，其他數(shù)字都出現(xiàn)了兩次。

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

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

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

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

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

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

使用異或，則完全沒有這個問題。

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

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

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

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

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

這個算法為什么是正確的？

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

x ^ x ^ x = 0 ^ x = x

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

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

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

3.

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

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

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

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

而我們使用異或運算，完全可以不使用這個額外的臨時變量。只需要這樣就好：

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

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

初始的時候，x 里就是 x；y 里就是 y：

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

第二句話 y^=x，實際上，讓 y 和當下 x 里存放的值：x ^ y 進行了異或：

注意，此時，y 里有一個 x 和兩個 y 。兩個 y 異或的結果就是 0，所以，此時 y 里存放的是 x：

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

此時，x 里有兩個 x 和一個 y 。兩個 x 異或的結果就是 0。所以此時，x 里存放的是 y 的值：

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

4.

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

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

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

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

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

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

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

因為如果 x?和?y 的地址一樣，x?和?y 的值肯定也一樣，什么都不做，則避免了這個 bug；

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

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

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

因為在底層編程中，if?判斷也是比較耗費性能的，所以，一個更優(yōu)雅的寫法是這樣的（C / C++）：

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

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

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

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

值得一提的是，2009 年，Hallvard Furuseth 提出，下面的寫法性能更優(yōu)，因為表達式 x^y 可以被緩存重復利用：

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

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

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

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

5.

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

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

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

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

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

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

另一方面，在計算機底層，異或的一個重要的應用，是清零。

因為自己和自己異或的結果是零，所以，近乎所有的 CPU 指令中，清零操作都是使用異或完成的。

xor same, same

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

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

xor reg, reg

對于這個問題，在 stackoverflow 上有一個非常好的討論。感興趣的同學可以閱讀一下：

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.

真正讓異或運算大獲異彩的，其實是在密碼學領域，尤其是在對稱加密領域。

實際上，異或運算近乎被應用在了所有的對稱加密算法中。

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

比如說，我們有一個密文。這個密文就是 hi?吧。它所對應的二進制是：

01101000 01101001

下面，我們可以生成一個秘鑰。為了簡單起見，我們假設生成的秘鑰和密文是等長度的。比如密鑰是 66，對應的二進制是這樣的：

00110110 00110110

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

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

這個加密信息，對應的字符串是 ^_

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

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

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

如果有興趣的同學，可以搜索學習一下 DES（Data Encryption Standard） 和 AES（Advanced Encryption Standard），就會看到異或運算在其中所起的重要作用。

實際上，在編碼學領域，特別是各類糾錯碼和校驗碼，異或運算也經(jīng)常出現(xiàn)。

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

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

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

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

7.

最后，說一個我最喜歡的異或的應用。

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

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

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

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

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

在原文中，作者對相關的數(shù)據(jù)結構進行了代碼級別的定義。

實際上，這種數(shù)據(jù)結構的原理非常簡單。

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

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

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

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

我們之所以可以這么做，是因為對于雙向鏈表，所有的查詢操作，肯定是從頭到尾，或者從尾到頭進行的，而不可能直接從中間進行。也就是所謂的鏈表不支持隨機訪問。

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

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

我強烈建議感興趣的同學，自己動手編程實現(xiàn)一個異或雙向鏈表，是一個很有意思，也很酷的編程練習：）

8.

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

那就是，異或運算，為什么叫異或？這個名稱命名的來源，顯然和或運算（or）有一些關系，但是這個關系到底是什么？

答案是，異或運算可以表示成這樣：

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

右邊的式子也很好理解。因為異或運算就是 x 和 y 不同為真。

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

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

這兩種情況的任何一個，在異或的定義下，都是真。所以，這兩種情況，是或的關系。

看，異或這個概念就被這樣對應起來了：

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

是不是很酷？

大家加油?。海?/strong>