異或運算的巧用 → 不用額外的變數,如何交換兩個變數的值?

語言: CN / TW / HK

開心一刻

兩頭奶牛在一起吃草,其中一頭(奶牛甲)越吃越慢,一副若有所思的模樣,另一頭奶牛(奶牛乙)發覺了,開始了對話

奶牛乙:擱那合計啥呢?

奶牛甲:你幫我合計合計

奶牛乙:咋地了

奶牛甲:我吃的是草,擠出來的是奶,也就是說我把沒用的變成有用的了

奶牛乙:是這個事

奶牛甲:人呢,喝的是奶,拉出來的是粑粑

奶牛乙:咋地了

奶牛甲:他又把有用的變成沒用的了,我這不白乾了嗎

奶牛乙:你說的不對

奶牛甲:不對嗎?

奶牛乙:那粑粑做成化肥,有化肥才能長草,所以說你吃的不是草,是粑粑

奶牛乙:啊 ???

概念

關於“位”運算,大家或多或少都知道點,比如與運算(&)、或運算(|)、異或運算(^)、取反運算(~)、左移(<<)、右移(>>)

因為今天的主角是:異或運算,其他的位運算就不在本文展開了,大家自行去查閱

異或運算的英文名: exclusive OR ,簡稱  XOR ,那它是不是和或運算有什麼關係?

關於或運算,我們都比較清楚,只有當兩個位都是0時,結果才為0,其他情況結果都是1,也就是說或運算結果為 1 的情況兩種

(1)一個位是 1,另一個位是 0

(2)兩個位都是 1

有時候我們需要明確區分這兩種情況,怎麼辦?

所以引入了 XOR ,它排除了情況(2),只有情況(1),也就說:一個位是 1,另一個位是 0 時,  XOR 的結果才是 1,因此也可稱做 無進位相加

所以 XOR 可以看成是更單純的 OR 運算,正好對應了它的英文名:  exclusive OR 用來判斷兩個值是否不同(不同、不同、不同!!!)

XOR 的運算真值表

運算定律

我們學過的加法、乘法都有運算定律,異或運算也有它的運算定律

N ^ N = 0

N 表示任何值,也就是說:兩個相等的值做異或運算,得到的結果是 0

因為值相等,那麼值對應的各個位的值也是相等的,對應到 XOR 的運算真值表則是

我們來看個具體的例子:15 ^ 15

15 對應的二進位制位: 01111 ,那麼 15 ^ 15 的運算則是

N ^ 0 = 0

一個值與 0 做異或運算,得到的結果仍是這個值

例如:15 ^ 0 = 15

N ^ M = M ^ N

同加法有交換律、乘法也有交換律一樣,異或運算也有交換律

例如:15 ^ 8 = 8 ^ 15

(N ^ M) ^ Y = N ^ (M ^ Y)

同加法有結合律、乘法有結合律一樣,異或運算也結合律

例如:(15 ^ 8) ^ 3 = 15 ^ (8 ^ 3)

具體應用

前面講了那麼多理論,大家可能沒啥感覺,接下來我們就看看具體的案例,讓大家好好感覺感覺

不用額外的變數,交換兩個變數的值

樓主在以往的面試過程中,確確實實被面到過這個問題,關鍵是當時沒答上來

這個問題的考點就是 XOR

假設這兩個變數分別是 N(值為 5)、M(值為 6),通過三次 XOR 即可交換 N、M 的值

N = N ^ M// N = 5 ^ 6, M = 6

M = N ^ M// M = 5 ^ 6 ^ 6 = 5 ^ 0 = 5,N = 5 ^ 6

N = N ^ M// N = 5 ^ 6 ^ 5 = 6 ^ 0 = 6,M = 5

找出一串數字中唯一出現了奇數次的數字

問題詳細描述:已知一串數中,只有 1 個數字出現了奇數次,其他數字都出現了偶數次,如何快速找到這個奇數次的數字

如果沒有任何限制,解決方式有很多種,而最容易想到的往往是用 雜湊表

對這串數字從頭遍歷到尾, 逐個判斷該數字是否存在於 雜湊表 ,沒有存在則存入  雜湊表 ,存在了則從  雜湊表 中移除

最終 雜湊表 中剩下的那個數字就是出現了奇數次的數字

雜湊表 方案的時間複雜度是  O(N) ,額外空間複雜度也是  O(N)

假設加個限制:額外空間複雜度 O(1)

這時候就該 XOR 出馬了,我們結合  N ^ N = 0 、異或的交換律、異或的結合律,可推算出:這串數字全部進行異或運算,最終的結果就是出現了奇數次的那個數字

此時的額外空間複雜度是 O(1) ,只用到了兩個額外變數:  eor 、  cur

找出 1 至 n 中缺少的那個數

問題詳細描述:一串數字包含 n-1 個成員,這些數字是 1 到 n 之間的整數,且沒有重複,請找出缺少的那個數字

常規解法:從 1 累和到 n,然後再逐個減去這串數字

類似這樣 1 + 2 + ... + n - arr[0] - arr[1] - ... - arr[n-2]

時間複雜度 O(N) ,空間複雜度  O(1) ,似乎很完美

但是求和的過程存在溢位的風險,那怎麼辦? XOR 閃亮登場

我們將這串陣列與 1 至 n 的每個整數放在一起進行全部的異或運算

類似這樣 arr[0] ^ arr[1] ^ ... ^ arr[n-2] ^ 1 ^ 2 ^ ... ^ n

那麼得到的結果就是缺少的那個數

不存在溢位的風險,並且位運算比加、減運算更快

找出 1 至 n 中重複的那個數字

問題詳細描述:一串數字包含 n+1 個成員,這些數字是 1 到 n 之間的整數,只有一個數字出現了兩次,其他數字都只出現一次,請找出重複出現的那個數字

與問題: 找出 1 至 n 中缺少的那個數 解法一致

arr[0] ^ arr[1] ^ ... ^ arr[n] ^ 1 ^ 2 ^ ... ^ n

找出一串數字中出現了奇數次的那兩個數字

問題詳細描述:已知一串數中,有 2 個數字出現了奇數次,其他數字都出現了偶數次,如何快速找到那 2 個奇數次的數字

要求:時間複雜度 O(N) ,空間複雜度  O(1)

經過上面幾題的洗禮,我相信大家對 奇數次 、  偶數次 字眼已經產生了條件反射:用  XOR

我們對這串數字進行 XOR ,那麼得到的結果  eor = a ^ b ,a 和 b 就是那兩個出現了奇數次的數字

因為 a != b ,則  eor != 0 ,所以  eor 肯定有某一個二進位制位是 1

我們取 eor 二進位制最右邊的 1:  int rightOne = eor & (~eor + 1)

通過 rightOne 可以將數字串拆成兩部分: cur & rightOne = 0 和  cur & rightOne != 0

a、b 分別落在兩側,其他偶數個的數字只會落在某一側,整個數字串就被拆分成兩個 找出一串數字中唯一出現了奇數次的數字 的資料模型了

分別從兩側中找出奇數次的數字即可

完整程式碼如下

這個解法沒那麼好理解,大家好好琢磨琢磨

總結

1、 XOR 用來判斷同位上的值是否不同

2、 出現 奇數個 、  偶數個 、  缺失的 、  重複的 字眼,可以往  XOR 考慮

3、關於 不用額外的變數交換兩個變數的值,大家瞭解就好,不推薦使用

閱讀性差,另外相比臨時變數,它可能會出問題

4、示例程式碼地址

ExclusiveORTest

參考

That XOR Trick