学步园

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

思路：通过位与运算能够求出数组中只出现1次的2个数位与的结果result，按位求出在result中1出现的第一个位置，因为在这个位置上，2个不同的数一个肯定一个为1，一个为0，通过这个方法把整个数组分为2个部分，一个是这个位置为1的，一个是这个位置为0的，获取这个位置数字为1的数相与即可得到第一个只出现1次的数，第二个数类似。

#include <iostream>
using namespace std;
//获取某个数在a的位置上是否为1
bool innone(int num,unsigned int a)
{
	num=num>>a;
	return(num&1);
}
//求取num中第一个二进制位上为1的位置
int whereposition(int num)
{
	int index=0;
	while (((num & 1) == 0) && (index < 32))
	{
		num = num >> 1;
		++ index;
	}
	return index;
}
//计算出2个不同的值
void cout2othernumindata(int data[],int length,int &num1,int &num2)
{
	if (data==nullptr)
	{
		return;
	}
	int result=0;
	for (int i=0;i<length;++i)
	{
		//位与运算得到2个不同的数的与值
		result=result^data[i];
	}
	int index=whereposition(result);
	for (int i=0;i<length;++i)
	{
		if (innone(data[i],index))
		{
			//第一个不同的数
			num1=num1^data[i];
		}
		else
		{
			//第二个不同的数
			num2=num2^data[i];
		}
	}
}
int main()
{
	int data[10]={1,2,3,4,5,4,3,2,6,1};
	int num1=0;
	int num2=0;
	cout2othernumindata(data,sizeof(data)/sizeof(int),num1,num2);
	cout<<num1<<endl;
	cout<<num2<<endl;
	return 0;
}