[C++知识库]教你用c语言完成找单身狗问题

一组数据中只有两个数据单独出现，其余数据都是成对出现，找出 这些数据中单独的两个数并输出。

#include<stdio.h>
#include<assert.h>
#include<windows.h>
#pragma warning(disable:4996)

void findnum(int num[],int len,int *xp,int *yp){
	assert(xp);
	assert(yp);
	*xp = 0;
	*yp = 0;
	step1
	int n = num[0];
	for (int i = 1; i < len; i++){
		n ^= num[i];
	}
	//1.n一定不是0！
	//2.n的二进制序列中，一定至少有一个1
	//3.x,y二进制，相同的部分一定是0，不同的部分一定是1，反过来，如果n中有一个比特位是1，一定是x，y对应的比特位是不同的
	step2
	int flag = 1;
	int i = 0;
	while (i<sizeof(int)){
		if (n&flag){
			break;
		}
		flag <<= 1;
		i++;
	}
	//4.成对的数据，第flag标志位对应的二进制一定是一样的（0 or 1）
	//5.不成对的，该位置一定不同
	//6.按照flag进行分组，flag==0，flag==1两组，成对的数据，
	//一定被分配到了同一个组，不同的数据，一定被分配到了不同的组
	//A组，B组，所有数据是成对的，只有一个是单独的
	//step3
	for (int i = 0; i < len; i++){
		if (flag&num[i]){
			//A组
			*xp ^= num[i];
		}
		else
			//B组
			*yp ^= num[i];
	}
}
int main()
{

	int num[] = { 1, 2, 1, 2, 3, 3, 4, 4, 5, 6, 6, 5, 9,10 };
	int len = sizeof(num) / sizeof(num[0]);
	int x = 0;
	int y = 0;
	findnum(num,len,&x,&y);
	printf("%d ,%d", x, y);
	system("pause");
	return 0;
}