medium, bit manipulation
Question
有一个整数序列，其中的每个整数除了一个都出现了3次，找到那个落单的数。
Notes
Time complexity要求O(n)且不能分配新memory
Solution
使用bit操作来解答. 将所有数的第i个bit相加，再模3的结果必然是0或者1，因为数字要么出现3次要么出现1次。然后使用或运算来找到单数。
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ret = 0
for i in xrange(32):
count = 0
for num in nums:
if num>>i & 1:
count+=1
ret |= count%3<<i
if ret >= 2**31:
return ret - 2**32
else:
return ret
另解：使用三个变量
ones -- bitmask表示出现一次的第i个bit
twos -- bitmask表示出现两次的第i个bit
threes -- bitmask表示出现三次的第i个bit
当第i个bit，出现第三次，将ones和twos的第i个bit都清为0，ones的最终值就是answer。
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ones, twos, threes = 0, 0, 0
for num in nums:
twos |= ones & num
ones ^= num
threes = ones & twos
ones &= ~threes
twos &= ~threes
return ones
