位運算的秒用--異或運算面試真題

前言

上次咱們聊了聊異或運算的妙用，其實簡單來說，就是記住異或運算的三個特性

• 0和任何數N進行異或運算，結果為N。
• 任何數N和自己進行異或運算，結果為0。
• 異或運算滿足交換律和結合律 當然如果您對這幾個特性不是很瞭解，或者不是很熟悉異或運算的話，建議先看看這篇文章​ ​ 位運算的妙用--異或運算​ ​。

「閒話不用多說，咱們來看面試真題」

Q1:一個數組中有一種數出現了奇數次，其他數都出現了偶數次，怎麼找到這一個數

「要求：時間複雜度O(n)」。

其實這道題還是比較好理解的。

咱們直接來舉例子。

比如陣列[1,1,2,2,3] 把3找出來即可，因為3只出現了1次，為奇數次，其餘的數字出現的都為偶數次。

比如陣列[1,1,2,2,3,3,3] 同樣把3找出來即可。

其實最簡單的方法，也就是暴力破解法，咱們可以把陣列迴圈一遍，把每個數字出現的數字記錄在另一個數組中(需要記錄數字和該數字出現的次數的map)，然後迴圈另一個數組找出出現次數為奇數的即可。「但是這個題目有要求」，時間複雜度要求為O(n)，也就是說只能迴圈一次就把結果就找出來，所以暴力破解法肯定是行不通的。所以咱們必須得換個思路。

利用異或運算的規律來解題

首先，在異或運算中「任何數N和自己進行異或運算，結果為0」,所以我們把陣列中的所有數進行異或運算，所有「出現偶數次的數字進行異或運算結果為0」，咱們來看一個例子(因為異或運算滿足交換律，所以不用關心數字出現的位置)。

arr = [a,b,b,c,c,c,c,d,d.............]

比如看上述陣列，咱們來對每個元素進行異或運算。

temp = a ^ b ^ b ^ c ^ c ^ c ^ c ^ d ^ d

因為「任何數N和自己進行異或運算，結果為0」所以除了a以外的數字，異或結果為0。

所以全部進行異或運算一次的結果為：

temp = a^0

其實簡單的說就是兩個b異或結果為0，兩個c異或結果是0(上面的case寫了4個c，其實結果是一樣的)，兩個d異或結果為0，那麼所有的數字異或下來，出現偶數次的結果異或運算的結果就為0。

另外根據「0和任何數N進行異或運算，結果為N」所以：

temp = a^0 = a

所以最終的temp則為我們需要找到的數，原始碼如下：

func findOddTimesNumber(arr []int) (temp int) {
 for i := 0; i < len(arr); i++ {
  temp ^= arr[i] //temp預設為0  相當於0^a(出現奇數次的數字)^b^b^c^c.......,根據上述運算的解析，結果為a，也就是我們想找到的數
 }
 return temp
}

如果上面的題您已經明白了，那麼「接下來咱們加大難度，看一種更復雜的情況」。

Q2:一個數組中有兩種數出現了奇數次，其他數都出現了偶數次，怎麼找到這一個數

「要求：時間複雜度O(n)」。

這道題和上面那道題的區別就在於「有兩種數字出現了奇數次」。

arr = [a,b,c,c,d,d,e,e......]

其實簡單說也就是要把上面陣列arr中的a和b分別找出來，如果按照前面的方法全部異或一次，那麼結果肯定為a^b,我們的目的是把a和b分別找出來，這種辦法當然是行不通的，或者說是不夠的。

但是上面計算之後的結果：

temp= a^b(其餘出現偶數次的數字進行異或運算結果都為0)

首先，因為a和b是兩種數，所以「a肯定是不等於b的」,所以「a^b的結果肯定大於0」,換句話說a^b的結果，也就是「temp的二進位制表現肯定是至少有一位是1的」。這句話很重要，明白了這句話咱們就繼續往下看。

比如temp的第7位為1，那就說明a和b的第7位是不一樣的，一個為0，一個為1。那麼咱們是不是可以通過第7位是否為1，然後進行分組，「每個分組中出現的偶數次的數字的異或結果都是0的」，所以最後兩個分組各自剩下的就是所需數字了。

咱們先來看一個方法。

res := num & (^num + 1)

上述方法的目的是獲取num最左邊的1。什麼意思呢?比如num是 1011011，那麼他最左邊的1 就是00000001。

咱們用一個代入的方式一步一步的計算試試。

所以最後演算法如下：

func findTwoOddTimesNumber(arr []int) (left, right int) {
 for i := 0; i < len(arr); i++ {
  left ^= arr[i]
 }
 temp := left & (^left + 1)  //獲取最左邊的1

 for i := 0; i < len(arr); i++ {
  if arr[i]&temp == 0 {  //根據某一位是否為1進行分組
   right ^= arr[i]
  }
 }
 left = right ^ left
 return left, right
}