2013小米笔试题--异形数

题目：

一个数组里，除了三个数是唯一出现的，其余的都出现偶数个，找出这三个数中的任一个。比如数组元素为【1, 2,4,5,6,4,2】，只有1,5,6这三个数字是唯一出现的，我们只需要输出1,5,6中的一个就行。

分析：一般这样的题目采用异或的办法来去重，但是这里有三个不同的，那么这个三个两两异或，肯定会出现2个异或的结果低位第一个为1的位置相同，另外一个不同！！！！这个自己推导。根据这个结论，我们就有办法取出其中一个不同的数。将这3个异或后的结果分别取最低位中1的位置。然后再将这3个结果都异或，得到其中不同的那个，那么现在用所有原始数据都相互异或后再分别与每个原始数据异或，取最低位为1的位置 ，如果跟上面相同，那么输出这个数；

代码如下：

int lowbit(int x)//输出x 的低位中的第一个1 位置  {      return x&~(x-1);  //x 与 负x 相与 找到  }  void find(int *arr,int len)  {      int xor = 0;      int flips = 0;      for (int i=0;i<len;++i)          xor ^= arr[i];      // 三个数两两的异或后lowbit有两个相同，一个不同，可以分为两组 //正确      for(int i=0;i<len;++i)          flips ^=lowbit(xor ^ arr[i]);      // 表示的是：flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)        int b = 0;              // 假设三个只出现一次的其中一个数为b      for(int i=0;i<len;++i)          if(lowbit(xor ^ arr[i]) == flips)              b = arr[i];  //这里要注意一定要遍历完，不能相等取出arr[i]就返回，因为有可能其他出现2次的数干扰lowbit，使之相等，从而返回错误的数据    cout<<b<<endl;      //////test/////////////////////////////////////////////////////////////////      //int arr[] = {1,5,7,1,5,7,12,11,13}; //共 11 个       //find(arr,9);      //////////////////////////////////////////////////////////////////////////  }