位運算中異或的常見用法總結

異或(^) 這個位操作運算符相信大家一定都不陌生，這個運算符可以用來解決很多普通算法解決不了的問題，而且位運算是直接對二進制碼做運算，相對普通的加減乘除運算符來說的話更加的高效，我們借着題目一起來看看。

1

對兩個輸入參數做加法運算，但是不能使用 “+” 運算符 。

解法思路

看到這樣的問題，能想到的隻有位運算，問題是怎麼算？相信大家國小剛學習加法的時候，對于一下子不能得到答案的題，肯定會在草稿紙上列豎式，從右向左算，同一列對下來的數字相加如果超過 10，那麼肯定要在下面寫兩個數字相加後的個位數，然後往前進一位，下一位運算時就要加上這個進位，用這樣的方式直到最後算出結果。這題的思路也是一樣的，隻不過有兩點不一樣，第一，10 進制變成了 2 進制，第二，我們不再是在草稿紙上列豎式，而是要寫成計算機看得懂的代碼，這就得借助我們的位運算了，因為 2 進制表示的數中隻會出現 0 和 1，你可以把這兩個數看成是 true 和 false，這樣更好了解，我們可以先通過異或塞選出不用進位的情況，然後再用與運算和左移運算計算出進位的情況，疊代更新出最後的結果。

參考代碼

public int plus(int a, int b) {         int aTemp = 0, bTemp = 0;         while (b != 0) {             aTemp = a ^ b;             bTemp = (a & b) << 1;             a = aTemp;             b = bTemp;         }         return a;     }           

02

如何在不建立臨時變量的情況下進行交換兩個數？

異或的常見應用，很簡單，但是注意思考角度從位出發，而不是數，這點很重要。

public void swap(int a, int b) {         a ^= b; // a 中存放兩數互異的點位         b ^= a; // 取反 b 中不同于 a 的點位，也就是實作了 b = a         a ^= b; // 取反 a 中不同于 b 的點位，也就是實作了 a = b     }           

03

如果把 A 轉換成 B ，需要改變多少位？

異或的簡單應用，兩個數做異或的結果就是兩個數差異所在，然後隻需計算這個結果中有多少個 1 即可。

public int convertA2B(int A, int B) {         int n = A ^ B;         int count = 0;         while (n != 0) {             n = n & (n - 1); // n - 1 是将 n 的最低位為零             count++;         }         return count;     }           

04

LeetCode 第 136 号問題：給定一個非空整數數組，除了某個元素隻出現一次以外，其餘每個元素均出現兩次。找出那個隻出現了一次的元素。

異或的三個點順下來，就可以很清楚地解這道題：

異或運算和乘法一樣，位置和運算順序不影響最後結果：

a^b^c = b^c^a

兩個相同的數做異或運算結果為零：

a^a = 0

任何數和零做異或結果還是這個數本身：

a^0 = a

public int findOnce(int[] arr) {         int result = 0;         for (int i = 0; i < arr.length; ++i) {             result ^= arr[i];         }         return result;     }           

05

LeetCode 第 137  号問題：給定一個非空整數數組，除了某個元素隻出現一次以外，其餘每個元素均出現了三次。找出那個隻出現了一次的元素。

這題的難點在于 3 次，如果把數組裡面的數字就當作數字本身來看的話，很難找到突破口；如果想到了位運算，那就要有一個概念就是位運算是基于位的，而不是基于數的，在這個問題中，所有的 bit 的出現次數隻會有兩種情況，

3*n，3*n + 1

,這裡的 n 是任意整數，假設你周遊數組，其實會有一個中間态就是 

3*n + 2

 存在，對于除這個數以外的其他數，過程大概是 

3*n + 1

 -> 

3*n + 2

3*n

，我們隻要記錄的就是 

3*n + 1

 和 

3*n + 2

的情況，因為 

3*n

 其實就是一個初始狀态（n=0）,記不記錄和我們最後要傳回的答案無關，而記錄 

3*n + 2

 是為了恢複一些 bit 從 

3*n + 2

 到 

3*n

public int singleNumber(int[] nums) {         int ones = 0, twos = 0;         for (int i = 0; i < nums.length; ++i) {             // 找出目前的 3n + 1             ones = (nums[i] ^ ones) & (~twos);             // 找出目前的 3n + 2             twos = (nums[i] ^ twos) & (~ones);         }         return ones;     }           

06

LeetCode 第 260  号問題：給定一個整數數組 

nums

，其中恰好有兩個元素隻出現一次，其餘所有元素均出現兩次。找出隻出現一次的那兩個元素。

這題的主要難點是如何把兩個數給拆出來，如果直接運用異或算法，我們最後得到的結果是兩個數做異或的結果，關鍵點是如何基于這個異或的結果來找到這兩個數，有一點很重要的就是，異或的結果為 1 的點位隻會出現在其中一個數中，我們可以用其中一個為 1 的點位作為判斷依據，這個點位存在的所有數在一起做異或，這個點位不存在的所有數一起做異或，這樣就把這個問題拆解成了兩個 problem 3。

public int[] singleNumber(int[] nums) {         if (nums == null || nums.length == 0) {             return new int[2];         }         int different = 0;         for (int i : nums) {             different ^= i;         }         different &= -different;         int[] ans = {0, 0};         for (int i : nums) {             if ((different & i) == 0) {                 ans[0] ^= i;             } else {                 ans[1] ^= i;             }         }         return ans;     }           

總結

位運算相對其他的運算來說更加的高效，異或在位運算中的應用非常廣，但是這裡的難點是我們平時可能會忽視位運算，導緻我們遇到一般的問題不會往位運算的方向去想，另外就是如果對二進制的運算不熟，我們也很難了解一些位運算的綜合操作，這裡提到了異或可以交換兩個數，做加法操作，還可以用來解決一些問題。