Single Number III

题目：

Given 2*n + 2 numbers, every numbers occurs twice except two, find them.

分析：

第一遍循环用xor操作找到这两个数字的xor结果；然后因为这两个数不相等，那么相同为零，相异为一的原则下，这个xor结果中任何一个=1的bit就说明是这两个说相异的bit。然后找到任何一个这样的=1的bit，然后第二遍循环，&这个bit得0的一组，&这个bit得1的是另一组，就刚好得知这两个不同的数了。

注意，取得任意=1 bit的方法是temp &= -temp，在不包含越界的情况下，int 4是00000100而int -1是11111100，就是把前面的都换成1。所以就得到了=1的bit。

解法：

class Solution {
public:
    /**
     * @param A : An integer array
     * @return : Two integers
     */
    vector<int> singleNumberIII(vector<int> &A) {
        // write your code here
        int temp = 0;
        for (int i = 0; i < A.size(); i++) {
            temp ^= A[i];
        }
        temp &= -temp;
        vector<int> res = {0, 0};
        for (int i = 0; i < A.size(); i++) {
            if ((temp & A[i]) == 0) {
                res[0] ^= A[i];
            } else {
                res[1] ^= A[i];
            }
        }
        return res;
    }
};