260. 只出现一次的数字 III

https://leetcode-cn.com/problems/single-number-iii/

解法一：

与136. 只出现一次的数字 不同之处在于要找的数字有两个。

用了一个很骚的操作diff & -diff,即与自身相反数与操作,得到的二进制数只有一个1(称为set bit),且是diff之中最右的1.

例如3和5

3^5=6:
  011
^ 101
------
  110 
说明3和5从右边第二位开始不同

6是0110
-6是取反加一：0110 -> 1001 -> 1010
  
6&-6=2:
 0110
&1010
------
 0010
 因此6&-6一定能得到最右边的1

根据和2与操作的结果，将所有数分成两组，则3和5一定划分到不同的组，每组之中再异或即可分别找出。

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        diff = 0
        for num in nums:
            diff ^= num
        diff &= -diff
        res = [0, 0]
        for num in nums:
            if num & diff == 0:    #分组
                res[0] ^= num
            else:
                res[1] ^= num
        return res