Single Number III

又是一道single number题目，这类题目一般都是依赖位操作，先给出题目：

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]
Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

这题已经说了，必须是线性的时间复杂度，也就是时间复杂度是O(N)，同时空间复杂度被限制为了O(1)，也就是hashmap之类的就不能用了，假如用map这种东西，这种题目就没什么意思了。

做过single number这题的人应该知道，那题比较简单，所有数字都是两两出现的，除了一个。由于异或操作满足交换律，所以两个相同数字的异或结果是0，而0与任何数字异或的结果都是那个数字本身，所以最后就剩下那个孤零零的数字了。

这题在single number的基础上增加了复杂度，有2个数字单独出现了，所以全部异或的操作肯定不能使用。假如我们全部异或了，我们得到的结果是那两个孤零零数字异或的结果，好像对这题没啥用。但是仔细想想呢，有了两个数字单独异或的结果，我们至少可以知道，这个结果肯定在某个比特位上不为0，我们以这个比特位为1，其余为0产生一个mask，用这个mask可以知道数字上这个位是否为0。

有这个mask有什么用呢？我们可以知道，假如我们把这个mask和当前数组里所有数字进行异或处理，那么肯定可以分为2组，1组包含某个单独的数字1，另一组包含单独的数字2。有这个就好办了，因为其与在别分割为组的数字们，他们肯定都是和另一个和它相同的数字成对出现的，它的某一位与mask的与结果，肯定和和它相同的数字相同。

所以这个题目又转为了single number这题了，该怎么解不用解释了吧。下面贴一个解法：

vector<int> singleNumber(vector<int>& nums) {
    int xorn = 0;
    for (auto v : nums) {
        xorn ^= v;
    }
    int flag = xorn ^ (xorn & (xorn - 1));
    vector<int> res(2, 0);
    for (auto v : nums) {
        if ((flag & v) == 0) {
            res[0] ^= v;
        } else {
            res[1] ^= v;
        }
    }
    return res;
}