题目：

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

算法思路：

如果一个数组当中，只要一个数字出现一次，其他都是出现两次，那么我们只要把所有的数进行异或得到的就是结果

现在有两个数字出现一次，那么我们还是异或所有的数，最后的到的结果就是这两个不想等的数字的异或结果

比如 2 4 3 6 3 2 5 5 最后异或就是 4 与 6 异或，那么它们两个异或的结果肯定不是0；也就是说这个结果数字的二进制

当中至少有一位是1；我们在这个结果数字当中找到第一个为1的位置，记为第n位，现在我们以第n位是不是1把原来的

数组分为两部分；再分别异或两个数组；

分组异或：

比如int a[] = {1, 1, 3, 5, 2, 2}

    整个数组异或的结果为3^5即 0x0011 ^ 0x0101 = 0x0110

    对0x0110，第1位（由低向高，从0开始）就是1。因此整个数组根据第1位是0还是1分成两组。

   a[0] =1  0x0001  第一组

   a[1] =1  0x0001  第一组

   a[2] =3  0x0011  第二组

   a[3] =5  0x0101  第一组

   a[4] =2  0x0010  第二组

   a[5] =2  0x0010  第二组

    第一组有{1, 1, 5}，第二组有{3, 2, 3}，明显对这二组分别执行“异或”解法就可以得到5和3了。

// FindNumAppearOnce.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>using namespace std;//找到第一个为1的位置unsigned int FindFirstBitis1(int num){	int indexBit = 0;	while (((num & 1) == 0) && (indexBit < 8 * sizeof(int)))	{		num = num>>1;		++indexBit;	}	return indexBit;}bool IsBit1(int num , unsigned int indexBit){	num = num >> indexBit;	return (num & 1);}void FindNumAppearOnce(int array[], int nLength, int& num1, int& num2){	if (array == NULL || nLength < 2)	{		return;	}	int resultXOR = 0;	for (int i = 0; i < nLength; i++)	{		resultXOR ^=array[i];	}	//找到抑或结果数字当中的第一个1的位置	unsigned int indexOf1 = FindFirstBitis1(resultXOR);	num1 = num2 = 0;	for (int j = 0; j < nLength; ++j)	{		if (IsBit1(array[j],indexOf1))		{			num1^=array[j];		}		else		{			num2^= array[j];		}	}}int _tmain(int argc, _TCHAR* argv[]){	int array[] ={4,6,1,1,1,1};	int i = 0;	int j = 0;	FindNumAppearOnce(array,sizeof(array)/sizeof(array[0]),i,j);	if (i == 0 && j != 0)	{		cout<<"您输入的数组的当中出现1次的只有一个数字，它是："<<j<<endl;	}	else if (j == 0 && i != 0)	{		cout<<"您输入的数组的当中出现1次的只有一个数字，它是："<<i<<endl;	}	else if (i == 0 && j == 0)	{		cout<<"您输入的数组当中没有只出现一次的数字"<<endl;	}	else	{		cout<<"您输入的数组当中只出现1次的两个数字是"<<i<<" "<<j<<endl;	}		getchar();	return 0;}

C++ 算法之 数组中只出现一次的数字