【C语言】寻找两个‘单身狗’数

问题描述

一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。

编写一个函数找出这两个只出现一次的数字。

解题分析

在解这道题前，我想很多读者肯定见过这道题的简化版，“在一个数组中找出现次数为偶数次的数”。 而这道简化题是用异或来做的“^”(相同为0，相异为1)

而这道题呢，有两个‘单身’的数字 ，所以不能直接对全体数字进行异或。

假如“单身”的数字为5 和7，那么5和7异或后32为二进制中必定有1，如下图，5和7异或后第2位为1，所以5和7二进制数第2位二进制数不同！

在{1,2,3,4,5,1,2,3,4,7}中，我们可以按二进制数第2位为‘1’和‘0’进行分类，{2,2,3,3,7}，{1,1,4,4,5}这样就能把两个单身的数字分离开啦

而我们如何确定要判断是第几位二进制数是1呢？

其实这个问题可以简化为如何判断某个二进制数最后一位为‘1’，当我们把这个数与1按位与，如果最后一位为1那就为1，反之为0。

然后就是要解决是在哪一位的问题了，我们可以先把全体数异或的值放到num变量里面，然后进行循环，用‘>>’运算符（向右移）每次让num向右移一位进行判断，这样就能得到是第几位数啦

接下来我们就可以分组求出单身的数啦

for(int i=0;i<32;i++)
{
    if(((num>>1)&1)==1)
    {
        break;
    }
}

代码实现

#include<stdio.h>
void find_single_dog(int arr[], int sz)
{
  int dog1 = 0;
  int dog2 = 0;
  int num = 0;
  int i;
  for (i = 0; i < sz; i++)
  {
  num ^= arr[i];
  }
  for (i = 0; i < 32; i++)
  {
  if (((num >> i) & 1) == 1)
  {
    break;
  }
  }
  for (int j = 0; j < sz; j++)
  {
  if (((arr[j] >> i) & 1 )== 1)
  {
    dog1 ^= arr[j];
  }
  }
  dog2 = num ^ dog1;
  printf("%d %d",dog1, dog2);
}
int main()
{
  int arr[] = { 1,2,3,4,5,1,2,3,4,7 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  find_single_dog(arr, sz);
  return 0;
}