一刷剑指offer（40）——数组中只出现一次的数字

题目：
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字，要求时间复杂度为O（n），空间复杂度为O（1）。例如输入{2，4，3，6，3，2，5，5}，输出4和6。

异或的性质：

若A!=B，则A xor B=1；若A==B，则A xor B=0。

即任意一个数字，异或它自己都为0。

先不考虑数组中有两个只出现一次的数字，先考虑数组中仅有一个只出现一次的数字。

如果我们设置一个遍历result=0，再从头到尾依次异或数组中每一个数字，那么最终的结果刚好是那个只出现一次的数字，因为那些成对出现两次的数字全部在异或中抵消了。

接下来要处理的就是如何将原数组分成两个子数组，使得每个子数组包含一个只出现一次的数字。

由于这两个数字肯定不一样，因此异或的结果肯定不为0，也就是说这个结果数字的二进制表示中至少有一位为1。

我们在结果数字中找到第一个为1的位置，记为第n位。

现在我们以第n位是否为1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第n位都是0，而第二个子数组中每个数字的第n位都是0。

可以知道，出现了两次的数字肯定分配在一个子数组里。

但是看到这里，我还是有一点疑惑，这样的标准，真的能把两个不一样的且只出现一次的数字放在两个子数组里吗？比如假如1和5只出现了一次，那么1：001，5：101，这样不还是在一个子数组里吗？

先看下面的代码，就会知道为什么可以这样做。

//在整数num的二进制表示中找到最右边是1的位
unsigned int FindFirstBitIs1(int num)
{
    //从第0位开始检验
    int indexBit=0;
    //num&1==0：说明num的最低位！=1
    while(((num & 1)==0) && (indexBit<8*sizeof(int)))
    {
        //num右移一位
        num=num>>1;
        ++indexBit;
    }
    return indexBit;
}

bool IsBit1(int num,unsigned int indexBit)
{
    num=num>>indexBit;
    return (num&1);
}

void FindNumsAppearOnce(int data[],int length,int* num1,int* num2)
{
    if(data==NULL || length<2)
        return;
    int resultExclusiveOR=0;
    //若有1和5仅出现一次，那么最低位相同的1，异或为0，只剩下5的较高位为1
    for(int i=0;i<length;++i)
        resultExclusiveOR^=data[i];
    unsigned int indexOf1=FindFirstBitIs1(resultExclusiveOR);
    *num1=*num2=0;
    for(int j=0;j<length;++j)
    {
        if(IsBit1(data[j],indexOf1))
            *num1^=data[j];
        else
            *num2^=data[j];
    }
}