数组中只出现一次的数字

题目：一个整型数组里，除了两个数字以外，其他数字都出现了两次，请写程序找到这两个只出现一次的数字。要求：时间复杂度为O(n),空间复杂度为O(1).

分析：看到这题，首先要明白，这是求两个数字。还要明白其要求，空间复杂度和时间复杂度。如果没有这些约束我们可以有很多方法解，如Hash、逐次遍历等。

当常规方法无法满足要求，我们就可以使用一个神奇的工具：位运算。

我们首先看看当只是一个数字是只出现一次怎么求解。

异或运算有一个性质：任何一个数字异或自己都等于0。多个数字依次做异或运算，相同的数字会抵消。看下例：

例如一个输入数组：{1,2,3,2,3}

0001

0010 异或得到：

0011

0011 异或得到：

0000

0010 异或得到：

0010

0011 异或得到：

0001

看到木有，数组里面相同的数字都抵消了。这里只是针对只有一个数字是只出现一次的。其他情况不成立。

但是本题里有两个，直接这么做事不成立的，怎么办？我们想到，用位整个数组运算以后得到的结果有什么作用呢？很明显，出现两次的数在位运算后抵消了，那么其实就是两个只出现一次的两个数做的位运算。例如：

{1,2,2,3}

0001

0010 异或得到：

0011

0010 异或得到：

0001

0011 异或得到：

0010 这个结果和 1^3=0010是一样了，验证了上面的理论。

好了，有了这个有用的信息，那么我们就可以用这个结果中位为1来区分成两组数据，很显然这两组数据中都分别只包含一个只出现一次的数字（作的异或运算嘛，=1，说明它们是不同的。）。然后再用最开始讲到的方法去做就OK拉。代码贴上来：

bool Judge(int pData, int BitIndex)
{
    pData = pData >> BitIndex;
    return (pData & 1);
}
void FindOnlyOneNumbers(int pData[],int length, int &num1,int &num2)
{
    //1.异常检测
    if (pData == NULL || length < 2)
        return;

    //2.求出区分位
    int resultExclusive = 0;
    for (int i = 0; i < length; i++)
        resultExclusive ^= pData[i];      //假如只有一个数字是只出现一次，那么这个结果就是这个数字，如果两个的话，那么这个数字中位为1即是只出现一次的两个数的不同位。

    //3.接下来为了区分两者，我们寻找区分位最右边为1的位
    int indexCount = 0;
    while (resultExclusive&1==0&&indexCount<=8*sizeof(int))
    {
        resultExclusive >> 1;
        indexCount++;
    }

    //4.然后按照区分位的不同，将pData分成两组,这里没必要用两个数组保存，直接进行用位运算分别计算两个数就ok了
    int resultExclusive1 = 0, resultExclusive2 = 0;
    for (int i = 0; i < length; i++)
    {
        if (Judge(pData[i],indexCount))
            resultExclusive1 ^= pData[i];
        else
            resultExclusive2 ^= pData[i];
    }
    num1 = resultExclusive1;
    num2 = resultExclusive2;
}