- 异或运算：如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。
- 题目一：136. Single Number【 leetcode】
一个整型数组里除了一个数字之外，其他的数字都出现了偶数次。请写程序找出这一个只出现一次的数字。
思路：任何一个数字异或它自己都等于0；与0异或都等于它本身
# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
# write code here
res = 0
for i in range(len(array)):
res ^= array[i]
return res
- 题目二：
一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。
思路：
# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
# write code here
xor = 0
for i in range(len(array)):
xor ^= array[i]
mark = 1
#找到从低位到高位访问XOR的第一个等于1的那一位
while xor & mark == 0:
mark <<= 1
#然后根据该位是否为1，将数组分成两个子数组,分别取求异或
res1,res2 =0 ,0
for i in range(len(array)):
if array[i]&mark == 0:
res1 ^= array[i]
else:
res2 ^= array[i]
return [res1,res2]
题目三：
有一个数组，每个数字都出现了3次，除了其中的某一个只出现了1次。找出这个只出现了1次的数字。
思路：这个题的做法是把32位的二进制数进行遍历，统计每个数字的每一位出现的和。因为每个数字出现了3次或者1次，所以如果某一位出现的次数不是3次，那么这个位置一定是因为那个只出现1次的数字导致的。用来保存结果的res是0，因此使用或操作，就能把这个位置的数字变成1.该问题也可以用字典哈希来做，但是那样的话空间复杂度为O(n)
# -*- coding:utf-8 -*-
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = 0
for i in range(32):
cnt = 0
#统计32位中的每一位出现1的次数
mask = 1 << i
for num in nums:
if num & mask:
cnt += 1
#如果该位上出现1的次数不能被3整除，则一定是因为唯一的那个出现一次的数导致的
if cnt % 3 == 1:
#保留该位，与res求或运算
res |= mask
#以后出现位运算的时候，需要对结果进行判断一下最好。
# 如果不在这个范围内，说明了结果被认为是无符号的数了，需要减去2 ^ 32
if res >= 2 ** 31:
res -= 2 ** 32
return res
