1. 单身狗1

代码实现：

#include <stdio.h>

int main()
{
	int arr[] = { 1,2,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	int tmp = 0;
	for (i = 0; i < sz; i++)
	{
		tmp ^= arr[i];
	}
	printf("%d\n", tmp);

	return 0;
}

需要用到异或的两个规律：

1. 0^n=n
2. n^n=0

输出结果：

2. 单身狗2

代码实现：

#include <stdio.h>

int main()
{
	int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//将整个数组异或起来，得到两个不同数字的异或结果   例如：5^6的结果
	int i = 0;
	int tmp = 0;
	for (i = 0; i < sz; i++)
	{
		tmp ^= arr[i];
	}
	//找到tmp中二进制为1的某一位k
	int k = 0;
	for (i = 0; i < 32; i++)
	{
		if (((tmp >> i) & 1) != 0)
		{
			k = i;
			break;
		}
	}
	//遍历数组，把每个数据第k位上是1的，分到一个组进行异或
	//最终的值存到p1和p2中
	int p1 = 0;
	int p2 = 0;
	for (i = 0; i < sz; i++)
	{
		if (((arr[i] >> k) & 1) != 0)
		{
			//第k位是1
			p1 ^= arr[i];
		}
		else
		{
			//第k位是0
			p2 ^= arr[i];
		}
	}

	printf("%d %d", p1, p2);

	return 0;
}

这个题与上一个不同的地方是有两个“单身狗”，根据上一题的经验，我们也可以想到把这些数据分成两组进行异或。

但是如何分组，特别是如何把5和6分开？这是重点也是难点。

其实我们可以这样做：

1. 首先整体异或，结果就是两个不一样数字的异或结果x；
2. 然后找到x的倒数第k位为1的地方；
3. 最后把所有数字以倒数第k位分组进行异或。