[多少懂点位运算]找出唯一的数字

大家都知道现代计算机的底层是以二进制为基础的，计算机所有的操作最后都归结到了简单的二进制位运算上：与，或，非和异或。

许多编程语言也提供了这四个位运算符（一般表示为'&'，'|'，'!'和'^'），再加上移位运算符（<<和>>）,在计算的时候比算术运算要快很多,不过现在的编译器和解释器已经会将乘以2的幂次和除以2的幂次转换为移位运算符了。

懂一点位运算的知识可以巧妙的解决一些特定领域的问题。

问题描述

现在看一个比较简单的问题:

有一组整数，其中出了一个数字外，其他每个数字都出现了两次，找出这个只出现了一次的数字。

比较直接的方法就是哈希表（如果语言有原生的集合数据类型更好），速度也不满，不过空间复杂的是O(n)的，但是往往面试官会让你在O(1)的空间复杂度下解决问题，这时候就需要位运算登场了。

异或运算的性质

异或运算简单来说就是或运算再取反，即a xor b = not (a or b),我们可以得到：

1 ^ 0 = 1

1 ^ 1 = 0

0 ^ 0 = 0

0 ^ 1 = 1

稍微推广一下我们可以发现一个数字异或自己为得到0，而异或0会得到自己，即a ^ 0 = a, a ^ a = 0,于是这个问题也就迎刃而解了，就是对这一组数字做一连串的异或运算，最后得到的数字就是那一个唯一只出现过一次的数字。

代码实现

请不要认为这一部分是水字数。

from functools import reduce
from operator import xor

def findUnique(numbers):
    return reduce(xor, numbers)

总结

本文简单的介绍了异或运算的性质和一个更简单的应用，希望可以给大家一点帮助和启发。

最后祝大家享受生活，享受代码。