异或(Exclusive or, XOR)是一种逻辑运算，在一些情境下，巧用异或运算能够很高效地解决问题。

异或运算的定义

异或运算的符号是^，其定义如下：

a xor b = (a & ^b) | (^a & b)

真值表：

a b a xor b
0 0 0
0 1 1
1 0 1
1 1 0

应用情境

基础问题

首先考虑下述问题：

一组整数，除了一个只出现一次以外，其他每个整数都恰好出现两次，寻找那个特殊的整数。

最容易想到的方法是排序后再遍历一趟数组，便可以得到这个唯一的只出现一次的整数。算法实现如下：

def single_number(numbers):
    tmp = numbers.sort()
    for i in range(tmp.__len__()-1):
        if tmp[i] != tmp[i+1]:
            return tmp[0] if i == 0 else tmp[i+1]

此算法的时间复杂度取决于采用的排序算法的时间复杂度。

进一步思考不难想到，可以用哈希算法来解决这一问题。具体做法是每遍历到一个数，如果该数在哈希表中存在，就从哈希表中删除该数，否则将该数加入到哈希表中。 这一算法实现如下：

def single_number(numbers):
    m = {}
    for n in numbers:
        if n in m:
            m.pop(n)
        else:
            m[n] = True
    return list(m)[0]

由于哈希表的时间复杂度可以认为是O(1)的，因此，可以在O(n)的时间内求出整数序列中仅仅出现一次的元素。

再进一步思考，可以利用异或运算的性质来解决这个问题。相同元素异或的值为0，任意值与0异或都得原值。具体实现如下：

def single_number(numbers):
    tmp = 0
    for n in numbers:
        tmp ^= n
    return tmp

利用异或的性质来解决这一问题，即简便又高效，是一个非常好的算法。

扩展

接下来，思考这样一个问题：

一组整数，除了一个只出现一次以外，其他每个整数都恰好出现三次，寻找那个特殊的整数。

当题目条件变为每个整数都出现三次，排序的解法和哈希表的解法仍然试用，且实现方式和算法的复杂度都不变。此处不再赘述。

思考，在此条件下，这个问题能否仍然利用异或运算的性质来解决吗？答案是肯定的。

对于32位的整数，显然有如下结论：所有数每一位的和模3的结果必定为0或1，并且，该值肯定为序列中仅仅出现一次的那个数该位上的值(0或1)。于是，这个问题便可以 这样解决：分别求出仅仅出现一次的数的每一位的值，然后通过或运算连在一起即可。

上述算法也不难实现：

def single_number(numbers):
    number = 0
    for i in range(32):
        value, mask = 0, 1 << i
        for n in numbers:
            value += (0 if mask & n == 0 else 1)
        number |= (value % 3) << i
    return number

推广到一半情形

推广到更一般的情形：

一组整数，除了一个只出现一次以外，其他每个整数都恰好出现n次，寻找那个特殊的整数。

不难想到，对序列中每一个数的某一位上的值求和，再模n，得到的余数便是仅仅出现一次的那个数该位上的值。这一方法可以灵活、高效地解决这一类问题。

算法修正

然而经过测试，发现上述算法有一个缺陷：如果最终仅仅出现一次的数是一个负数，那么返回的将是该数的补码所对应的无符号整数。这显然不是我们想要的结果，因此， 需要进一步根据结果的特点(最高二进制位的值是否为1)来进行补码的转换。也可以增加一个标志变量来记录负数的个数，以此来判断最终得到的是不是负数的二进制补码。

延伸思考

对于Python这一类的语言，这一问题并不便于解决。因此不得不思考更好的解决这一问题的方法。

对于这一模型中 n=3 的情形，可以这样考虑：

通过两个变量来保存异或运算过程中得到的信息。如果某个数出现了三次，便直接清除该数每一位上的信息。实现如下：

def single_number(numbers):
    ## a, b 分别为出现一次的标志位和积累标志位
    a, b = 0, 0
    for n in numbers:
        b |= a & n    ## 是否为第二次出现
        a ^= n        ## 出现奇数次保留，否则抛弃
        t = a & b     ## 第三次出现
        a, b = a & ~t, b & ~t   ## 抛弃出现三次的数的信息
    return a          ## 返回仅仅出现一次的数。

这样的算法便可以从一组数中找到仅仅出现一次的数。

对于n为其他值得情形，分析起来更复杂，也更容易出错。在绝大多数问题中，哈希表的算法会更加适用。

总结

二进制数字的每一位包含的信息很丰富也很费解，位运算特别是异或运算在特殊模型中能有意想不到的妙用。