异或运算解决查找数组中出现奇数次元素

        假设有一个数组只有一个元素出现奇数次，需要查找这个出现奇数次的元素，怎么使用时间复杂度为O(n)，空间复杂度为O(1)，来解决这道题。以下是使用异或来解决这道题：

  public static int selectOddTimesNum(int[] nums) {
    int result = 0;
    for (int num : nums){
      result ^= num;
    }
    return result;
  }

        这里可以看到，时间复杂度为O(n)，空间复杂度只创建了个result变量接收结果，也满足了题目要求。如果不使用异或的话，一般操作是使用HashMap或者其它数据结构来遍历数组，并将每个元素出现的次数记录，然后再遍历输出奇数次的元素。

        这里使用了异或发现，这样更简洁更方便解决这个问题。这里只查了一次，那么我需要进阶一下。有一个数组，里面有2个出现了奇数次的元素，那怎么使用异或运算将这两个数查找出来呢？

        这好像不难，但是按照上面的异或运算，最后结果只能查找出两个奇数次元素的异或结果，并不能分别找出这两个元素。这里就需要回归异或，以及系统运算的原理了。首先异或，可以看成不进位运算，也就是我们十进制中满十进一，现在满十，但不进一了。其次，电脑系统运算是二进制运算。那么通过上面的异或运算，结果是两个数异或的结果，也就是 a ^ b。那么这两个数转为二进制的话，必然至少有一位是不同的，也就是其中一个为1，一个为0。

        那么现在我们得到了第一次异或的结果a ^ b，接下来只需要找出其中一个元素，那另一个就能找出来。上面说了，它俩至少有一位不相同，那我就假设第n位不同，怎么确定这第n位呢？这里我取a ^ b的二进制的最右边的1，假设这一位不同。那么异或运算这一位为1的。

  public static int[] selectOddTimesNum2(int[] nums) {
    int[] temp = new int[2];
    int result = 0;
    for (int num : nums){
      result ^= num;
    }
    // 取出最右边的1
    int rightOne = result & (~result + 1);
    int other = 0;
    for(int num : nums){
      // 只要这一位为1的，就进行异或
      if ((num & rightOne) == 1){
        other ^= num;
      }
    }
    // 结果就是其中一个数
    temp[0] = other;
    // 再异或一下，就是另一个数
    temp[1] = result ^ other;
    return temp;
  }

        可以看到取出一位不同位就能计算出其中一个元素，但是这样下去，如果继续增加出现的元素个数，无疑计算会越来越大，还不如使用HashMap来记录。这里只是讲解一下异或的应用，以及异或的缺点，在实际问题解决中，根据不同场景使用异或，或许能达到意想不到的结果。