好好的利用异或能够产生奇妙的效果。

异或运算的性质：

不论什么一个数字异或它自己都等于0。也就是说。假设我们从头到尾依次异或数组中的每个数字，那么终于的结果刚好是那个仅仅出现一次的数字。由于那些出现两次的数字所有在异或中抵消掉了。

例题：

给定大小是N的数组，数组里的元素互相不反复，元素的大小范围是1～（N+1）。目标是找出第一个miss的数。要求时间复杂度O(N)。空间是O(1).

由于这个数组总共仅仅有N 个元素，因此在1--N+1中必然有一个数不存在。设res =0, 使用异或操作，先让res和 下标+1  异或，然后同每个数异或。当中出现两次的数刚好异或为0.剩下的则是结果。

<span style="font-size:14px;">// you can also use includes, for example:

// #include <algorithm>

int solution(vector<int> &A) {

    // write your code in C++98

    int res = 0;

    int max = A.size();

    if(max==0) {

        return 1;

    }

    for(int i=0;i<A.size();i++) {

        res^=(i+1);

        if(A[i]<=max) {

            res^=A[i];

        }

    }

    return res==0?max+1:res;

}</span>

类似的另外一道题：

题目：一个整型数组里除了两个数字之外。其它的数字都出现了两次。请敲代码找出这两个仅仅出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

答案见： http://zhedahht.blog.163.com/blog/static/2541117420071128950682/

參考文献：

http://www.cnblogs.com/parapax/p/3632255.html

http://blog.csdn.net/caopengcs/article/category/1502799/4