刷题：数组中只出现一次的数字

• 题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
• idea：异或具有交换律，结合律。因此一个数组中假如只有一个数a出现一次时其他数都出现两次时，异或会得到a。可以试想一下按二进制展开所有数，所有单独对第一位进行异或（设a第一位为1），那么第一位全部异或肯定得1（其他数都出现两次，那么必然有2n+1（1是a）个数出现1, 2m个数出现0）。其他位亦然。因此假如只有一个数出现一次时对数组进行逐个异或得到a。假如两有个数（a和b）出现一次时，那将全部数异或结果得 $a\oplus b$a⊕b，由于a和b不等，那么
  $x = a\oplus b \ != \ 1$x=a⊕b != 1
  因此只需要找到x中其中一位不为1的位，将x与所有数进行异或，必然有一半数与x异或得0一半异或得1。遍历原来数组时，若与x异或得1的数，则与num1进行异或，否则与num2进行异或。最后num1就是a，num2就是b
• code

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        vector<int>::iterator iter;
        int x = 0;
        if (data.size() == 0) return;
        for (iter = data.begin(); iter != data.end(); iter++){
            x ^= *iter;
        }
        unsigned int flag = 1;
        if (x == 0) return;
        while(!(flag&x)){
            flag = flag<<1;
        }
        
        *num1 = 0, *num2 = 0;
        for (iter = data.begin(); iter != data.end(); iter++){
            if ((*iter)&flag) *num1 = (*num1) ^ (*iter);
            else *num2 = (*num2) ^ (*iter);
        }
        
    }
};