找单身狗2

一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。

例如：有数组的元素是：1,2,3,4,5,1,2,3,4,6，只有5和6只出现1次，要找出5和6。

这里我们不妨回忆一下之前找单身狗1的思想：找单身狗1

这次数组里有两个单身狗，那么如果我们能把这个数组分成两组，每组都有一个单身狗，再按照找单身狗1的思想，这样不就可以找到这两个单身狗了吗？Yes！

那么问题来了，我们怎么把这两只单身狗分到两组中去呢？

我们不妨先把数组中的全部元素异或：1^2^3^4^5^1^2^3^4^6==5^6，5^6的二进制结果是

 这样我们发现倒数第一位和倒数第二位的结果为1，原因是由于5和6二进制的倒数第一位和倒数第二位相异，那么不妨只考虑倒数第一个相异为1的那一位（即倒数第一位）（考虑倒数第二个相异为1的那一位也可），通过判断倒数第一位是0还是1把数组元素分成两类。把数组元素分成两类后，就可以按照单身狗1的做法就可以找出这两个单身狗了！

代码如下:

#include <stdio.h>
int find_single_dog2(int arr[], int sz,int* pr1,int* pr2)
{
	int n = 0;
	int i = 0;
	//1.所有元素异或到一起
	for (i = 0; i < sz; i++)
	{
		n ^= arr[i];
	}
	//2.计算n的第几位是1，得到i
	int pos = 0;
	for (i = 0; i < 32; i++)
	{
		if (((n >> i) & 1) == 1)
		{
			pos = i;//记录所有元素异或后第一个1的位置，根据这个位置是1还是0将数组元素分为两组
			break;
		}
	}
	//3.分组
	for (i = 0; i < sz; i++)
	{
		if (((arr[i] >> pos) & 1) == 1)
		{
			*pr1 ^= arr[i];
		}
		else
		{
			*pr2 ^= arr[i];
		}
	}
 
}
int main()
{
	int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
	int ret1 = 0;
	int ret2 = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	find_single_dog2(arr, sz, &ret1, &ret2);
	printf("单身狗是%d和%d\n", ret1, ret2);
	return 0;
}