C语言题目之单身狗2

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、题目

二、思路

第一步

在c语言题目之打印单身狗我们已经讲解了在一组数据中出现一个单身狗的情况，而本道题是出现两个单身狗的情况。根据一个数异或上0等于数本身，一个数异或数本身等于0。我们可以知道题目中的所有数异或之后会得到5和6的异或结果。也就是如下图：

第二步

在第一步的过程中，我们得到两个数5和6的异或结果0011，根据上图我们可以知道，当两个数出现二进制位不同的时候，他们的异或结果为1，既然两个数异或结果是两个数的二进制位不同的结果，那我们可以判断5和6的出现二进制位不同的地方，也就是出现1的地方，然后我们根据二进制位出现1的地方，将一堆数分成两个部分，这样不就将两个单身狗进行分开来了么。

第三步

在第二步我们已经将所有的数分成两堆，那么接下来，只要将两堆数分别异或不就得到了两个单身狗数嘛。

---

三、代码实现

void findnum(int arr[], int sz, int* pnum1, int* pnum2)
{//得到所有数的异或结果int i = 0;int sum = 0;for (i = 0; i < sz; i++){sum ^= arr[i];}//判断位数不同的那位int flag = 0;for (i = 0; i < 32; i++){if ((sum >> i) & 1)  //按位与，两个都为1才为1，找到是1的位置，按位异或是1的位置的位肯定不同{flag = i;break;}}//分成两组*pnum1 = *pnum2 = 0;  //这里设置为0是防止传进来的两个数不是0for (i = 0; i < sz; i++){if ((arr[i] >> flag)  & 1){*pnum1 ^= arr[i];  //这里将标志位地方二进制为1的那一堆数异或起来}else{*pnum2 ^= arr[i];  //这里将标志位地方二进制为0的那一堆数异或起来}}
}
int main()
{int arr[] = { 1,2,3,4,5,1,2,3,4,6 };int sz = sizeof(arr) / sizeof(arr[0]);int pnum1 = 0;int	pnum2 = 0;findnum(arr, sz, &pnum1, &pnum2);printf("%d %d",pnum1,pnum2);return 0;
}