# 题目

一个整型数组里除了两个数字之外,其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。

# 思路

1异或1=0 0异或0=0 1异或0=0

# 如果题目是只有一个只出现一次的数字:

两个相同的数异或值为0,将数组所有的值进行异或操作,最后剩余值就是目标值。

# 如果有两个出现一次的值

  • 数组所有元素异或后是两个目标值的异或值
  • 两个目标值不相等,所以最终的异或值不为0
  • 最终异或值的二进制某一位肯定是1,找到这个位置为index
  • 所以目标的两个值的二进制,一个index位为0,另一个index位为1
  • 按二进制index位为01,将数组分两批进行异或,两批最后的结果即为两个目标值

# 代码

    function FindNumsAppearOnce(array) {
      let exclusive = 0;
      for (let i = 0; i < array.length; i++) {
        exclusive = exclusive ^ array[i];
      }
      let index = findFirst1(exclusive);
      let result1 = 0;
      let result2 = 0;
      for (let i = 0; i < array.length; i++) {
        if (isN1(array[i], index)) {
          result1 = result1 ^ array[i]
        } else {
          result2 = result2 ^ array[i]
        }
      }
      return [result1, result2];
    }

    // 找到n的二进制第一个为1的位置
    function findFirst1(n) {
      let index = 0;
      while (((n & 1) === 0) && index < 64) {
        n = n >> 1;
        index++;
      }
      return index;
    }

    // 判断n的二进制第index位是否为1
    function isN1(n, index) {
      return n & (n >> index);
    }