C语言实现单身狗问题（找出单身狗详解版）

今天我们用C语言来实现一个单身狗问题，让我们开始学习吧!

1.单身狗问题初阶版（找一只单身狗）

代码实现

2.单身狗问题进阶版（找两只单身狗）

代码实现

1.单身狗问题初阶版（找一只单身狗）

问题描述：

在一堆数据中，其余数字都出现两次，只有这个数字出现一次，找到这个只出现一次的数字(它就是那只单身狗），并输出单身狗

方法分析：

我们这里要用到“异或（^）”，我们首先要知道什么是异或

相同为0，相异为1

例如：5^6（两个数异或时，是用二进制进行异或运算的）

0和任何数异或都等于任何数

知道这些，我们就可以进行问题分析了：

假设我们输入了10个数：1 2 3 4 5 1 2 3 4

让它们整体异或，我们把这10个数排成有序数列，就是1 1 2 2 3 3 4 4 5（这与不排序整体异或结果是一样的），我们会发现1^1=0,2^2=0,以此类推到了最后就是0^5=5,所以把它们放一起异或就得到了5，这样也就找到了这只单身狗

接下来我们看一下完整代码吧：

代码实现

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

//找出单身狗，找一只狗

int main()
{
	//随机9个数存进去
	int arr[9] = { 0 };
	int i = 0;
	for (i = 0; i < 9; i++)
	{
		scanf("%d", &arr[i]);
	}
	int ret = 0;//接收异或值
	//整体异或
	for (i = 0; i <9 ; i++)
	{
		ret ^= arr[i];
	}
	printf("单身狗是 %d\n", ret);
	return 0;
}

运行结果：

这样我们就求得了这只单身狗

2.单身狗问题进阶版（找两只单身狗）

我们理解了用异或这个运算符求单身狗后，我们就可以进阶学习了

问题描述：

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

方法分析：

我们已经知道异或，接下来这个问题也是用异或这个方法来解决的，但是我们要找出两只狗，我们想想，是不是把两个只出现一次的数字放在两个不同的组，再把其余出现两次的数字在按一定的方法放在这两个组，再分别对这两个组进行整体异或操作就可以像初阶版一样找出这两只单身狗

例如：这几个数字是 1 2 3 4 5 6 1 2 3 4

我们理想中的两个组存放的数据是：

组1: 5 后面的数字

组2: 6 后面的数字

那我们现在要解决的就是，如何把它们放在两个组中

我们先把这10个数字整体异或，最后结果一定就变成了0^5^6=3 (0000 0011)

我们根据这个异或结果 3 对我们的数据进行分组，3这个数的二进制有011，我们就按1来对数据分组，那么我们就可以得到

组1（二进制第一位为1）：5 1 1 3 3

组2（二进制第二位为1）：6 2 2 4 4

如何判断一个数对应的二进制位数上是0 还是1呢？

这就要用到我们初识C语言中的移位操作符了:左移：‘<<’ 右移：'>>'

比如： 1，它的二进制第一位就是1，所以我们只需要右移0位就可以把它分到第一组

2，它的二进制第二位是1，所以我们需要右移1位把它分到第二组

以此类推，就得到了我们的两个组。

这里讲清楚之后，我们进行代码的实现：

代码实现

//进阶版，找两只单身狗

void find_single_dog(int arr[], int sz, int single_dog[])
{
	int ret = 0;//用ret来初始异或所有数据
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		ret ^= arr[i];
	}
	//计算ret的二进制位哪一位为1，标记这个位置，用来后续分组0和1
	int pos = 0;
	for (i = 0; i < 32; i++)
	{
		if (((ret >> i) & 1) == 1)
		{
			pos = i;//得到了为1的二进制位
			break;
		}
	}
	//进行分组
	for (i = 0; i < sz; i++)
	{
		if (((arr[i] >> pos) & 1) == 1)
		{
			single_dog[0] ^= arr[i];
		}
		else
		{
			single_dog[1] ^= arr[i];
		}
	}
}

int main()
{
	int arr[10] = { 1,2,3,4,5,6,1,2,3,4 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int single_dog[2] = { 0 };//用来存放两只单身狗
	find_single_dog(arr, sz, single_dog);
	int i = 0;
	//打印这两只单身狗
	printf("这两只单身狗是:>");
	for (i = 0; i < 2; i++)
	{
		printf(" %d  ", single_dog[i]);
	}
	return 0;
}

运行一下