如何快速找出一组成对出现的数中唯一落单的一个

给定一个成员都大于0的int型数组，里面除了有一个单独的数以外其他的数都是成对出现的，而且这个数组中数的排列是随机的没有任何顺序的，比如it theArray = { 3, 7, 13, 16, 7, 13, 16}; 要求用最快的速度找出这个落单的数。
听上去问题并不难，我们的第一个想法是对数组进行一个二重循环，找出这个落单的数，代码如下

int findSingleV1(int theArray[], int size) {
    int i, j;
    for (i = 0; i < size - 1; i++) {
        for (j = i + 1; j < size; j++) {
            if (theArray[i] == theArray[j])
                break;
        }
        if (j == size)
            return theArray[i];
    }
    return 0;
}

成功的话返回这个数，失败的话返回0（给定数组中的数都大于0）。
就到此为止了吗？没有，V1的查找的时间复杂度为n的平方，显然不是最好的解决方案。下面我们可以考虑用排序来对数组进行处理，然后再找出单独的数，代码如下，

int myCompare(const void *a, const void *b) {
    return (*(int *)a > *(int *)b) ? 1 : -1;
}

int findSingleV2(int theArray[], int size) {
    int i;
    qsort(theArray, size, sizeof(theArray[0]), myCompare);

    // find single number
    for (i = 0; i < size - 1;) {
        if (theArray[i] == theArray[i+1]) {
            i += 2;
            continue;
        }
        return theArray[i];
    }
    if (i == size - 1 )
        return theArray[i];
    return 0;
}

V2中我们用到了C标准库中的qsort，因此需要自己单独定义一个compare函数。代码也比较简单，采用排序先进行处理以后，算法复杂度为NLogN。
下面我们看一个使用线性时间就可以找出答案的最快算法，

int findSingleV3(int theArray[], int size) {
    int i = 0, temp;
    while (i < size) {
        temp ^= theArray[i++];
    }
    return temp;
}

这个算法使用了平时并不常用的异或运算符，利用了异或运算符的如下性质，

输入	运算符	输入	结果
1	^	0	1
1	^	1	0
0	^	0	0
0	^	1	1

异或运算的特点是：两个相同的位异或得0，不同的位异或得1，不论是0还是1只要与0进行异或得出的结果都不变。这样的话在一个数组中如果很多对数字成对出现，那么他们按位异或的结果仍然为0，而这个0和那个单独出现的数再进行异或，得到的数就是这个落单的数的值，这个算法最为快速，也最为巧妙。