用异或找到数组中不重复出现的数字

找一个数很简单，但找两个数呢？

最近做leetcode上面的题目的时候，遇到了一个面试题，需要找到数组中两个只出现过一次的数（其余数均出现过两次），感觉很有意思，简单记录一下。

基本知识

异或（xor）是一种非常常见的位运算，其计算特点是“相同为0，不同为1”，计算符号是⊕，有时也用a^b表示。一般使用异或时会用到下面的规律：

1. 任何数和本身的异或为0
2. 任何数与0的异或结果是自身
3. 异或满足交换律，a^b^c = c^b^a

有了这些基本概念之后就能尝试去解决这个题目了。

求解思路

关于如何用异或查找到数组中唯一出现的数字（其他数字均出现过两次），有一个很简单的解法：设置初始值为0，然后将这个值与数组中的所有数进行异或运算，最终的结果就是唯一出现的数字。

看到这个题目，最开始想到的做法是亦或，但仔细考虑之后发现由于有两个数字都只出现了一次，所以对整个数组进行异或的最终结果是两个只出现过一次的数的异或。很明显这样不能解决问题，但如果能够把整个数组划分为两组，确保两个只出现过一次的数不在同一组内，并且相同的数一定在同一组当中这一条件，对两组内容各进行一次异或便能得到最终的结果。

但是怎么划分呢？这里有一个很巧妙的做法，由于不相等的两个数进行异或之后一定有一位的值为1，可以通过这点将所有数据划分为两组：对整个数组的数据进行判断，将该位为0的数据分到一组，该位为1的数据分到一组。这样便能满足相同的数都会被分在一组当中，两个只出现过一次的数也会被分到不同的两组当中。

在代码实现的过程中，并不需要显式的分组，只要对指定位进行判断，分别与两个不同的数进行异或即可。另外找到二进制中为1的某一位可以通过将1逐步左移的方式实现。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int tmp = 0;
        for(int i = 0; i < nums.size(); i++){
            tmp ^= nums[i];
        }

        // 找到值为1的二进制位
        int index = 1;
        while(!(tmp&index)){
            index <<= 1;
        }

        int num1 = 0, num2 = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] & index){
                num1 ^= nums[i];
            }
            else{
                num2 ^= nums[i];
            }
        }
        return vector<int>{num1, num2};
    }
};

其他

在这个题目的题解区看到了别人总结的力扣位运算题目：136、137、260、645，感兴趣可以深入了解一下。