左神讲算法——异或的高级操作（两数交换+经典面试题）

桃扇骨 2022-10-06 07:57 172阅读 0赞

--------------------

### 目录 ###

*  1. 异或的性质
 *  2. 两数交换
 *  3. 经典面试例题

> **参考链接**：[2021最新左神数据结构算法全家桶][2021]

--------------------

# 1. 异或的性质 #

异或可以看成相同为1，不同为0；也可以看作无进位相加，有奇数个1则结果为1，有偶数个1则结果为0

1.  异或满足交换律和结合律：`a^b=b^a` `(a^b)^c=a^(b^c)`
2.  任何数与0异或不变：`a^0=a`
3.  任何数异或自己为零：`a^a=0`

--------------------

# 2. 两数交换 #

当我们交换两个数时，可以通过异或的方式进行操作：

//交换两个数
    a = a ^ b;	//a=a^b b=b
    b = a ^ b;	//b=a^b^b=a^0=a a=a^b
    a = a ^ b;	//a=a^a^b=0^b=b

该方式的原理就是通过异或的性质实现的：

*  第一步中：a=a^b，b=b
 *  第二步中：b=a^b^b=a^0=a，a=a^b
 *  第三步中：a=a^a^b=0^b=b，b=a

由此可见，a和b达到了交换的目的。但请注意：用这种方式的前提是**a和b指向不同的内存地址**，否则异或会清零，比如我们在数组中使用时，注意i和j不能相同

//交换arr[i]和arr[j]
    public static void swap(int[] arr, int i, int j) { 
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

--------------------

# 3. 经典面试例题 #

> **例题**：在一个数组中，出现了以下两种情况，如何快速求解（规定时间复杂度为`O(N)`，空间复杂度为`O(1)`）
> 
> 1.  一个数组中，只有一种数出现了奇数次，其余数出现了偶数次，怎么找到该数？
> 2.  一个数组中，有两种数出现了奇数次，其余数出现了偶数次，怎么找到这两个数？

1️⃣ 对于第一问，只需要声明一个变量`eor`初始化为0，然后遍历数组与变量依次异或，最后得到的数即为所求数。为什么？因为异或满足交换律和结合律，遍历数组依次异或相当于与组中所有的数进行了异或，然后可调整顺序，将相同的数调整到一起异或为0，又因为相同的数为偶数个，所以除奇数次以外的数完全抵消了，最后相当于0与奇数次的数异或得到奇数次的数

public static void printOddTimesNum1(int[] arr) { 
        int a = 0;
        for (int cur : arr)
            a = a ^ cur;
        System.out.println(a);
    }

2️⃣ 对于第二问，我们可以声明两个变量来解决，第一个变量`eor1`同第一问，遍历数组依次异或，根据交换律结合律。出现偶数次的数两两抵消，最后只会留下出现奇数次的数进行异或，假设这两个数为a和b，所以得到`eor=a^b`；第二个变量我们声明为`eor2`，由于a和b是不同的，所以a与b异或的结果`eor!=0`，因此eor中必有一位为1，显然该位为1是因为a、b中该位的值不同，我们假设该位为第i位，然后我们可以根据第i位是否为1将整个数组分为两部分，这样我们就将ab分开了，如下图所示：  
![image-20210612074219200][]  
然后我们用`eor2`只遍历数组中第i位为1的数进行异或，即上图中的左半部分，这样就会得到`eor2=a`（或者只遍历数组中第i位为0的数进行异或，这样会得到`eor2`=b）

经过上述的异或计算，我们得到了a异或b的值和其中一个值，然后将`eor1`和`eor2`进行异或就能得到另一个值：

eor1 = a ^ b
    eor2 = a	//或 eor2 = b
    eor1 ^ eor2 = a^(a^b) = b

这样我们就求出了两个出现奇数次的数，代码如下所示：

public static void printOddTimes2Num2(int[] arr) { 
        int eor1 = 0;
        int eor2 = 0;
        for (int i = 0; i < arr.length; i++) { 
            eor1 ^= arr[i]; //得到eor1=a^b
        }
        int rightOne = eor1 & (~eor1 + 1);//提取出eor1最右边的1
        for (int cur : arr) { 
            if ((cur & rightOne) == 1)
                eor2 ^= cur; //得到eor2=a或b
        }
        System.out.println("两数分别为:" + eor2 + "," + (eor1 ^ eor2));
    }

其中`rightOne = eor1 & (~eor1 + 1)`是提取出a^b中最右边的那个一，这是常规操作，大家记住即可，如下案例所示帮助理解：

eor1		1 0 1 0 1 1 1 1 0 0
    ~eor1		0 1 0 1 0 0 0 1 1 1
    ~eor+1		0 1 0 1 0 0 0 1 0 0
    --------------------------------------
    rightOne	0 0 0 0 0 0 0 1 0 0

[2021]: https://www.bilibili.com/video/BV1Vb4y1f7kK?p=2&t=5533
[image-20210612074219200]: /images/20221005/5234223fa82f43dd90b36f846d9fdc13.png