算法题：找出整数数组中两个只出现一次的数字

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

---

分析：这是一个很新颖的关于位运算的题目。

首先考虑这个问题的一个简单版本：一个整数数组里除了一个数字之外，其他的数字都出现两次，请写程序找出这个只出现一次的数字。

这个问题的突破口在哪？题目中数组的性质是只有一个整数出现一次，其他的都出现两次。这样的话就使我们想到了异或运算的性质：任何一个数字按位异或它自己都等于0，因为异或的性质是相同为0不同为1。也就是说如果从头到尾依次按位异或数组中的每一个整数，那么最终的结果刚好是那个只出现一次的数字。那么两两相同的整数在异或的过程中等于0抵消了。同时0与任何整数按位异或的结果都是这个整数本身。

根据上面的这个简单为题的解决方案，回到题目中的问题。如果能把原数组分为两个子数组，在每个子数组中包含一个只出现一次的数字，而其他的数字都出现两次。如果能够这样拆分原数组，那么问题就变成在拆分的两个数组中分别寻找这两个只出现一次的数字。

那么剩下的问题就是根据什么条件拆分数组？

解决的办法是：把所有的整数依次做按位异或运算，因为其他的有配对的整数按位异或的结果等于0，这样最后异或的结果就相当于把这两个只出现一次的整数异或，所以想要区分这两个整数，可以从它们异或的结果上区分。在它们异或的结果中找一个为1的bit位，即为第N位。根据异或的运算原理，那么这两个数的第N位肯定一个为1一个为0。根据第N位是1或者0把整个数组分成两组。就能满足每个子数组包含一个只出现一次的整数，其他的数字两两配对的出现在不同的子数组中。

---

算法步骤：

（1）依次按位异或数组中的每一个整数，得出异或运算的结果。

（2）找到异或运算结果的二进制形式中，最低位的1对应的下标值。把这个位作为区分两个整数的标准。

（3）根据区分标准，把整个数组分成两个子数组，分别求它们的异或运算值，得到两个运算结果就是要求的两个只出现一次的整数。

---

函数声明：

bool FindTwoSingleNums(int nums[], int nLength, int &a, int &b);
bool IsBit1(int num, uint indexBit);
uint FindFirstBitIs1(int num);

---

代码实现：

bool FindTwoSingleNums(int nums[], int nLength, int &a, int &b)
{
    if(nLength < 2)
    {
        return false;
    }

    int resXOR = 0;
    for(int i = 0; i < nLength; i++)
    {
        resXOR ^= nums[i];
    }//for

    uint index = FindFirstBitIs1(resXOR);
    for(int i = 0; i < nLength; i++)
    {
        if(IsBit1(nums[i], index))
        {
            a ^= nums[i];
        }
        else
        {
            b ^= nums[i];
        }

    }//for
}//FindTwoSingleNums()

//找到一个数的最低位的1的下标值，下标从零开始
uint FindFirstBitIs1(int num)
{
    uint index = 0;
    uint maxIndex = sizeof(num) * 8;
    
    //注意运算符的优先级
    while(((num & 1) == 0) && (index < maxIndex))
    {
        num >>= 1;
        ++index;
    }//while

    return index;
}//FindFirstBitIs1()

//下标从0开始，所以向右移动的位数为indexBit
bool IsBit1(int num, uint indexBit)
{
    num >>= indexBit;
    return num & 1;
}//IsBit1

PS：关键词—>相同数字按位异或结果为0，并根据所有元素异或结果第一个出现1的位置（出现1的最低位）把数组分成两部分。