认识异或运算

基本定义

相同为 0，不同为 1 ：

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

把异或符号换成加号：

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

所以只需要记住异或运算就是无进位相加，也就是半加器:

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

基本性质

异或运算的性质（用无进位相加来理解）

0 ^ N == N N ^ N == 0

满足交换律和结合率: a ^ b ^ c ^ d ^ e = d ^ c ^ b ^ e ^ a

实战

1、快速比较两个值相等

肯定会想到 a - b == 0 来判断，但 a ^ b == 0 效率会更高

2、交换两个整数而不必使用第三个参数

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、一个数组中有一个数出现了奇数次，其他数都出现了偶数次，怎么找到这个出现奇数次的数？

假设一个数组[1,2,4,3,4,3,1] 根据性质 1 性质 2 将数组中所有的数进行组合异或：

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解题思路提供的拓展)怎么将一个整数的类型，提取出最右侧的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 //进行取反，0和1互换
       ~N + 1 = 1 1 0 0 1 0 1 1 0 0 0 0 //二进制加法
               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 //找到倒数第五个位置为1

5、一个数组中有两个不等数出现了奇数次，其他数都出现了偶数次，怎么找到这两个数？

先看代码

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必然有一个位置是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; //找到剩余的成员 假设找到的是a,那么 a ^ b ^ a = b
}

1、首先按题目3的解题思路，将数组结合异或得出的结果eor = a ^ b,其中 a $\neq$ b，那 a ^ b $\neq$ 0, 说明a和b二进制上一定有同一个位置出现1和0的区分，所以 a ^ b 必然有一个位置是1
2、按题目4的解题思路，找到 rightOne 的位置
3、再将数组根据rightOne的位置进行过滤，可以将a或者b的数剔除出去，这样就回到了题目3的思路，结合异或运算，那么最终eor2一定等于a或者b
4、再结合题目2的思路 eor ^ eor2 可以得出另一个数

最后编辑于：2020.10.20 08:48:20