點擊藍色「五分鐘學算法」關注我喲
加個「星標」，一起學算法
異或(^) 這個位操作運算符相信大家一定都不陌生，這個運算符可以用來解決很多普通算法解決不了的問題，而且位運算是直接對二進位碼做運算，相對普通的加減乘除運算符來說的話更加的高效，我們借著題目一起來看看。
對兩個輸入參數做加法運算，但是不能使用 「+」 運算符 。
看到這樣的問題，能想到的只有位運算，問題是怎麼算？相信大家小學剛學習加法的時候，對於一下子不能得到答案的題，肯定會在草稿紙上列豎式，從右向左算，同一列對下來的數字相加如果超過 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;
}
如何在不創建臨時變量的情況下進行交換兩個數？
解法思路異或的常見應用，很簡單，但是注意思考角度從位出發，而不是數，這點很重要。
參考代碼public void swap(int a, int b) {
a ^= b;
b ^= a;
a ^= b;
}
如果把 A 轉換成 B ，需要改變多少位？
解法思路異或的簡單應用，兩個數做異或的結果就是兩個數差異所在，然後只需計算這個結果中有多少個 1 即可。
參考代碼public int convertA2B(int A, int B) {
int n = A ^ B;
int count = 0;
while (n != 0) {
n = n & (n - 1);
count++;
}
return count;
}
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;
}
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) {
ones = (nums[i] ^ ones) & (~twos);
twos = (nums[i] ^ twos) & (~ones);
}
return ones;
}
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;
}
位運算相對其他的運算來說更加的高效，異或在位運算中的應用非常廣，但是這裡的難點是我們平時可能會忽視位運算，導致我們遇到一般的問題不會往位運算的方向去想，另外就是如果對二進位的運算不熟，我們也很難理解一些位運算的綜合操作，這裡提到了異或可以交換兩個數，做加法操作，還可以用來解決一些問題。
歡迎你來分享你對異或以及位運算的認識。