摘要
- 實質運算意義上為一種特別的加法運算：
A XOR B = (A + B) mod 2 A XOR B，若 B = 1…1，則可視為針對 A 的各個 bits 做 toggle- 應用：
(1) 英文字母大小寫轉換
(2) 不使用暫存變數進行兩個變數的 swap
(3) Leetcode — Problem 136. Single Number 的解法
介紹
XOR，其全名為 exclusive or ~
下方是 XOR 的真值表
從中不難理解為何叫做 exclusive or：當遇到兩個 Input 不同時，其結果為 1 ；其餘情況都為 0 。
這樣的運算性質在程式上有些很特別的用法，如：
(1) 英文字母大小寫轉換
英文字母的大小寫其 ASCII Code 的數值差了 32 (e.g. ‘A’ + 32 = ‘a’, ‘a’ - 32 = ‘A’)，而 32 表示成二進位為 0010 0000。
只考慮單個位元的話，根據 XOR 的運算性質，一個位元 (記為 x) 與 1 做 XOR 的結果為對該 Bit 做 Toggle，因此大小寫的轉換可以透過這樣的方式達成
(2) 不用任何暫存變數，來交換 (Swap) 兩個變數的值
透過觀察 XOR 真值表的運算結果，考慮單一個 Bit，發現 XOR 結果為其差值 (不考慮正負號的話)。
故第一行 x ^= y可解釋成 x 為 x 與 y的差值，第二行 y ^= x 可解釋為 y 與 “x 與 y的差值” 的差值，也就是 8 ^ (5 ^ 8) 。
由於 XOR 有交換律、結合律的性質，故 8 ^ (5 ^ 8) = 8 ^ (8 ^ 5) = (8 ^ 8) ^ 5 = 0 ^ 5 = 5 。
所以這時候變數 y 已經變成 x 的值了，後面以此類推，可以讓變數 x 變成原本 y 的值。
(3) 給定一個 Array，在這些 Array 中的每個數字都會出現兩次，除了某一個數字只出現一次，請找出該數字。
同上，XOR 可解釋成計算兩個數的差值，假設 Array 中的數字依序是 A1, A2, A2, A3, A1，那麼 A1 ^ A2 ^ A2 ^ A3 ^ A1 根據交換律及結合律重新排列一下可以得到 A1 ^ A1 ^ A2 ^ A2 ^ A3 = (A1 ^ A1) ^ (A2 ^ A2) ^ A3 = 0 ^ 0 ^ A3 = A3 ，故可以得到唯一的數字。
XOR 運算的意義
若能針對 XOR 運算有以上的解釋 (Bit 的 Toggle & 差值的概念)，而非拘泥於真值表的計算結果，就會發現 XOR 並非這麼抽象。
不過更進一步分析，對數字敏感的人其實會發現，XOR 運算子是一種特殊的加法：
A XOR B = (A + B) mod 2
也就是說 A XOR B 的計算結果是 A + B 後，除以 2 得到的餘數
我們從這個角度出發來看待 XOR 運算，重新考慮上面的例子：
(1) 英文字母大小寫轉換
假設 ch 的 Binary Representation 為 abcdefgh，為了方便，我們記為 (a, b, c, d, e, f, g, h)。
ch ^ 32 =
(a, b, c, d, e, f, g, h) + (0, 0, 1, 0, 0, 0, 0, 0) mod 2 =
(a, b, (c + 1) mod 2, d, e, f, g, h)
因此整個計算結果，只會針對 c 這個位元會產生變化，若 c = 0，則結果為 (0 + 1) mod 2 = 1；反之，若 c = 1，則結果為 (1 + 1) mod 2 = 0。
透過這方式可以很簡單的理解為什麼 XOR 會有 Toggle 特定 Bit 的特性。
(2) 不用任何暫存變數，來交換 (Swap) 兩個變數的值
同理，假設 x = (a, b, c, d, e, f, g, h) 及 y = (i, j, k, l, m, n, o, p) 則x ^= y, y ^= x 可視為y = y ^ (x ^ y) =
(y + x + y) mod 2 =
(2i + a, 2j + b, 2k + c, 2l + d, 2m + e, 2n + f, 2o + g, 2p + h) mod 2 =
(a, b, c, d, e, f, g, h) = x 原本的值
第三個例子也是同樣的原理可以推得~
