查找数组中只出现一次的一个数

对于一个数组其中每个数出现了两次，只有一个数出现了一次，找出这个只出现了一次的一个数，这是一个经典的面试题，把数组中的数进行异或运算，出现两次的数异或的结果为0，最终异或的结果就为只出现了一次的一个数。

例如：数组元素为3,4,4,3（011）异或4（100）结果为111,111再接着异或4（100），结果为011，即为3。

void FindOnlyoneInArray(int a[],int length){
	if (a==NULL||length<2)
	{
		return;
	}
	int result = 0;
	for (int i = 0; i < length;++i)
	{
		result ^= a[i];
	}

   cout << result << endl;
}

对于查找数组中只出现一次的一个数我们已经知道怎么来做了，那么对于查找数组中两个只出现一次的数，也是同样的道理，只需要把数组分成两个子数组，每个里面包含一个只出现一次的数，而其他数字都成对出现两次，但是怎么来拆分原数组呢？

 还是异或数组中的每一个数字，最终得到的结果就是两个只出现一次的数字的异或结果，以为这两个数不一样，最终异或的结果也不为0，那么这个结果的二进制表示中至少有一位为1，我们找到这个1的位置，记为一个标记，当做分割的标准，第一个子数组中每个数字的标记为都为1，第二个的都为0，因为相同的数字，标记位一定相同，不同的数字，标记位不同，这样就达到了我们的要求。

例如：数组元素为2,4,3,6,3,2,5,5，异或的结果为0010，也就是倒数第二位为1，也就是倒数第二位为标记位来进行拆分，那么第一个子数组就为{2,3,6,3,2}，他们的倒数第二位为1，第二个子数组为{4,5,5}倒数第二位为0，对这两个子数组分别再异或，最终找到4和6。

void FindAppearOnce(int data[], int length, int *num1, int *num2){

	if (data == NULL || length < 2){
		return;
	}

	int result = 0;
	for (int i = 0; i < length;++i)
   {
		result ^= data[i];
    }

	unsigned int indexOf1 = FindFirstBitIs1(result);
	
	*num1 = *num2 = 0;

	for (int j = 0; j < length;++j)
	{
		if (IsBit1(data[j],indexOf1))
		{
			*num1 ^= data[j];
		}
		else{
		
			*num2 ^= data[j];
		}
	}
}

unsigned int FindFirstBitIs1(int result){

	int indexBit1 = 0;
	while (((result&1)==0)&&(indexBit1<8*sizeof(int)))
	{
		result = result >> 1;
		++indexBit1;
	}
	return indexBit1;
}

bool IsBit1(int num,unsigned int indexBit1){

	num = num >> indexBit1;
	return (num&1);
}