位運算的秒用--異或運算

語言: CN / TW / HK

先來看一個case

咱們今天閒話不用多說,先來看一個小例子。

如何交換兩個數?

問題當然很簡單,交換兩個數,常規的做法是引入一箇中間變數,程式碼如下

func Swap(a, b int){
 temp := a   //把a的值賦值給臨時變數temp,temp為a的值
 a = b   //把b的值賦值給a,現在a的值已經變成了b的值
 b = temp  // 再把之前temp中儲存的a賦值給b即可
}

相信上面的程式碼大家應該都沒問題,但是咱們來加大問題難度,如果不讓引入第三個變數temp,能實現兩個數字的交換麼?

「建議大家先思考兩分鐘再往下看」。

其實很簡單,程式碼如下:

func Swap(a, b int) {
 a = a ^ b
 b = a ^ b
 a = a ^ b
}

相信您現在應該和我第一次看到這個程式碼的感覺一樣,這特麼是啥?????這樣能把a和b的值交換?

先不要著急,咱們來一點一點的分析。

異或運算

想要看懂上面的程式碼,首先你得知道什麼叫異或運算。

先看定義

如果a、b兩個值不相同,則異或結果為1。如果a、b兩個值相同,異或結果為0。(這特麼是啥?)沒明白沒有關係,咱們接下來看例子:

舉個例子

比如a=5,b=3。

  • 首先 你得把a和b轉換成二進位制,那麼a=101, b= 011。
  • 然後a和b進行異或運算,一位一位的去對比,如果值相同,則對應位置異或運算的結果為0,如果值不同,則對應位置異或運算的結果為1。

異或運算示意圖

  • 所以a和b的異或運算的結果為 110 也就是6。
  • 異或運算也可以按照另外一個角度去理解,就是「無進位的加法」,其實也就是二進位制的相加,但是加完的結果不進位而已。

異或運算的特點

0和任何數N進行異或運算,結果為N

其實這個很好理解,任何數轉換成二進位制,每一位上的數字要麼是0,要麼是1,而和0進行異或,以前是0的位置和0相同,則結果為0,以前是1的位置和0不同,則結果為1,所以運算之後結果是沒變的,如下圖:

任何數和0進行異或運算

任何數N和自己進行異或運算,結果為0

這個也很好理解,N^N每一位肯定都會是一樣的,根據異或運算的法則,結果肯定每一位都為0。

任何數和自己進行異或運算

異或運算滿足交換律和結合律

這個很好理解 也就是說 a^b^c運算 和c^b^a是一樣的。

再來看開頭的例子

當你對異或運算有一定的瞭解了之後,咱們再來看一看開頭的例子:

func Swap(a, b int) {
 a = a ^ b
 b = a ^ b
 a = a ^ b
}

第一步運算:

a = a ^ b

第二步運算:

b = a ^ b
因為第一步a=a^b所以在第二步中直接把a替換成a^b即可

所以:

b = a ^ b ^ b

咱們在之前說過,「任何數字對自己進行異或運算的結果都為0」,所以b^b的結果就為0,上面也就等價於。

b= a^0

咱們在上面還說過,「任何數和0進行異或運算,都等於他自己」,所以:

b=a^0 = a

第三步運算:

a = a ^ b

此時b已經運算出來為a,a = a ^ b(第一步運算賦值) 所以第三步運算等價於。

a = a^b^a = 0^b = b(運算細節同第二步)

這樣咱們就可以不用第三個變數進行兩個變數的交換了。