1.此问题又名单身狗1问题，对于传统解法可使用暴力解法即遍历数组，但此方法相对比较low，而且如果数组长度变大就会很麻烦，所以这里引出一个关键概念，即异或，先上代码
void FindDog1(int *arr,int sz,int * p) { int ret = 0; for (int i = 0; i < sz; i++) { ret ^= arr[i]; } *p = ret; printf("%d\n", ret); }
首先，异或算法的规则是相同为0，相异为1，当一个数与0异或时，得出的结果是这个数，比如5^5=0,5^0=5,由此结论基础，设置一个ret初始值为0，将ret与数组每个元素异或即可得出唯一的单独的值.
2.在单身狗1的基础上再延伸出来的第二类问题，单身狗2问题，对于单身狗2问题，依然可以使用暴力解法，但为什么不用，原因同上，先上代码，缓缓道来
void Finddog2(int* arr, int sz, int* p1,int *p2) { int ret = 0; for (int i = 0; i < sz; i++) { ret ^= arr[i]; } int pos = 0; int j = 0; for (j = 0; j < 32; j++) { if (((ret << j) & 1) == 1) { break; } } pos = j; for (int i = 0; i < sz; i++) { if (((arr[i] << j) & 1) == 1) { *p1 ^= arr[i]; } else { *p2 ^= arr[i]; } } }
首先，依然是要使用异或的方法，但与单身狗1不同的是，这次将每个元素异或后，得到的值是两个“单身狗”值异或后的值，并不能得出我们想要的东西，所以，在此我们又将出现一种新的思想，那就是分组思想，也就是将两个单身狗值分为两组，这样一来，一个组里就一个单身狗，问题就转变为了两个单身狗1的问题，这样一来，我们就好下手了.
关键代码块分析：
下面这段代码的用处是找到两个单身狗的二进制序列中的哪一位是不同的，因为此时的ret是两个单身狗异或后得到的值，此时ret的二进制序列中为1的那一位也就是两个单身狗中二进制不同的一位，这里只要能随便找到一位不相同的就可以.
int pos = 0; int j = 0; for (j = 0; j < 32; j++) { if (((ret << j) & 1) == 1) { break; } } pos = j;
下面代码的就体现出了分组思想，将上面得到的二进制位pos的那一位为1的分为一组，为0的分为另一组，这样一来，就完成了分组，指针p1和p2解引用后的值就为两个单身狗值
for (int i = 0; i < sz; i++) { if (((arr[i] << j) & 1) == 1) { *p1 ^= arr[i]; } else { *p2 ^= arr[i]; } }
结尾：今天的分享到此结束，喜欢的朋友如果感觉有帮助可以点赞三连支持，咱们共同进步!
