学步园

61.找出数组中两个只出现一次的数字
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度是 O(n)，空间复杂度是 O(1)。

/*
61.找出数组中两个只出现一次的数字
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度是 O(n)，空间复杂度是 O(1)。

异或处理 a^a=0 
假如这两个数为a和b，那么将所有的数异或得到的数必定为a^b。
由于a和b不相等，那么a^b!= 0，也就是说在a^b中必定至少有一位为1，对应位上a与b不一样，
所以根据这一位，我们可以将a和b分开，并将数分成两组。

我们在结果数字中找到第一个为1的位的位置，记为第N位。
现在我们以第N位是不是1为标准把原数组中的数字分成两个子数组，
第一个子数组中每个数字的第N位都为1，第二个子数组的每个数字的第N位都为0。
所以把第N位为1的异或 结果num1， 把第N位为1的异或 结果num1，
*/
#include<iostream>
using namespace std;

void FindTwoDifferentNum(int a[],int n,int &num1,int &num2)
//返回数组a中两个只出现一次的数字num1和num2
{
	int i,ans=0,k;

	for(i=0;i<n;i++)//先全部异或，其结果是这两个只出现一次的数字的异或
		ans^=a[i];
	
	num1=ans;//保存ans 
	
	k=0;//k表示的是第N位 a和b的不同 
	while((ans&1)==0)
	{
		ans>>=1;
		k++;
	}

	ans=num1;
	for(i=0;i<n;i++)//第n位不同 将全为1的异或 得到num1 
	{
		if((a[i]>>k)&1)
			num1^=a[i];
	}
	num2=num1^ans;//num1和全部异或的结果异或，就是num2
}

int main()
{
	int a[]={1,5,3,4,2,3,1,5,4,6};
	int num1, num2;
	FindTwoDifferentNum(a,sizeof(a)/sizeof(int),num1,num2);
	cout<<num1<<"  "<<num2<<endl;
}