刷题 - 数组中只出现1次的两个数

题目描述：

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

预备知识：

对于一个整数数组，首先我们先分析一个简单的情况：假定数组中只有一个数据出现1次，其他数据都出现了两次，如何找到这个只出现1次的数据？

位运算中，两个数的异或运算规则是：二进制位相同返回0，不同返回1，由此两个相同数据的异或值为0，任何数据与0的异或还为原值。如1100^1100=0000，1010^0000=1010。

所以可以很快想到，上面求唯一一个出现1次的数据就可以对数组中的数据全部异或，得到的结果就是只出现1次的数据。

本题思路：

通过预备知识的内容，回到本题，本题的数组中由两个只出现1次的数据，其余数据都出现2次，设这两个数据是A和B。

首先还是对数组中所有的数据进行异或处理，结果是A^B，我们分析一下这个结果：结果的二进制表示中，所有的0代表了A和B二进制相同的位，1代表了A和B二进制不同的位。

那么我们就可以以A^B二进制结果中为1的位对原数组进行划分，例如A^B=0000100，倒数第3位为1，遍历原数组中所有的数据，其二进制表示中第3位为0的划分为1组，第3位为1的划分到一组。

可以想到划分后的这两组，一定都是一堆出现2次的数据和1个出现1次的数据，由此就可以用预备知识中的处理方法得到结果了。

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        if(data.size()<2)
            return ;
        int size=data.size();
        //数组中所有元素异或，结果为两个不同值的异或结果（同值异或结果为0）
        int temp=data[0];
        for(int i=1;i<size;i++)
            temp=temp^data[i];
        if(temp==0)
            return ;
        //找到异或结果二进制表示中为1的最低位，该位代表了原数组中不同的两个值在此位不同
        int index=0;
        while((temp&1)==0){
            temp=temp>>1;
            ++index;
        }
        //以上面的index位的值将原数组划分两组，不同的值肯定被划分到不同的组，同值元素肯定划分到同组
        *num1=*num2=0;
        for(int i=0;i<size;i++){
            if(IsBit(data[i],index))
                *num1^=data[i];
            else
                *num2^=data[i];
        }
     }
    bool IsBit(int num,int index){
        num=num>>index;
        return (num&1);
    }
};