40、剑指offer--数组中只出现一次的数字

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

解题思路：一个数异或它本身等于0。也就是说对于一个数组，其他数字均出现两次，只有一个数字出现一次，这些数字异或后，就是那个只出现一次的数字。

本题中有两个数字出现了一次，因此应该想办法将这两个数字分在两个数组里，这样每个数组得到的结果就为这两个数字。

因此先将所有数字异或一遍 = a^b  然后在结果中找到第一位为1的位置，记做第n位。然后我们按照第n位为1和不为1将数组分成两部分，a、b肯定分在两部分中。相同的数字肯定分在一个数组中。所以对每个数组中数字异或，就可求出a、b

class Solution {
public:
    //找到最右边为1的位
    unsigned int FindFirstOf1(int num)
    {
        int index = 0;
        while(((num & 1)==0) &&(index < 8*sizeof(int)))
        {
            num = num>>1;
            ++index;
        }
        return index;
    }
    bool IsBit1(int num,unsigned int index)
    {
        num = num>>index;
        return (num&1);
    }
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        if(data.empty())
            return;
        int length = data.size();
        int resultExclusiveOR = 0;
        for(int i=0;i<length;i++)
        {
            resultExclusiveOR ^= data[i];
        }
        unsigned int indexOf1 = FindFirstOf1(resultExclusiveOR);
        *num1 = *num2 = 0;
        for(int j=0;j<length;j++)
        {
            if(IsBit1(data[j],indexOf1))
            {
                *num1 ^= data[j];
            }
            else
            {
                *num2 ^=data[j];
            }
        }
    }
};