LeetCode只出现一次的数字 III Swift

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]

注意：

1. 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
2. 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

思路

class Solution {
    func singleNumber(_ nums: [Int]) -> [Int] {
        let xor = nums.reduce(0, ^)
        //-xor是xor的补码 等于~xor + 1 ，rightOne能获得 xor 的最右侧的一个 1
        let rightOne = xor & -xor
        var x = 0
        for num in nums {
            //能过滤出某位 = 0 的数组
            if rightOne & num == 0 {
                x ^= num
            }
        }
        //xor = x ^ y
        let y = xor ^ x
        
        return [x, y]
    }
}

备注：

x & -x = x & ( ~x + 1 )   

-x 是 x 的补码，等于 ~x + 1 。~x是 x 的反码。

用途： 一般可以用来获取某个二进制数的LowBit,返回最右边的1

机器数是带符号的，在计算机用一个数的最高位存放符号, 正数为0, 负数为1.

正数

原码 = 反码 = 补码

负数

反码 符号位不变，其余位反转

补码 反码 + 1

[+1] = [00000001]原 = [00000001]反 = [00000001]补

[-1] = [10000001]原 = [11111110]反 = [11111111]补

一个8位二进制数, 使用原码或反码表示的范围为[-127, +127], 而使用补码表示的范围为[-128, 127]. 

[10000000]补 =  -128  

[00000000]补 = 0