寻找单身狗

在一个数组中仅出现一次，其他数均出现两次，这个出现一次的数就被称为“单身狗“。

一.一个单身狗

我们知道异或运算操作符 ^ ，它的特点是对应二进制位相同为 0，相异为 1。

由此我们容易知道两个相同的数,进行异或运算得到的结果一定为 0，0和非0数字异或的结果为非0数字，因此我们可以将数组中的所有元素都进行异或，出现过两次的数异或结果将为0，留下来的就是单身狗了。

代码实现：

int FindSingle(int* arr,int sz)
{int dog = 0;int i = 0;for (i = 0; i < sz; i++){dog ^= arr[i];}return dog;
}
int main()
{int arr[5] = { 1,4,2,1,2 };int sz = sizeof(arr) / sizeof(arr[0]);printf("单身狗为：%d\n", FindSingle(arr, sz));return 0;
}

二.两个单身狗

如果数列中存在两个单身狗，依然和上面一样全部进行异或运算显然是得不到答案的，相同的数通过异或消除了，得到的会是两个单身狗异或的结果。

能不能将两个单身狗分开，在两个数组中分别以上面的方式找出单身狗呢？

异或的条件是对应二进制位相同为 0，相异为 1。通过两个单身狗数异或的结果，我们可以得到两个单身狗数在某些二进制位上单身狗的值不同（0或1），可以通过这位上的值不同来将两个单身狗分开。

同样，对于出现过两次的非单身狗数，也可以通过判断某一二进制位相同，将其放入同一数组中，再对该数组进行异或运算后消除。

代码实现：

void FindSingle(int* arr, int sz,int* dog,int* dog1,int* dog2)
{int i = 0;for (i = 0; i < sz; i++){//全部异或得到两个单身狗的异或结果*dog ^= arr[i];}//两个单身狗数某二进制位上的值不同int pos = 0;for (i = 0; i < 4; i++){//dog的值为两个单身狗数异或的结果，dog的某一二进制位为1则代表两个单身狗在这一二进制位上不相等//找出这一位置并拷贝下来if (((*dog >> i) & 1) == 1){pos = i;break;}}//将数组按pos位上的值为1或0分组并求异或for (i = 0; i < sz; i++){if (((arr[i] >> pos) & 1) == 1){*dog1 ^= arr[i];}else{*dog2 ^= arr[i];}}
}
int main()
{int arr[10] = { 1,2,3,4,5,1,2,3,4,6 };int dog = 0;int dog1 = 0;int dog2 = 0;int sz = sizeof(arr) / sizeof(arr[0]);FindSingle(arr, sz, &dog, &dog1, &dog2);printf("单身狗1是：%d,单身狗2是：%d", dog1, dog2);return 0;
}