算法练习5：异或操作在算法中的应用

在写算法前，我们先看看异或有什么特点：相同位异或得0，不同位异或为1
比如: 1 ^ 2 = 3
1: 0 0 1
2: 0 1 0
res:0 1 1 => 3

利用这个特性，我们可以推导出：

• 相同的数自身进行异或操作结果为0：n ^ n = 0
• 交换律: a ^ b ^ c = a ^ c ^ b
• 任何数与0进行异或操作为它自身：n ^ 0 = n

利用这些特性可以，我们可以找到出现奇数次的数，下面我们来看粟子：

题目：查找一个出现奇数次的数

一个无序数组里有若干个正整数，范围是1-10，其中有9个数字出现了偶数次，只有1个数字出现了奇数次，问如何找到这个出现奇数次的整数？

• 解题思路：
  1. 因为偶数次，可以看成是2n次，然后因为数自身进行异或等于0，所以相当于 n(num ^ num) = n * 0 = 0，所以出现偶数次的整数，又因为交换律（所以在哪个位置都一样），所以它们自身异或的结果永远为0；
  2. 而奇数次，可以看成是2n + 1次，同理2n次后的这个数结果为0，仅剩下1次自身num，而任何数与0异或都等于它自身，所以它们异或后的结果为num本身
  3. 利用上俩个结论，只要把所有数进行异或操作，得到的结果就是出现奇数次的整数了

function getOdd(arr) {
  let res = 0;
  for(let i = 0; i < arr.length; i++) {
    res ^= arr[i]
  }
  return res;
}

const res = getOdd([1, 1, 4, 2, 2, 3, 3])
console.log('res:', res); // 4

• 遍历一次数组（长度n），时间复杂度为O(n)；空间复杂度为O(1)

扩展：查找2个出现奇数次的数

如果数组里出现有2个出现奇数次的数，其他整数出现偶数次，该如何找出这俩个数?

先了解一个特性：

• 两个不同的数，进行异或操作，结果中至少有一位二进制的值是1，因为如果都是0，就代表两个数是相等的

解题：

1. 第一步还是按照找单个奇数次的方法，对所以数进行异或操作，得到出现奇数次的A和B两个数的异或结果，结果中至少有一位二进制的值是1
2. 二进制为1的这位数，代表着A和B这两个数中的这一步是不同的，因为如果都相同，那异或结果不会为1。根据这个特点，可以将数组分割成2部分，一部分包含A，一部分包含B
3. 再分别对2部分进行异或操作，就能分别得到A和B了

举个例子：

1. [1,5, 1, 3, 2, 2],所有数进行异或操作，得到5和3的异或结果
   5： 101
   3： 011
   xor：010
2. 创建一个分隔位seperator，初始值为1，每次与xor相与，来查找xor中第一次出现1的位数，如果相与结果为0，代表者不是这一位，分隔位向左移一位，继续查找，直到查找到相与结果不为0，即为结果：
   • 第一次相与结果：
     seperator：001
     oxr： 010
     &： 000
     结果为0，不是这一位，seperator向左移一位，继续相与:
   • 下一次相与结果：
     seperator：010
     oxr： 010
     &： 010
     结果为2，不为0，代表着这位分隔位seperator就是分割A和B两个数所需要的
3. 遍历数组，将所有与seperator相与为0的数，全部放到一边做异或操作；相与结果为其它数的，全部放到另一边进行异或操作
   1与seperator（2）结果为：0，用a来存储其异或结果，a=1
   5与seperator（2）结果为：0，继续放在a那组进行异或操作，a =1^5=4
   1与seperator（2）结果为：0，继续放在a那组进行异或操作，a =4^1=5
   3与seperator（2）结果为：1，结果不是0，用另一数b来存储其异或结果,b=3
   2与seperator（2）结果为：0，继续放在a那组进行异或操作，a = 5^2=7
   2与seperator（2）结果为：0，继续放在a那组进行异或操作，a = 7^2=5
   此时，a最终结果为5，b最终结果为3,就是我们想要求得的数

function getTwoOddNum(arr) {
  let xorRes = 0;
  let a = 0;  // 第1个奇数次的数
  let b = 0;  // 第2个奇数次的数
  // 获得两个数A和B的异或结果
  for(let i = 0; i < arr.length; i++) {
    xorRes ^= arr[i] 
  }
  // 如果两个数结果为0，代表两数相同，不存在结果
  if(xorRes === 0) {
    return null;
  }
  // seperator用来判断两个整数的第一个出现的不同位
  let seperator = 1 // 初始值设在最末尾
  // 如果xorRes和seperator相与的结果为0，代表着xorRes的这一位为0，不是我们想要的结果
  while((xorRes&seperator) == 0) {
    // 分隔符继续向左移一位查找
    seperator <<= 1
  }
  // 如果xorRes和seperator相与的结果为1时，代表着seperator这一位为1，就是A和B两个数不一样的位数
  // 第二次遍历
  for(let i = 0; i < arr.length; i++) {
    // 分隔位为1的部分
    if(arr[i] & seperator) {
      a ^= arr[i]
      // 分隔位为0的部分
    }else {
      b ^= arr[i]
    }
  }
  return [a, b]
}
const res1 = getTwoOddNum([1, 1,5, 1, 4, 2, 2, 3, 3,5])
console.log(res1); // [ 1, 4 ]