原题链接：https://leetcode.com/problems/single-number-iii/
给出一个数组，其中有两个元素仅有一个，其它均有两个，要求找出仅有一个的两个数字。
首先最直观的解法，维护一个 set，遍历原数组，没有的加进去，有的移出，最后剩下的就是就是只有一个的了。
该方法的时间复杂度是 O(N)，空间复杂度也是 O(N)。
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
result = set()
for n in nums:
if n in result:
result.remove(n)
else:
result.add(n)
return list(result)
题目说有O(1)空间复杂度的姐，可以想到的思路是 set 的添加和删除改成用一个常数来存储，用位操作来保存。
想了很久没想出来，最后去看了下讨论，终于理解了。
主要用到的是异或的一些特性。
以前有个经典例子，使用异或可以不借助中间变量交换两个数字：
In [203]: a, b = 1, 2
In [204]: a = a ^ b
In [205]: b = a ^ b
In [206]: a = a ^ b
In [207]: print a, b
2 1
一些其他特性：
0 ^ n = n
n ^ n = 0
题中仅有两个值是唯一的，其它都恰好只有两个。
因此全部进行异或的结果等于只异或两个答案的结果：
假定：
l = [a, b, c1, c2, d1, d2, ......, z1, z2]
中，a，b 是唯一的两个数，其它字母相同的是同样的数。
那么：
c1 ^ c2 = 0
...
z1 ^ z2 = 0
a ^ b ^ c1 ^ c2 ^ ... ^ z1 ^ z2 = a ^ b ^ (c1 ^ c2) ^ ... ^ (z1 ^ z2) = a ^ b ^ 0 ^ ... ^ 0 = a ^ b
因为 a 和 b 是不同的，即 a ^ b != 0，因此他们至少有一位是不同的，如对于 3 和 5 而言，
011 -> 3
^ 101 -> 5
----------
110 -> 6
6 的右数第二、三位均为 1，即 3 和 5 的右数第二、三位是不同的，因此我们可以用这一位来区分 3 和 5。如取第二位，则为 10，值为2。
2 & 3 = 2
2 & 5 = 0
用回 a 和 b 表示即为：若 s = a ^ b，找出 s 从右到左第一个不为 0 的位：
mask = 1
while (s & mask == 0):
mask = mask << 1
然后再次遍历数组，使用条件 num & mask == 0 将数字分为两组，分别取异或 s ，则可以得到 a 和 b。
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
bit_num = 0
for num in nums:
bit_num ^= num
mask = 1
a = b = bit_num
while (bit_num & mask == 0):
mask = mask << 1
for num in nums:
if (num & mask):
a ^= num
else:
b ^= num
return [a, b]
