今天要來介紹一下 XOR ,首先還是要先說明一下今天為什麼介紹XOR呢?因為某日我得到了一個題目是這樣子的
某個未排序陣列裡面所有數字都程度出現,但有一個數字不是,請找出孤單的那個數字。
[2, 3, 1, 2, 3] → 1
[2, 3, 2, 3, 2] → 2
看到題目的當下第一個想法是使用兩層迴圈,算出答案。但是就這樣了嗎?其實還有更便易的解法,只要使用一層迴圈就可以得到答案,但是這個解法還需要依靠XOR才能完成。
先來介紹一下 XOR的特性,當條件1及條件2成立時,會回傳false,簡單來說就是當兩個條件都成立的時候,會被判斷成沒有符合的條件。可以參考下表比較好了解!
2022/12/30更新:很抱歉之前製作的表格內容錯誤,文章發表後沒有再次檢查刊登的內容,已將表格更新,感謝留言提醒的各位,日後寫文時,會再多注意內容是否正確再發佈文章。
那介紹完XOR之後就要開始來解題了!
function findSingleValue(array) {
var result = array[0];
for (var i = 1; i < array.length; i++) {
result = result ^ array[i];
}
}
當我擁有一個array是 [2, 3, 1, 2, 3] 的時候,我將此array丟進findSingleValue時,就會開始進行運算了。現在就模擬2進位的方式來處理這個array吧!
2 → 010
3 → 011
1 → 001
2 → 010
3 → 011
按照程式的邏輯
001 = 010 ^ 011
000 = 001 ^ 001
010 = 000 ^ 010
001 = 010 ^ 011
最後我們得到了001,再將這個2進位轉換回10進位就會得到1,就是正確答案了!其實我一開始在這邊犯了一個錯誤,就是我在思考的時候,忘了將10進位轉換為2進位,所以一直使用2 ^ 3 ^ 1 ^ 2 ^ 3的方式計算,還一直想說到底要怎麼使用XOR才能得到正確答案!以上就是XOR的介紹,其實只要記住一點,當兩個條件中有一個條件不成立時,就等於條件成立了,就能很簡單運用XOR了!
感謝 WanCW 補充XOR 的說明:
0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0
從上述可以發現:
1. xor 符合交換律 a^b == b^a
2. 0^a 永遠是 a
3. a^a 永遠是 0
因為 1. 所以... ^a...^a... == ...^a^a
因為 3. 所以 ...^a...^a... == ...^a^a == ...^0
因為 2. 所以 …^a…^a… == …^a^a == …^0 = 落單的 x
— — — —
白話版
1.x^y == y^x → xor 運算可以隨意換順序
2.x^x == 0 / → 相同的數字 xor 會剩下 0
3.x^0 == x → 任何數字跟 0 xor 還是同一個數字
所以,a^b^c^d…… 中,
因為 1. 我們可以把先算成對的數字、
因為 2. 成對的結果一定是 0 → 剩下一堆 0、
因為 3. 0 可以直接拿掉不管 → 剩下不成對的數字