基本定義

• 相同為 0，不同為 1 ：

 0 ^ 0 = 0  ,  0 ^ 1 = 1  , 1 ^ 0 = 1 , 1 ^ 1 = 0

• 把異或符號(hào)換成加號(hào)：

0 + 0 = 0  , 0 + 1 = 1 , 1 + 0 = 0  , 1 + 1 = 0

• 所以只需要記住異或運(yùn)算就是無(wú)進(jìn)位相加，也就是 半加器:

 6 ^ 7 = 110 ^ 111 = 110 + 111 = (1+1)(1+1)(0+1) = (0)(0)(1) = 1

基本性質(zhì)

異或運(yùn)算的性質(zhì) （用無(wú)進(jìn)位相加來(lái)理解）

1. 0 ^ N == N ??? N ^ N == 0
2. 滿足交換律和結(jié)合率: a ^ b ^ c ^ d ^ e = d ^ c ^ b ^ e ^ a

實(shí)戰(zhàn)

1、 快速比較兩個(gè)值相等

肯定會(huì)想到 a - b == 0 來(lái)判斷，但 a ^ b == 0 效率會(huì)更高

2、 交換兩個(gè)整數(shù)而不必使用第三個(gè)參數(shù)

a = 9;
b = 11;
a = a ^ b; // 將 9 ^ 11 賦值給 a 變量
b = a ^ b; // b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a
a = a ^ b; // a = (a ^ b ) ^ a = (a ^ a) ^ b = 0 ^ b = b

3、 一個(gè)數(shù)組中有一個(gè)數(shù)出現(xiàn)了奇數(shù)次，其他數(shù)都出現(xiàn)了偶數(shù)次，怎么找到這個(gè)出現(xiàn)奇數(shù)次的數(shù)？

假設(shè)一個(gè)數(shù)組[1,2,4,3,4,3,1] 根據(jù) 性質(zhì) 1 性質(zhì) 2 將數(shù)組中所有的數(shù)進(jìn)行組合異或：

1 ^ 2 ^ 4 ^ 3 ^ 4 ^ 3 ^ 1 = (1 ^ 1) ^ (2) ^ (4 ^ 4) ^ (3 ^ 3) = 0 ^ 2 ^ 0 ^ 0 = 2

public static void PrintOddTimeNum1(int[] arr)
{
    int eor = 0;
    for (int i = 0; i < arr.Length; i++)
    {
        eor ^= arr[i];
    }
    Console.WriteLine(eor);
 }

4、 (為題目5解題思路提供的拓展)怎么將一個(gè)整數(shù)的類型，提取出最右側(cè)的1

???????????????N = 0 0 1 1 0 1 0 1 0 0 0 0
?????????????~N = 1 1 0 0 1 0 1 0 1 1 1 1 //進(jìn)行取反，0和1互換
???????~N + 1 = 1 1 0 0 1 0 1 1 0 0 0 0 //二進(jìn)制加法
???????????????N = 0 0 1 1 0 1 0 1 0 0 0 0
N & (N + 1) = 0 0 0 0 0 0 0 1 0 0 0 0 //找到倒數(shù)第五個(gè)位置為1

5、 一個(gè)數(shù)組中有兩個(gè)不等數(shù)出現(xiàn)了奇數(shù)次，其他數(shù)都出現(xiàn)了偶數(shù)次，怎么找到這兩個(gè)數(shù)？

先看代碼

public static void PrintOddTimesNum2 (int[] arr)
{
    int eor = 0;
    for(int i=0;i<arr.Length;i++)
    {
        eor ^= arr[i]; //最后eor = a ^ b
    }
    // eor = a ^ b
    // eor != 0
    // eor必然有一個(gè)位置是1
    int rightOne = eor & (~eor + 1); //提取出最右的1
    
    int eor2 = 0;
    
    for(int i=0; i<arr.Length;i++)
    {
        if ((arr[i] & rightOne) != 0)
        {
            eor2 ^= arr[i]; //找到a或者b的其中一員
        }
    }

    int other = eor ^ eor2; //找到剩余的成員 假設(shè)找到的是a,那么 a ^ b ^ a = b
}

1、首先按題目3的解題思路，將數(shù)組結(jié)合異或得出的結(jié)果eor = a ^ b,其中 a b，那 a ^ b 0, 說明a和b二進(jìn)制上一定有同一個(gè)位置出現(xiàn)1和0的區(qū)分，所以 a ^ b 必然有一個(gè)位置是1
2、按題目4的解題思路，找到 rightOne 的位置
3、再將數(shù)組根據(jù)rightOne的位置進(jìn)行過濾，可以將a或者b的數(shù)剔除出去，這樣就回到了題目3的思路，結(jié)合異或運(yùn)算，那么最終eor2一定等于a或者b
4、再結(jié)合題目2的思路 eor ^ eor2 可以得出另一個(gè)數(shù)