首先，我们先考虑简单的情况下，就是只有一个出现一次的数字，其余数字都出现2次，这样我们可以采用一种很巧妙的方法：“异或”。
void findNumAppearOnce(int date[],int length,int &num) { if(length<2) return; num=0; for(int i=0;i<length;i++) { num ^=date[i]; } }
然后，我们考虑有两个出现一次的数字的情况。同理，我们依然采用上面的方法，由于两个出现一次的数字肯定不相同，最后的结果就是这两个数字的异或结果，因而这个结果必不为0，至少存在一位为1（就是由于这两个出现一次的数字的同一位上：一个为0，一个为1）。因此，我们首先找到一位不为0的二进制位n，把所有的数据按照此位划分为两组，这两组的第n位分别为0和1，这样就能保证每组中必然包含一个仅出现一次的数字。
源代码参考：剑指Offer
代码如下：
#include <iostream> using namespace std; //从左向右移动，获取第一个为1的位数 unsigned int FindFirstBitIs1(int num) { int indexBit = 0; while(((num&1)==0)&&(indexBit<32)) { num=num>>1; ++indexBit; } return indexBit; } //对数据分组 bool IsBit1(int num,unsigned int indexBit) { //移动相应的位数，让相对位置移动到最后一位上 num=num>>indexBit; //例如：1001101 ^ 0000001 这样的情况为0 ; 1010110 ^ 0000001 这样的情况为1 return (num & 1); } void findNumAppearOnce(int date[],int length,int &num1, int &num2) { if (length<2) return; //get num1^num2 int resultExclusiveOR = 0; for (int i=0;i<length;i++) resultExclusiveOR ^=date[i]; unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOR); num1=0;num2=0; for (int j=0;j<length;j++) { if(IsBit1(date[j],indexOf1)) num1 ^=date[j]; else num2 ^=date[j]; } } int main(int argc,char* argv[]) { int a[6]; for(int i=0;i<6;i++) cin>>a[i]; int num1,num2; findNumAppearOnce(a,6,num1,num2); cout<<"num1="<<num1<<endl; cout<<"num2="<<num2<<endl; return 0; }
本文转自cococo点点博客园博客，原文链接：http://www.cnblogs.com/coder2012/archive/2012/11/01/2750249.html，如需转载请自行联系原作者
