![位运算取第一个非0的位 r & (~(r-1)) 位运算取第一个非0的位 r & (~(r-1))](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
Single Number III
Given an array of numbers nums
, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5]
, return [3, 5]
.
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
[1,1,2]=>1 xor 1 xor 2=2
[1, 2, 1, 3, 2, 5]=> all xor= 3 & 5 != 0 => 0x11 xor 0x101=bit 2,3 is not equal=>find bit2 and seperate like [1,1,2]
"""
r = 0
for num in nums:
r = r ^ num
assert r != 0
n = r & (~(r-1))
ans1, ans2 = 0, 0
for num in nums:
if num & n == 0:
ans1 = ans1 ^ num
else:
ans2 = ans2 ^ num
return ans1, ans2