Go：異或運(yùn)算的妙用

概述

異或運(yùn)算 通過(guò)對(duì)兩個(gè)相同長(zhǎng)度的二進(jìn)制數(shù)進(jìn)行逐位比較，若對(duì)應(yīng)位的值不同，結(jié)果為 1, 否則結(jié)果為 0, Go 語(yǔ)言中使用的運(yùn)算符號(hào)為 ^。

下面舉幾個(gè)簡(jiǎn)單的小例子:

0 ^ 0 = 0

0 ^ 1 = 1

1 ^ 0 = 1

1 ^ 1 = 0

運(yùn)算定律

交換律

x ^ y = y ^ x

結(jié)合律

x ^ (y ^ z) = (x ^ y) ^ z

任何數(shù)與自身進(jìn)行異或運(yùn)算，結(jié)果都為 0

x ^ x = 0

任何數(shù)與 0 進(jìn)行異或運(yùn)算, 結(jié)果為其自身

x ^ 0 = x

有了上面的理論基礎(chǔ)之后，下面來(lái)看下異或運(yùn)算的幾個(gè)應(yīng)用。

交換兩個(gè)變量的值

有個(gè)經(jīng)典的筆試題：交換兩個(gè)變量的值，不能使用第三個(gè)變量。

解法一

利用 Go 語(yǔ)言的原生 “騷操作” :

package main

import "fmt"

func main() {
 x, y := 1, 2
 
 x, y = y, x

 fmt.Printf("x = %d, y = %d\n", x, y) 
 // 輸出: x = 2, y = 1
}

當(dāng)然了，如果在真實(shí)面試中這樣寫，只能回去等消息了。

解法二

利用加法分配率

package main

import "fmt"

func main() {
 x, y := 1, 2

 x += y    // x = 3
 y = x - y // y = 1
 x -= y    // x = 2

 fmt.Printf("x = %d, y = %d\n", x, y)
 // 輸出: x = 2, y = 1
}

解法三

異或運(yùn)算性質(zhì): 三個(gè)值中的任意兩個(gè)值進(jìn)行異或運(yùn)算，都可以得出第三個(gè)值。

package main

import "fmt"

func main() {
 x, y := 1, 2

 x ^= y    // x = 3
 y = x ^ y // y = 1
 x ^= y    // x = 2

 fmt.Printf("x = %d, y = %d\n", x, y)
 // 輸出: x = 2, y = 1
}

加密解密

異或運(yùn)算可以實(shí)現(xiàn)簡(jiǎn)單高效的加密解密，例如:

• 明文數(shù)據(jù)為 text
• 密鑰為 secret
• 密文數(shù)據(jù)為 token

# 服務(wù)端響應(yīng)時(shí)，返回加密數(shù)據(jù)

token = text ^ secret

# 服務(wù)端接收到請(qǐng)求時(shí)，解密數(shù)據(jù)

text = token ^ secret

這個(gè)經(jīng)典應(yīng)用在 CSRF 攻擊防范 一文中已經(jīng)講過(guò)，這里不再贅述，感興趣的讀者可以跳轉(zhuǎn)閱讀。

數(shù)據(jù)備份

將數(shù)據(jù) x 和數(shù)據(jù) y 進(jìn)行異或運(yùn)算得到備份數(shù)據(jù) z, 然后將三個(gè)數(shù)據(jù)同時(shí)保存 (備份數(shù)據(jù) z 保存到可用性更高的數(shù)據(jù)中心)，之后不論數(shù)據(jù) x 或數(shù)據(jù) y 損壞了，都可以根據(jù)備份數(shù)據(jù) z 進(jìn)行恢復(fù)。

簡(jiǎn)化計(jì)算

在多個(gè)值進(jìn)行計(jì)算的場(chǎng)景中，可以根據(jù)運(yùn)算定律簡(jiǎn)化計(jì)算過(guò)程:

x ^ y ^ z ^ x ^ y

上述計(jì)算式子根據(jù)交換律，可以得到:

x ^ y ^ z ^ x ^ y

根據(jù) “任何數(shù)與自身進(jìn)行異或運(yùn)算，結(jié)果都為 0” 運(yùn)算定律，可以得到:

0 ^ 0 ^ z = z

算法設(shè)計(jì)

異或運(yùn)算經(jīng)常被用于設(shè)計(jì)高效的數(shù)據(jù)結(jié)構(gòu)和算法，例如之前的文章提到的 布谷鳥(niǎo)過(guò)濾器。

LeetCode 原題

給你一個(gè) 非空 整數(shù)數(shù)組 nums ，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。

要求: 必須設(shè)計(jì)并實(shí)現(xiàn)線性時(shí)間復(fù)雜度的算法來(lái)解決此問(wèn)題，且該算法只使用常量額外空間。

# 示例 1
輸入：nums = [2,2,1]
輸出：1

# 示例 2
輸入：nums = [4,1,2,1,2]
輸出：4

# 示例 3
輸入：nums = [1]
輸出：1

解題代碼如下:

// 利用異或運(yùn)算的性質(zhì):
// 1. 任何數(shù)和 0 做異或運(yùn)算，結(jié)果仍然是原來(lái)的數(shù)
// 2. 任何數(shù)和其自身做異或運(yùn)算，結(jié)果是 0
// 3. 異或運(yùn)算滿足交換律和結(jié)合律，a^b^a = b^a^a = b^(a^a) = b^0 = b
func singleNumber(nums []int) int {
 res := 0
 for _, v := range nums {
  res ^= v
 }
 return res
}