對于底層開發來說，位運算是非常重要的一類操作。而對于位運算來說，最有意思的，應該就是異或運算（XOR）了。
提到異或運算，很多同學可能首先想到的就是一個經典的，和異或運算相關的面試問題：
給你一個包含有 n - 1 個元素的數組，其中每個數字在 [1, n] 的範圍内，且不重複。也就是從 1 到 n 這 n 個數字，有一個數字沒有出現在這個數組中。編寫一個算法，找到這個丢失的數字。
誠然，這樣的問題可以考察大家是否真正了解異或運算，但其實這種問題沒什麼意義。
是的，可能大家發現了，作為一個喜歡算法，經常玩兒算法，每天在慕課網的課程問答區回答大家算法問題的老師，我卻經常怼各種算法問題沒有什麼意義...
因為我們在實際程式設計中，很難遇到這樣的場景：有一個數組，有 n - 1 個元素，其中恰好其中一個元素丢失了...
但在這篇文章中，你将看到，真實世界的異或運算是被怎樣應用的。
1.
為了文章的完整性，我們先簡單來看一下，什麼是異或運算？
非常簡單：相同為 0，不同為 1。
大多數程式設計語言使用符号 ^ 來表示異或運算。
如果我們使用真值表來表示的話，異或運算是這樣的：
在這裡，大家可以仔細體會一下，什麼叫相同為 0；不同為 1。
異或運算真值表的第 1 行和第 4 行在說：相同為 0。
異或運算真值表的第 2 行和第 3 行在說：不同為 1。
相同為 0，是異或運算的最重要的性質之一。即：
x ^ x = 0
而異或運算最重要的性質之二，可以通過這個真值表的前兩行看出來。就是 0 和任何一個數字（y）異或的結果，都是這個數字本身。即：
0 ^ y = y
當然，我們通過這個真值表，可以很輕易看出來，異或運算滿足交換律，即：
x ^ y = y ^ x
是以，上面的性質，我們也可以說成是：任意一個數字(x)，和 0 異或的結果，還是這個數字本身。即：
x ^ 0 = x
好了，了解了異或運算的這些性質，我們就已經完全可以了解絕大多數異或的應用了。
2.
在具體看異或邏輯更加實際的應用之前，我們還是先來簡單分析一下文章開始，那個經典的面試問題，來做一做熱身。
給你一個包含有 n - 1 個元素的數組，其中每個數字在 [1, n] 的範圍内，且不重複。也就是從 1 到 n 這 n 個數字，有一個數字沒有出現在這個數組中。編寫一個算法，找到這個丢失的數字。
如果使用異或解決的話，隻需要首先計算出從 1 到 n 這 n 個數字的異或值，然後，再将數組中的所有元素依次和這個值做異或，最終得到的結果，就是這個丢失的數字。
寫成式子就是：
1 ^ 2 ^ 3 ^ ... ^ n ^ A[0] ^ A[1] ^ A[2] ^ ... ^ A[n - 2]
這個算法為什麼是正确的？
因為在這個式子中，除了丢失的那個數字隻出現了一次，其他數字都出現了兩次。
是以，兩個相同的數字做異或，結果為 0；最終隻出現一次的那個數字，和 0 做異或，結果就是這個丢失的數字。
值得一提的是，對于這個問題，我們完全可以不使用異或運算，也設計出一個時間複雜度是 O(n)，空間複雜度是 O(1) 的算法。方法是，先計算出 1 到 n 的和，再用這個和，依次減去數組中的數字就好了。
而 1 到 n 的和，可以通過等差數列求和公式直接計算出：
(1 + n) * n / 2 - A[0] - A[1] - A[2] - ... - A[n - 2]
但是，這個方法有一個問題，就是如果 n 比較大的話，1 到 n 的數字和會超出整型範圍，導緻整型溢出。
實際上，當 n 到達 7 萬這個規模的時候，1 到 n 的數字和就已經不能使用 32 位 int 表示了。當然，我們可以使用 long 來表示，但使用 long 做運算，性能是比使用 int 慢的。
使用異或，則完全沒有這個問題。
這個經典的面試問題，可以很容易地被改變成如下版本：
多餘的數：給你一個包含有 n + 1 個元素的數組，其中每個數字在 [1, n] 的範圍内，且 1 到 n 每個數字都會出現。也就是從 1 到 n 這 n 個數字，有一個數字在這個數組中出現了兩次。編寫一個算法，找到這個多餘的數字。
相信了解了上面的問題，這個問題就很簡單了。答案是首先計算出從 1 到 n 這 n 個數字的異或值，然後，再将數組中的所有元素依次和這個值做異或，最終得到的結果，就是這個多餘的數字。
是的，算法一模一樣。隻不過現在，第二部分有 n + 1 個元素，而非 n - 1 個元素而已：
1 ^ 2 ^ 3 ^ ... ^ n ^ A[0] ^ A[1] ^ A[2] ^ ... ^ A[n]
這個算法為什麼是正确的？
因為在這個式子中，除了多餘的那個數字出現了三次，其他數字都出現了兩次。是以，其他數字通過異或，結果都為 0，而一個數字和自己做 3 次異或運算，結果還是它自己：
x ^ x ^ x = 0 ^ x = x
據此，我們可以非常簡單地得到結論：
一個數字和自己做偶數次異或運算，結果為 0；
一個數字和自己做奇數次異或運算，結果為 1。
3.
異或運算最典型的一個應用，是做兩個數字的交換。
傳統的兩個數字的交換，是使用這樣的三個指派語句：
int t;x = t;x = y;y = t; 這樣做的問題是，需要一個額外的臨時變量 t。為一個新的變量開空間，是性能的損耗，哪怕這隻是一個 int 值而已。這一點，在進階程式設計語言中展現不出來，但是在底層開發中，就會有影響。
而我們使用異或運算，完全可以不使用這個額外的臨時變量。隻需要這樣就好：
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，但因為現在 x 裡存放的是 x^y，y 裡存放的是 x，是以，這句話以後，x 中是 (x^y)^x：
此時，x 裡有兩個 x 和一個 y 。兩個 x 異或的結果就是 0。是以此時，x 裡存放的是 y 的值：
至此，x 和 y 的交換完成了。
4.
大多數資料關于使用異或運算進行兩個數字的交換，介紹到此，就結束了。而實際上，這個算法是有 bug 的。
這個 bug 在 2005 年，第一次被 Iain A. Fleming 發現。
在上面的示範中，如果 x 和 y 是兩個不同的位址，才成立。
但如果 x 和 y 是同一個位址呢？比如，我們調用的是 swap(A[i], A[j])，其中 i == j。此時，上面的算法是錯誤的。
因為，在這種情況下，我們第一步做的 x ^= y，實際上就是 A[i] ^= A[i]。這将直接讓 A[i] 中的元素等于 0，而丢失原本存在 A[i] 中的元素。後續，這個元素就再也找不回來了。
針對這個 bug，解決方案是，在做這個交換之前，判斷一下 x 和 y 的位址是否相同。
由于在一些語言中，拿到變量的位址并不容易（甚至沒有這個能力），是以，可以把邏輯改變為，判斷一下 x 和 y 是否相同。如果相同，則什麼都不做。
因為如果 x 和 y 的位址一樣，x 和 y 的值肯定也一樣，什麼都不做，則避免了這個 bug；
即便 x 和 y 的位址不一樣，但如果 x 和 y 的值相同，什麼都不做也是正确的。
是以，我們的邏輯變成了這樣：
if(x != y){
x ^= y;
y ^= x;
x ^= y;
} 因為在底層程式設計中，if 判斷也是比較耗費性能的，是以，一個更優雅的寫法是這樣的（C / C++）：
(x == y) || ((x ^= y), (y ^= x), (x ^= y)) 在這個寫法中，巧妙地使用了邏輯短路，如果第一個表達式 x == y 成立，後面的交換過程就不會被執行了；否則，運作後面的交換邏輯。
這樣寫，整個邏輯中沒有了 if 判斷。
在極端情況下，即使在進階語言程式設計中，沒有 if 運算也将大大提升程式性能。可以參考我之前的文章：用簡單的代碼，看懂 CPU 背後的重要機制
值得一提的是，2009 年，Hallvard Furuseth 提出，下面的寫法性能更優，因為表達式 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.
異或運算的另一個直接應用，是編譯器的優化，或者是 CPU 底層的優化。
舉個簡單的例子，在很多編譯器的内部，判斷 if(x != y)
本質是在判斷：if((x ^ y) != 0)
很多同學可能會從數學的角度，認為判斷 x 是否等于 y，是看 x - y 的結果是否為 0。
但實際上，減法是一個比異或操作複雜得多的操作。如果學習過數字電路的同學會知道，設計一個減法器，并不容易。
但是，兩個數字按位異或，就非常容易了。
另一方面，在計算機底層，異或的一個重要的應用，是清零。
因為自己和自己異或的結果是零，是以，近乎所有的 CPU 指令中，清零操作都是使用異或完成的。
xor same, same 還記得之前說的，兩個元素交換的 bug 嗎？這個 bug 的本質，就是當兩個元素的位址一樣的時候，相當于對這個位址做清零了。
當然，從體系結構的角度，這個清零不僅僅可以發生在記憶體，也可以發生在寄存器。
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.
真正讓異或運算大獲異彩的，其實是在密碼學領域，尤其是在對稱加密領域。
實際上，異或運算近乎被應用在了所有的對稱加密算法中。
系統地講解密碼學已經遠超這篇文章的範疇了。在這裡，我隻給出一個簡單的例子，讓大家可以直覺地了解，為什麼異或運算可以用在對稱加密算法中。
比如說，我們有一個密文。這個密文就是 hi 吧。它所對應的二進制是：
01101000 01101001 下面，我們可以生成一個秘鑰。為了簡單起見，我們假設生成的秘鑰和密文是等長度的。比如密鑰是 66，對應的二進制是這樣的：
00110110 00110110 那麼，我們将密文和秘鑰做異或操作，得到的結果，就是加密後的資訊：
01101000 01101001 (密文)異或00110110 00110110 (秘鑰)=01011110 01011111 (加密資訊) 這個加密資訊，對應的字元串是 ^_
這個字元串顯然沒有意義。但是，如果你知道秘鑰 66 的話，将這個加密資訊和秘鑰 66 再做異或運算，就可以恢複原先的密文 hi。
相信看到這裡，這背後的原理，大家都已經了解了。是異或運算性質最基本的應用，其實非常簡單。
當然，生産環境的對稱加密沒有這麼簡單，但這是最基礎的原理。
如果有興趣的同學，可以搜尋學習一下 DES（Data Encryption Standard） 和 AES（Advanced Encryption Standard），就會看到異或運算在其中所起的重要作用。
實際上，在編碼學領域，特别是各類糾錯碼和校驗碼，異或運算也經常出現。
比如奇偶校驗，比如 CRC 校驗，比如 MD5 或者 SHA256，比如 Hadamard 編碼或者 Gray 碼（格雷碼）。
格雷碼可能很多同學都聽說過，一般在離散數學或者組合數學中會接觸。
最近力扣有一次周賽的問題，本質其實是格雷碼和對應二進制數字之間的轉換，有興趣的同學可以了解一下：
如果明白格雷碼的原理，這個 Hard 問題就是 Easy 問題，一通異或運算就解決了
7.
最後，說一個我最喜歡的異或的應用。
使用異或，可以編寫更加節省空間的雙向連結清單，被稱為是異或雙向連結清單（XOR linked list）。
在維基百科中，專門收錄了這個詞條：
這種雙向連結清單，由 Prokash Sinha 在 2004 年第一次提出，并且發表在了 Linux Journal 上。被稱為是：A Memory-Efficient Doubly Linked List（一種更有效利用空間的雙向連結清單）。
感興趣的同學，可以在這裡閱讀這篇文章：
https://www.linuxjournal.com/article/6828
在原文中，作者對相關的資料結構進行了代碼級别的定義。
實際上，這種資料結構的原理非常簡單。
在通常的雙向連結清單中，每一個節點需要有兩個指針，一個 prev，指向之前的節點；一個 next，指向之後的節點。
但是，異或雙向連結清單中，隻有一個指針，我們可以管它叫 xor_ptr。這個指針指向的位址，是 prev 和 next 兩個位址異或的結果。其中，頭結點的 prev 位址取 0；尾結點的 next 位址取 0。
這樣一來，如果我們需要獲得一個節點的 next 的位址，隻需要 xor_ptr ^ prev 就好；
如果我們需要獲得一個節點的 prev 的位址，隻需要 xor_ptr ^ next 就好。
我們之是以可以這麼做，是因為對于雙向連結清單，所有的查詢操作，肯定是從頭到尾，或者從尾到頭進行的，而不可能直接從中間進行。也就是所謂的連結清單不支援随機通路。
是以，在我們周遊異或雙向連結清單的過程中，如果我們是從頭到尾周遊的話，我們就可以一直跟蹤每一個節點的 prev 值。用這個值和 xor_ptr 做異或操作，拿到每一個節點的 next；
同理，如果我們是從尾到頭周遊的話，我們就可以一直跟蹤每一個節點的 next 值。用這個值和 xor_ptr 做異或操作，就可以拿到每一個節點的 prev 。
我強烈建議感興趣的同學，自己動手程式設計實作一個異或雙向連結清單，是一個很有意思，也很酷的程式設計練習：）
8.
文章的最後，聊一個我第一次接觸異或運算，産生的疑問，相信很多同學都有。
那就是，異或運算，為什麼叫異或？這個名稱命名的來源，顯然和或運算（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 不同；或，就是這兩種情況取或的關系。
是不是很酷？
大家加油！：）