XOR 消除法 | NatsuCamellia

在解題的時候，有人使用最標準的思路來解題，我們稱之為 Best Practice；但也有人用較為特殊的技巧或想法來快速解題，雖然這可能不是題目最先設計的用意，但是它卻能有效率的解決問題，當中也有一些值得學習的小技巧。

給予一個包含 n-1 個數字的陣列，範圍為 [1, n] ，所有數字都恰好出現一次，除了一個遺失的數字，請找出這個數字。

當然，我們有很多直觀的解法來解決這個問題，但是讓我們來看看 XOR 能如何巧妙地解決這道題目吧。

XOR

XOR 是一個用於位元的邏輯運算子，一般而言用 ^ 表示，如果兩個位元不同就回傳 1 ，反之則回傳 0。

x	y	x ^ y
0	0	0
0	1	1
1	0	1
1	1	0

許多的程式語言會將^實作成位元運算子，讓 XOR 能對每個位元進行運算，例如：

0011 ^ 1010 = 1001

因為：

0 ^ 1 = 1
0 ^ 0 = 0
1 ^ 1 = 0
1 ^ 0 = 1

因為有了這個特性，我們不只可以將 XOR 應用在布林值，我們甚至可以用在任何物件上。

關於 XOR 的特性

我們可以從先前的定義演繹出一些關於 XOR 的特性，我們先逐一了解這些特性，並接著使用它們來解決問題。

對 0 做 XOR： `x ^ 0 = x`

x	y	x ^ y
0	0	0
1	0	1

對自己做 XOR： `x ^ x = 0`

這個很直觀，根據定義，兩個一樣的位元做 XOR 會回傳 0。

x	y	x ^ y
0	0	0
1	1	0

交換律： `x ^ y = y ^ x`

XOR 滿足交換律，也就是說我們可以任意交換 XOR 的順序，因為我們是要比較兩個位元是否相異，順序不重要。要證明交換律成立很簡單，我們只要檢查 x ^ y 和 y ^ x 的 Truth table 就可以了。

x	y	x ^ y	y ^ x
0	0	0	0
0	1	1	1
1	0	1	1
1	1	0	0

XOR 運算的現象

結合以上幾個特性，我們可以得到一個非常有用的技巧：

XOR 消除法：如果我們有一連串的 XOR 運算 a ^ b ^ c ^ … ，我們可以消除每一對重複的數字，而不影響運算結果。

消除法的中心思想是：我們先運用交換律交換運算順序，再利用 x ^ x = 0 的性質來消除每一對重複的數字。

讓我們來看看一個例子：

  a ^ c ^ d ^ b ^ d ^ c ^ a
= a ^ a ^ c ^ c ^ d ^ d ^ b  // 交換律
= 0 ^ 0 ^ 0 ^ b              // x ^ x = 0
= b                          // x ^ 0 = x

並且因為 ^ 是位元運算子，這個技巧不管 a , b , c , d 是什麼資料型態都可以使用。

應用一：交換兩個數字

在解決找出遺失數字的問題前，我們先來看看這個問題

交換兩個數字，而不使用額外的變數。

這看起來有點棘手，但是我們可以透過 XOR 輕鬆完成：

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

看起來有點神奇對吧，但是它是真的可以辦到交換兩數的，我們透過拆解每個步驟，註解中表示每一行執行完之後 (x, y) 的值，來看看它到底是如何完成的：

x ^= y // (x ^ y, y)
y ^= x // (x ^ y, y ^ x ^ y) => (x ^ y, x)
x ^= y // (x ^ y ^ x, x) => (y, x)

我們可以發現，這其實只是使用我們先前導出的一些特性而已。

應用二：找出遺失的數字

我們終於要來解決一開始的題目了，我們重新來看看題目：

給予一個包含 n-1 個數字的陣列，範圍為 [1, n] ，所有數字都恰好出現一次，除了一個遺失的數字，請找出這個數字。

當然，我們有很多解法來解決這個問題，但是讓我們用學到的新玩具 XOR 來解決這道題目。

我們知道 XOR 可以消除重複出現的元素，但是如果我們只是對每個元素 XOR ，我們就沒辦法運用消除的這個特性，因為每個元素只出現最多一次。

a[0] ^ a[1] ^ ... ^ a[n-2]

請注意因為我們只有 n-1 個元素，所以最後一個索引值是 n-2

那該怎麼辦呢，如同前總統馬英九所說的：

一個便當吃不夠，你可以吃兩個。

所以呢？

一個元素 XOR 不夠，你可以 XOR 兩個。

讓我們也把 1 到 n XOR 進去：

1 ^ 2 ^ ... ^ n ^ a[0] ^ a[1] ^ ... ^ a[n-2]

我們會得到一個這樣的 XOR 序列：

給定的數字都會出現兩次：
- 其中一次在我們 XOR 進去的 1 到 n 之中。
- 另一次在給定的陣列中。
遺失的數字只會出現一次：
- 我們 XOR 進去的 1 到 n 之中。

如果我們把這些全部 XOR 起來，給定的數字會因為出現兩次而被消除，得益於 XOR 消除法；而遺失的數字只出現一次，不會被消除。也就是說結果會剩下遺失的數字，也就是題目所求的答案。

用程式碼表現，大概會像這個樣子：

public int findMissing(int[] array, int n) {
    int missing = 0;

    for (int i = 1; i <= n; i++) {
        missing ^= i;
    }

    for (int i : array) {
        missing ^= i;
    }

    return missing;
}

觀察這段程式碼，可能讓人不懂背後的演算法原理，但是我們知道了 XOR 消除法後，我們會發現其實是非常簡單的概念。但是我不推薦把這段程式碼拿給別人看，因為他會需要了解這個技巧才能知道這段程式碼的想法。

推廣至所有資料型態

我們也可以運用這個演算法在各種資料型態上，尋找缺失的元素，只要符合以下條件：

給定出現過的元素
給定所有元素

我們就能套用在任何一種資料型態上，例如：

我們有所有 Person 的集合，就可以找出缺失的 Person 。
我們有所有節點的集合，就可以找出缺失的節點。
就算不是連續整數，只要我們有所有整數的集合，和出現過的整數，我們就能找到缺失的整數。

練習：找出重複的數字

給予一個包含 n+1 個數字的陣列，範圍為 [1, n] ，所有數字都恰好出現一次，除了一個重複的數字出現了兩次，請找出這個數字。

XOR