C语言在数组中寻找单身狗的问题(剑指offor)

初级版：

数组中含有任意个元素，其中都无数个成双成对的元素，只有一个元素是单身狗。(问题：寻找出这个数组中一个的单身狗)

代码思路：通过将数组每一个元素进行进行异或，由于一个数据和自身异或，或一个数据和0异或的结果都等于0。从而得到没有对象的那个数字，在将那个数字赋值给一个变量。

#include <stdio.h>
int DanShenGou(int arr[], int sz)
{
	int i = 0;
	int pos = 0;
	for (i = 0; i < sz; i++)
	{
		pos ^= arr[i];//这一步是将arr数组中每一个元素都进行异或，从而寻找出单身狗
	}
	return pos;
}
int main()
{
	int arr[10] = { 1,2,3,4,5,1,2,3,4 };
	int sz = sizeof(arr) / sizeof(arr[0]);//求数组中的元素个数
	int ret=DanShenGou(arr, sz);
	printf("单生狗数字：%d\n", ret);
	return 0;
}

进阶版：

数组中含有任意个元素，其中都无数个成双成对的元素（其中含有一个偶数的单身狗也有一个奇数的单身狗），有两个元素是单身狗。(问题：寻找出这个数组中的两个单身狗)

代码思路：通过将数组每一个元素进行异或，由于一个数据和自身异或，或一个数据和0异或的结果都等于0。从而得到两个没有对象的元素，最后在将这两个元素进行异或，从而得到一个不为0的值，将该值赋给pos变量；再计算出pos变量的二进制数中哪一位含有1，创建一个变量ret保存该位数；然后将数组中每一个元素右移ret位再和1进行&操作，如果&1操作得到结果为1则该数是一个奇数，反之得到则该数是一个偶数，通过将数组分组成功后，最后将分组后的数组中每一个元

#include <stdio.h>
void DanShenGou(int arr[], int sz)
{
	int i = 0;
	int pos = 0;
	int ret = 0;
	int sum1 = 0;//用来装第一个单生狗
	int sum2 = 0;//用来装第二个单生狗
	for (i = 0; i < sz; i++)
	{
		pos ^= arr[i];//这一步是将arr数组中每一个元素都进行异或，从而寻找出两个单身狗
		              //然后将这个两个单生狗进行异或
	}
	for (i = 0; i < 32; i++)
	{
		if (((pos >> i) & 1) == 1)
		{
			ret = i;
			break;
		}
	}
	for (i = 0; i < sz; i++)
	{
		if (((arr[i] >> ret) & 1) == 1)
		{
			sum1^= arr[i];
			
		}
	}
	for (i = 0; i < sz; i++)
	{
		if (((arr[i] >> ret) & 1) == 0)
		{
			sum2 ^= arr[i];
		}
	}
	printf("单生狗数字：%d %d\n", sum1,sum2);


}
int main()
{
	int arr[10] = { 1,2,3,4,5,1,2,3,4,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);//求数组中的元素个数
	DanShenGou(arr, sz);
	return 0;
}

素进行进行异或。