偶数个相同的数字按位异或为零。假如一个集合里有一个数字出现奇数次，其他数字出现偶数次； 那么对所有数字取异或操作，重复偶数次的数字都清零，留下来的就是那一个重复奇数次的数。
# 136. Single Number
# 找出数组中不重复的元素。其它元素出现两次。
# Input: [4,1,2,1,2]
# Output: 4
def single_num(nums):
return reduce(lambda x, y: x ^ y, nums)
在此基础上还有：
260. Single Number III
找出数组中两个唯一出现一次的元素，其余元素均出现两次。原题
Input: [1,2,1,3,2,5]
Output: [3,5]
如果我们可以把所有数字分成两组，使得：
- 两个只出现一次的数字在不同的组中；
- 相同的数字会被分到相同的组中。
那么对两个组分别进行异或操作，即可得到答案的两个数字。这是解决这个问题的关键。 具体的，我们做：
- 先对所有数字进行一次异或，得到两个出现一次的数字的异或值。
- 在异或结果中找到任意为 1 的二进制位。
- 根据这一位对所有的数字进行分组。
- 在每个组内进行异或操作，分别得到两个数字。
因为这两个数字只出现一次，所以它们的二进制表示中至少有一位不同从而在异或值中为 1，则可根据该位 区分开两个数，这就满足了条件 1； 因为两个相同的数字的对应位都是相同的，所以都会被分到同一组，满足了条件 2。
def singleNumber(self, nums):
total_xor = self.get_xor(nums)
mask = 1
while total_xor & mask == 0:
mask <<= 1
p1 = [num for num in nums if num&mask==0]
p2 = [num for num in nums if num&mask!=0]
return [self.get_xor(p1), self.get_xor(p2)]
def get_xor(self, nums):
from functools import reduce
return reduce(lambda x, y: x ^ y, nums)
另外还有“数组中一个数字出现一次，其他数字出现奇数次”的问题：
剑指 Offer 56 - II. 数组中数字出现的次数 II
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]
输出：4
示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1
限制：
1 <= nums.length <= 10000
1 <= nums[i] < 2^31
因为三个相同的数字的异或结果还是该数字，我们这里不能应用异或运算， 但还是可以用按位统计的思路，即统计某个二进制位为 1 的数字个数。 如果一个数字出现三次，那么它的二进制表示的每一位（0 或者 1）也出现三次。 如果把所有出现三次的数字的二进制表示的每一位都分别加起来，那么每一位的和都能被 3 整除。如果某一位的和能被 3 整除，那么那个只出现一次的数字二进制表示中对应的那一位是 0；否则就是 1。 例如：
二进制：
110110
110110
110110
101011
101011
101011
001010
cnt：
634363
实现为：
def singleNumber(self, nums, n = 3):
ans = 0
for i in range(32):
count = 0
for num in nums:
if ((num >> i) & 1):
count += 1
ans |= ((count % n != 0) << i)
return self.convert(ans)
# convert 的作用是因为 python 中的 int 是个对象，且没有最大限制，不是在第 32 位使用 1 来表示负数。
def convert(self, x):
if x >= 2**31:
x -= 2**32
return x
参考：
LeetCode算法题整理（位运算篇）Bit Manipulation from Xiaoliji’s Blog
最后附上 GitHub：https://github.com/gonearewe
