数组中只出现一次的数字

题目描述

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

 

思路：由于性质：a ^ a = 0 ; 0 ^ n = n; 由于数组中有两个数字只出现一次，所以：

1.  将数组中的所有数字 ^，得到的数是这两个数的  ^，

2.  找到两个数 ^ 结果的最后一个1，即为两个数不相同的位

3.根据该位分组，则每一组中只有一个只出现一次的数字。

4.将两个组，分别 ^ ,则分别得到要求的两个数。

代码：

      void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int len = data.size();
        int num = 0;
        for(int i = 0; i < len;i++)
        {
            num = num^data[i];
        }
        int tmp = 1;
        while((num&tmp) == 0)
        {
            tmp = tmp<<1;
        }
        int arr1[500],arr2[500];
        int id1 =0 ;
        int id2 = 0;
        for(int i = 0; i < len;i++)
        {
            if((data[i] & tmp) == 0)
                (*num1)^=data[i];
            else
                (*num2)^=data[i];
        }
    }