面试题56 - I. 数组中数字出现的次数

1. 位运算

异或^：相同为0，不同为1.
假如只有一个不成对出现的数字，则基于这个性质，成对出现的数字异或起来得到全0，再异或上这个数字，结果就是这个数字，所以只需要全部异或起来就可以了。（妙啊

如果有两个不成对出现的数字a, b，则全部异或得到a^b，并不是想要的答案。
我们可以想到，如果把数据分为两组，1组有a和一部分成对的数据，2组有b和剩余部分成对的数据，则1组全部异或得到a，2组全部异或得到b。
现在的问题是如何分为两组。
a^b得到的结果中，有的位是0，有的位是1，而1的位说明a和b在该位上不相等。
所以可以取任意一个为1的位，将该位为1的数据分到1组，该位为0的数据分到2组。
这样1和2一定可以分开。
而由于成对出现的数据在同一位上一定是相同的，所以也可以被分到同一个组中，这样分组就完成了。

实际上也并不需要显式地分成两部分。
只要在循环的时候判断某一位是01，然后对应的异或到相应位置就可以了。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int n = nums.size();
        if (n == 2)
            return nums;
        
        int allXor = 0;
        for (int i = 0; i < n; i++)
            allXor ^= nums[i];
        
        int loc = 1;
        while ((loc & allXor) == 0)
            loc <<= 1;
        
        int a = 0, b = 0;
        for (int i = 0; i < n; i++) {
            if ((nums[i] & loc) == 0)
                a ^= nums[i];
            else
                b ^= nums[i];
        }

        return {a, b};
    }
};