一组数中，只有两个数出现了一次，剩下的数都是成对出现，找出这两个数

今天在做题的时候，碰到这样一道题：一个数组中除了两个数字之外，其余数字均出现了两次，如{1,2,3,4,5,3,2,1}。查找这两个只出现一次的数字，要求时间复杂度为o（n），空间复杂度为o（1）。
解题思路：
在解这道题时，首先要了解与（&），或（|），异或（^）的基本用法:
（1）0&0=0；0&1=1；1&1=1；
（2） 0|0=0；0|1=1；1|1=1；
（3） 1^1=0 ; 0^0=0 ; 0^1=1；
接下来就是解这道题的思路啦：
（1）首先，我们需要排除其他出现两次的数，所以我们可以将这组数中的所有数进行一遍异或，这样得到的结果就是两个出现一次的数的异或结果；
（2）因为这两个单一出现的数不相同，所以结果的二进制中肯定至少有一个1，那么这就是突破口，记录该位为pos，这说明在该位上，这两个不同的数，一定有一个为1，一个为0 ；将该数组在该位上是否为一分为两个部分，第一个子数组中每个数字的第pos位都为1，而第二个子数组的每个数字的第pos位都为0。
（3）将分为两部分的数组分别进行异或，最终得到的结果就是这两个单独的数字；
（4）这里的并不是直接分组，而是按照条件查找，边查找编异或。

下面就是具体的代码实现部分了：
具体代码：

void FindTwoNum(int*array, int n)
{
    int num1 = 0;
    int num2 = 0;
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum ^= array[i];//两个只出现一次的数的结果
    }
    int pos = 0;
    while ((sum & 1 )== 0)
    {
        sum = sum >> 1;//找出第一次出现1的位置---也就是分离数据的入口
        pos++;//pos 标志对应1的位置
    }
    for (int i = 0; i < n; i++)
    {
        if ((array[i] >> pos) & 1)//1与array[i]的第pos位相与，来进行分组
        {
            num1 ^= array[i];
        }
        else{
            num2 ^= array[i];
        }
    }
    cout << num1 << " "<<num2 << endl;
}
int main()
{
    int arr[] = { 1, 2, 3, 1, 2, 3, 4, 5 };
    int size = sizeof(arr) / sizeof(arr[0]);
    FindTwoNum(arr, size);
    system("pause");
    return 0;
}

运行结果：

这样就找到结果啦，如果是找只出现一次的一个数据的话，那就很简单了，因为0与任何数异或都得该数，所以只需要将数组中的元素异或一遍得到的结果就是我们要的答案了。