Go: 異或運算的妙用

概述

異或運算 通過對兩個相同長度的二進制數進行逐位比較，若對應位的值不同，結果爲 1, 否則結果爲 0, Go 語言中使用的運算符號爲 ^。

下面舉幾個簡單的小例子:

圖片來源: https://www.build-electronic-circuits.com/xor-gate/

運算定律

交換律

x ^ y = y ^ x

結合律

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

任何數與自身進行異或運算，結果都爲 0

x ^ x = 0

任何數與 0 進行異或運算, 結果爲其自身

x ^ 0 = x

有了上面的理論基礎之後，下面來看下異或運算的幾個應用。

交換兩個變量的值

有個經典的筆試題：交換兩個變量的值，不能使用第三個變量。

解法一

利用 Go 語言的原生 “騷操作” :

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
}

當然了，如果在真實面試中這樣寫，只能回去等消息了。

解法二

利用加法分配率

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
}

解法三

異或運算性質: 三個值中的任意兩個值進行異或運算，都可以得出第三個值。

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
}

加密解密

異或運算可以實現簡單高效的加密解密，例如:

明文數據爲 text
密鑰爲 secret
密文數據爲 token

# 服務端響應時，返回加密數據

token = text ^ secret

# 服務端接收到請求時，解密數據

text = token ^ secret

這個經典應用在 CSRF 攻擊防範一文中已經講過，這裏不再贅述，感興趣的讀者可以跳轉閱讀。

數據備份

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

簡化計算

在多個值進行計算的場景中，可以根據運算定律簡化計算過程:

x ^ y ^ z ^ x ^ y

上述計算式子根據交換律，可以得到:

x ^ y ^ z ^ x ^ y

根據 “任何數與自身進行異或運算，結果都爲 0” 運算定律，可以得到:

0 ^ 0 ^ z = z

算法設計

異或運算經常被用於設計高效的數據結構和算法，例如之前的文章提到的布穀鳥過濾器。

LeetCode 原題

給你一個非空整數數組 nums ，除了某個元素只出現一次以外，其餘每個元素均出現兩次。找出那個只出現了一次的元素。

要求: 必須設計並實現線性時間複雜度的算法來解決此問題，且該算法只使用常量額外空間。

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

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

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

解題代碼如下:

// 利用異或運算的性質:
// 1. 任何數和 0 做異或運算，結果仍然是原來的數
// 2. 任何數和其自身做異或運算，結果是 0
// 3. 異或運算滿足交換律和結合律，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
}

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/gmihrYjKVoLpj58SOZPejA

概述