1. 位异或的性质
（1）异或，相同为0，相异为1
（2）a^a=0（任何数和它本身异或结果为0）
（3）a^0=a (任何数与0异或结果还是它本身）
（4）异或支持交换律
2. 找出单身狗——版本1
2.1 题目内容：
有一个数组只有一个数字出现一次，其余数字都是成对出现的，编写一个函数找出只出现一次的数字。
例如：
有数组的元素是：1 2 3 4 5 1 2 3 4
5只出现了1次，要找出数字5。
2.2 思路分析
很多人看到这道题目的思路就是计数。即遍历这个数组，再依次将遍历到的数字和这个数组中的所有数字对比，如果相同，就计数+1。这样，最后成对出现的数字计数为2，只出现一次的数字计数为1。
我们可以通过分析得知这种方法的时间复杂度为O(N^2)。
如果有小伙伴不知道怎么分析算法复杂度，可以看看我的这篇文章：https://blog.csdn.net/m0_62531913/article/details/132019833?spm=1001.2014.3001.5501
这种方法虽然是可行的，但是这样的时间复杂度太高了，效率低下。
这里我们就需要巧用异或了！
因为这个数组中只有一个数字出现一次，其他数字都出现了两次。那么我们将这个数组中的每个数字两两相互异或。根据位异或的性质，任何数和它本身异或结果为0，那么这个数组中成对出现的数字相互异或后得到的结果就是0。同时位异或支持交换律，那么最后的结果就是0和那个只出现一次的数字进行异或。剩下又因为任何数与0异或结果还是它本身，所以这个数组中所有数字两两相互异或后的结果就是只出现一次的数字。
这样的做法时间复杂度就降低到了O(N)。
2.3 代码实现
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int find_single_dog1(int arr[], int sz)
{
int ret = 0; //记录数组元素两两相互异或的结果，初始化为0
for (int i = 0; i < sz; i++)
{
ret ^= arr[i]; //将数组元素两两相互异或
}
return ret;
}
int main()
{
int arr[] = {
1,2,3,4,5,1,2,3,4 };
int sz = sizeof(arr) / sizeof(arr[0]); //得到数组中的元素个数
int dog = find_single_dog1(arr, sz);
printf("dog=%d\n", dog);
return 0;
}
3. 找出单身狗——版本2
3.1 题目内容
一个数组中只有两个数字出现了一次，其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。
例如：
有数组的元素是：1，2，3，4，5，1，2，3，4，6
只有5和6只出现1次，要找出5和6。
3.2 思路分析
如果我们直接按照版本1的思路，会发现最后所有数字异或后的结果为两个单身狗数字的异或。
但是如果我们能将原始的数据分成两组，让每组元素只有一个数字出现一次，其他数字都是成对出现。这样我们将第一组数字相互异或就能得到第一个单身狗数字，将第二组数字相互异或就能得到第二个单身狗数字。
但是如何分组呢？因为最后剩下的是两个单身狗数字，这两个数字肯定不一样。那么这两个数字的二进制位中必然有不同的一位。这一位异或后的结果为1。我们就可以按照这个不同的一位来进行分组：
我们发现5和6从右往左数的第一位和第二位数字不同，第一位数字异或后的结果为1，第二位数字异或后的结果也为1。这里我们有两种分法：
我们如果按5和6的从右往左数的第一位来分组，可以得到这两组（第一组每个数字的每一位从右往左数第一位都是1，第二组每个数字的每一位从右往左数第一位都是0）：
我们如果按5和6的最低的第二位来分组，可以得到这两组（第一组每个数字从右往左数第二位都是0，第二组每个数字从右往左数第二位都是1）：
这里我们按第一种分法分组：
分组要求：
分成两个组后，每个组有一个单身狗数字。
相同的数字必须在同一组。
分完组后，将第一组数字相互异或，即1^1^3^3^5=5
将第二组数字相互异或，即2^2^4^4^6=6
这样我们就得到了5和6这两个单身狗数字！
3.3 代码实现
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void find_single_dog2(int arr[], int sz, int* pd1, int* pd2)
{
int ret = 0;
for (int i = 0; i < sz; i++)
{
ret ^= arr[i]; //所有数字异或，最终ret存放了两个单身狗数字异或后的值
}
int pos = 0;
for (int i = 0; i < 32; i++)
{
if (((ret >> i) & 1) == 1) //计算ret中的第几位是1
{
pos = i;
break;
}
}
for (int i = 0; i < sz; i++)
{
if (((arr[i] >> pos) & 1) == 1) //计算数组中元素的第pos位为1的异或
*pd1 ^= arr[i]; //根据异或的性质得到第一个单身狗数字
}
*pd2 = ret ^ *pd1; //计算数组中第pos位为0的异或，得到第二个单身狗数字
}
int main()
{
int arr[] = {
1,2,3,4,5,1,2,3,4,6 };
int sz = sizeof(arr) / sizeof(arr[0]);
int dog1 = 0;
int dog2 = 0;
find_single_dog2(arr, sz, &dog1, &dog2); //&dog1和&dog2是返回型参数
//因为函数只能有一个返回值，
//而我们想知道两个数字，所以我们这里传地址
printf("dog1=%d dog2=%d\n", dog1, dog2);
return 0;
}
4. 总结
到这里我们就巧用异或解决了C语言中的单身狗问题。有什么问题欢迎在评论区讨论。如果觉得文章有什么不足之处，可以在评论区留言。如果喜欢我的文章，可以点赞收藏哦！
