你真的了解位运算？用了这个运算符，算法的时间复杂度竟然降了一个数量级！

其实这个运算符很容易被人忽略，他就是C语言中的位异或运算符^
位运算符家族中，最常用的，莫过于异或运算符。

我们先看异或运算符的定义： 参与运算的两个值，如果两个相应位相同，则结果为0，否则为1。
即：0^0=0， 1^0=1， 0^1=1， 1^1=0

例如：10100001^00010001=10110000
0^0=0,0^1=1 可理解为： 0异或任何数，其结果=任何数
1^0=1,1^1=0 可理解为： 1异或任何数，其结果=任何数取反
任何数异或自己，等于把自己置0

通过按位异或运算，可以实现两个值的交换，而不必使用临时变量。例如交换两个整数a，b的值，可通过下列语句实现：
a=10100001, b=00000110
a=a^b； 　　//a=10100111
b=b^a； 　　//b=10100001
a=a^b； 　　//a=00000110

异或运算符的特点是：数a两次异或同一个数b（a=a^b^b）仍然为原值a.

利用他的特点，我们可以解决一个常见的问题：
Single Number: 整数型数组中，每个元素均出现两次，除了一个元素例外，如何找出这个元素？能否设计一个线性时间的算法，且不需要额外的存储空间？

其实O(n)的算法不容易一下子想到，先说说常规的解决思路，有如下两种：
1、对元素的出现次数进行统计，可进行n*n循环，判断元素是否只出现了一次。这样时间复杂度为O(n^2), 不需要额外空间。
2、先对元素进行排序，然后进行相邻两元素的对比，如a1和a2对比，a3和a4对比，如果不同，则前一个元素(a1、a3)就是所要查找的元素。
这两种解法的时间复杂度都比O(n)更高。但是，如果你运用了异或运算符的特点，那么这个问题就很容易解决了，算法复杂度为O(n)，且不需要额外空间，像这样：

int singleNumber(int A[], int n) {
    int result = 0;
    for (int i = 0; i<n; i++)
    {
        result ^=A[i];
    }
    return result;
}