Single Number III

题目来源
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.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [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(nlogn)时间。题目要求的是O(n)时间O(1)空间。哈希怎么利用现有空间来完成呢？
  如果用异或操作的话，出现两次的确实可以消掉，但是出现一次的两个元素没法求。
  看了下tags也是提示的位操作，但是怎么用还是想不出来。
  然后就看了答案，就是利用位操作然后得到两个数的异或结果，再找出第一个不一样的位，将所有的数分为两组分别进行异或操作。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int n = nums.size();
        vector<int> res{0, 0};
        int diff = 0;
        for (int i=0; i<n; i++)
            diff ^= nums[i];
        diff &= -diff; //重点在这里，找到第一个不同的位
        for (int i=0; i<n; i++) {
            if ((diff & nums[i]) == 0)
                res[0] ^= nums[i];
            else
                res[1] ^= nums[i];
        }
        return res;
    }
};