找出數組中一個(兩個，三個)隻出現一次的數字

面試時候碰到這麼一道題，給定一個數組，裡面的數字都是兩兩出現，但是假如現在裡面有一個(兩個，三個)隻出現一次的數字，請問你怎麼找出來他們。

1. 第一種情況，找出裡面一個隻出現一次的數字，這個比較簡單，因為裡面的數字都兩兩出現，我們可以考慮使用異或(^)，0與任何數異或都得到那個數本身，同時兩個相同的數異或結果為0，這樣将所有數字進行異或，可以發現結果為那個隻出現一次的數字。

*void FindOneDiffer(int* num,int N)
{
	int i;
	int notSame=0;
	for(i=0;i<N;i++)
	{
		notSame^=num[i];
	}
	if(notSame)//判斷輸入中是否隻有一個不相同的
	    cout<<notSame<<endl;
}
           

2. 第二種情況，找出裡面兩個隻出現一次的數字，說明其他的數字都是兩兩出現，隻有數字A,B是隻出現了一次，(A!=B)，這時候考慮先将所有數字都異或，得到X=A^B，此時X不為0，因為A!=B，那麼我們可知對于X的二進制數必定有一位為1，此時我們找出X的從右向左數第一個不為0的位數，即為m，那麼我們可知A和B中必有一個第m位為1，另一個為0，這是因為如果兩個第m位都為0或者都為1，那麼必然會使得X的第m位為0，是以我們可以根據這個第m位是否為1，将整個數組劃分為兩部分，一組是第m位為1，另一組是第m位為0，然後分别對兩組裡面的數字進行異或，可得這兩個數字。

void FindTwoDiffer(int* num,int N)
{
	int i,j,s1=0,s2=0;
	int tmp=0;
	for(i=0;i<N;i++)
	{
		tmp^=num[i];
	}
	i=1;
	while(!(i&tmp))
	{
		i<<=1;
	}

	for(j=0;j<N;j++)
	{
		if(i&num[j])
			s1^=num[j];
		else
			s2^=num[j];
	}
	cout<<s1<<','<<s2<<endl;
}
           

3. 第三種情況是找出裡面三個隻出現一次的數字，說明其他的數字都是兩兩出現，隻有數字A,B,C是隻出現了一次，我們再次要考慮的仍是如何将這三個數字分成兩組，第一組有一種特征，第二組有另一種特征，這樣就可以将這三個數字分成兩組，在接下來對裡面有兩個隻出現一次的數字的數組使用第二種情況的辦法就可以将裡面兩個數字分開，這樣就可以分開這三個數字，那麼現在的關鍵就是要找到能将三個數字分成兩組的特征。

在此，我們首先考慮2中的方法，X=A^B^C，但是在這裡X既可為0(A=2,B=5,C=7),也可以不為0，是以，我們無法根據X的第m位是否為1将其劃分，是以，考慮另一種辦法，将X再與其他所有數字異或，可得a=X^A=B^C，b=X^B=A^C，c=X^C=A^B，X^D,X^D,X^E,X^E...，此時可以發現x=a^b^c=(B^C)^(A^C)^(A^B)=0，

由于a,b,c各不為0，并且互不相等。(由于A,B,C各不相等，是以a,b,c各不為0)(假設a,b相等，那麼0=a^b=(B^C)^(A^C))=A^B，由于A與B不相等，那麼可知此式不相等，假設不成立，是以a,b,c互不相等) 。

我們定義一個函數，函數f(n)表示n的二進制表示時，從右往左數第一個位為1，其他所有位為0的數，比如f(4)=f(0x100)=4;f(n)=n&(-n);是以，f(a)，f(b)，f(c)都不為0，因為a,b,c都不為0，此時考慮f(a)^f(b)^f(c)，由于f(a)和f(b)中都隻有一位為1，那麼f(a)^f(b)的結果要麼都為0，要麼有兩個1，而f(c)的結果中隻有一位為1，是以，f(a)^f(b)^f(c)的結果不為0，此時假設f(a)^f(b)^f(c)的二進制中至少有1位為1，設為第m位，那麼我們可知a,b,c中要麼有一個第m位為1，要麼有三個第m位為1。

這裡我們假設a=X^A，b=X^B，c=X^C的第m位都為1，那麼可知A，B，C的第m位都與X的第m位相反，首先假設A,B,C的第m位都為0，那麼X的第m位将為1，由于X=A^B^C，那麼對于X而言，第m位由A,B,C的第m位異或而來，應該為0，但是卻與假設沖突，是以假設不成立。其次假設A,B,C的第m位都為1，那麼X的第m位将為0，由于X=A^B^C，那麼對于X而言，第m位由A,B,C的第m位異或而來，應該為1，但是卻與假設沖突，是以假設不成立，是以可知a,b,c中隻有一個第m位為1，其他兩個第m位為0，這樣我們就可以将三個數首先劃分為兩組，然後再繼續根據情況2進行劃分。

int isFirstBitof1(int value)
{
	return (value&-value);
}
void FindThreeDiffer(int* num,int N)
{
	int i,x=0;
	for(i=0;i<N;i++)
		x^=num[i];

	int firstbit1=0;
	for(i=0;i<N;i++)
	{
		firstbit1^=isFirstBitof1(x^num[i]);
	}
	firstbit1=isFirstBitof1(firstbit1);

	int first=0;
	for(i=0;i<N;i++)
	{
		if(firstbit1==isFirstBitof1(x^num[i]))
		{
			first^=num[i];
		} 
	}
	printf("%d",first);
	cout<<',';
	for(i=0;i<N;i++)
	{
		if(first==num[i])
		{
			int temp;
			temp=num[N-1];
			num[N-1]=num[i];
			num[i]=temp;
		}
	}
	FindTwoDiffer(num,N-1);
}