【學習】雙交換值中的異或運算，這個概念是怎麼計算的呢？

雙交換值怎麼計算

大家比較熟悉的邏輯運算，主要是“與運算”（AND）和“或運算”（OR），還有一種“異或運算”（XOR），也非常重要。

本文介紹異或運算的含義和應用。

一、含義

XOR 是 exclusive OR 的縮寫。英語的 exclusive 意思是“專有的，獨有的”，可以理解為 XOR 是更單純的 OR 運算。

我們知道，OR 運算的運運算元有兩種情況，計算結果為

true

。

（1）一個為 true，另一個為 false；

（2）兩個都為 true。

上面兩種情況，有時候需要明確區分，所以引入了 XOR。

XOR 排除了第二種情況，只有第一種情況（一個運運算元為

true

，另一個為

false

）才會返回 true，所以可以看成是更單純的 OR 運算。也就是說，

XOR 主要用來判斷兩個值是否不同。

XOR 一般使用插入符號（caret）

^

表示。如果約定

0

為 false，

1

為 true，那麼 XOR 的運算真值表如下。

0 ^ 0 = 0

0 ^ 1 = 1

1 ^ 0 = 1

1 ^ 1 = 0

二、運算定律

XOR 運算有以下的運算定律。由於非常簡單，這裡就省略證明了。

（1）

一個值與自身的運算，總是為 false。

x ^ x = 0

（2）

一個值與 0 的運算，總是等於其本身。

x ^ 0 = x

（3）

可交換性

x ^ y = y ^ x

（4）

結合性

x ^ （y ^ z） = （x ^ y） ^ z

三、應用

根據上面的這些運算定律，可以得到異或運算的很多重要應用。

3.1 簡化計算

多個值的異或運算，可以根據運算定律進行簡化。

a ^ b ^ c ^ a ^ b

= a ^ a ^ b ^ b ^ c

= 0 ^ 0 ^ c

= c

3.2 交換值

兩個變數連續進行三次異或運算，可以互相交換值。

假設兩個變數是

x

和

y

，各自的值是

a

和

b

。下面就是

x

和

y

進行三次異或運算，註釋部分是每次運算後兩個變數的值。

x = x ^ y // （a ^ b， b）

y = x ^ y

// （a ^ b， a ^ b ^ b） => （a ^ b， a）

x = x ^ y

// (a ^ b ^ a, a) => (b, a)

這是兩個變數交換值的最快方法，不需要任何額外的空間。

3.3 加密

異或運算可以用於加密。

第一步，明文（text）與金鑰（key）進行異或運算，可以得到密文（cipherText）。

text ^ key = cipherText

第二步，密文與金鑰再次進行異或運算，就可以還原成明文。

cipherText ^ key = text

原理很簡單，如果明文是 x，金鑰是 y，那麼 x 連續與 y 進行兩次異或運算，得到自身。

（x ^ y） ^ y

= x ^ （y ^ y）

= x ^ 0

= x

3.4 資料備份

異或運算可以用於資料備份。

檔案 x 和檔案 y 進行異或運算，產生一個備份檔案 z。

x ^ y = z

以後，無論是檔案 x 或檔案 y 損壞，只要不是兩個原始檔案同時損壞，就能根據另一個檔案和備份檔案，進行還原。

x ^ z

= x ^ （x ^ y）

= （x ^ x） ^ y

= 0 ^ y

= y

上面的例子是 y 損壞，x 和 z 進行異或運算，就能得到 y。

四、一道面試題

一些面試的演算法題，也能使用異或運算快速求解。

請看下面這道題。

一個數組包含 n-1 個成員，這些成員是 1 到 n 之間的整數，且沒有重複，請找出缺少的那個數字。

最快的解答方法，就是把所有陣列成員（A［0］ 一直到 A［n-2］）與 1 到 n 的整數全部放在一起，進行異或運算。

A［0］ ^ A［1］ ^ 。。。 ^ A［n-2］ ^ 1 ^ 2 ^ 。。。 ^ n

上面這個式子中，每個陣列成員都會出現兩次，相同的值進行異或運算就會得到 0。只有缺少的那個數字出現一次，所以最後得到的就是這個值。

你可能想到了，加法也可以解這道題。

1 + 2 + 。。。 + n - A［0］ - A［1］ - 。。。 - A［n-2］

但是，加法的速度沒有異或運算快，而且需要額外的空間。如果數字比較大，還有溢位的可能。

下面是一道類似的題目，大家可以作為練習。

一個數組包含 n+1 個成員，這些成員是 1 到 n 之間的整數。只有一個成員出現了兩次，其他成員都只出現一次，請找出重複出現的那個數字。

五、參考連結

•That XOR Trick

［1］

（完）

引用連結

［1］

That XOR Trick：

https：//florian。github。io/xor-trick/