C语言—找出单身狗（2个）

//找出数组中两个只出现一次的数，其它数都成对存在
#include
int main()
{
	int arr[10] = { 5,7,6,1,2,6,7,2,3,1 };
	int ret = 0;
	for (int i = 0; i < 10; i++)
	{
		ret ^= arr[i];
	}
	int n = 0;//num的第n位为1
	while (n < 32)
	{
		if (ret & (1 << n))
			break;
		else
			n++;
	}
	int a = 0, b = 0;
	for (int i = 0; i < 10; i++)
	{
		if (arr[i] & (1 << n))
			a ^= arr[i];
		else
			b ^= arr[i];
	}
	printf("这两个单身狗是:%d %d", a, b);
	return 0;
}

思路：先设一个数ret，将它与这个数组中所有数都异或，就得到这两个数的异或，接下来只需要将这两个数分开即可，分开的方法是将它们分成两组，再设两个变量，将他们分别以两组异或就得到这两个数了，分开的方法是找到这两个数二进制位中不同的一位，根据这一位是0还是1分成两组，这样的话那两个数就分成了两组

首先要先讲一下位移操作符‘<<’和'>>',比如说“1<<1”表示1的二进制向左移动一位，实质上就是在原来的基础上乘一个2，相反，‘>>’就是在原来的基础上除以2.

结果如图所示：

如果不是考虑到空间和时间复杂度，其实还有很多方法，这样的方法我也没想到，我一开始是设了好几个变量，再用了多次循环才得出结果，说实话算法真的挺难，但是很有锻炼思维的价值。