leetcode 260 只出现一次的数字 III

题意

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

做法

设两个不同的数是 $a$ 和 $b$， 取所有数的异或和 $x$，有$x = a \oplus b$ 。用 $y = x \ \& -x$ 取出 $x$ 最低的比特 $1$ 位。设 $y = 1 << t$ ，那么就有$a$ 和 $b$ 的二进制表示的第 $t$ 位 不同，一个是 $1$ ，一个是 $0$ 。

将所有数按照二进制表示的第 $t$ 位是 $1$ 还是 $0$ 分成 $A$ 和 $B$ 两组，由于除了 $a$ 和 $b$ 以外的其他数都会出现两次，所以$A$ 和 $B$ 两组的组内异或和的结果即为 $a$ 和 $b$。

代码

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xorsum = 0;
        for (int num: nums) {
            xorsum ^= num;
        }
        // 防止溢出
        int lsb = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum));
        int type1 = 0, type2 = 0;
        for (int num: nums) {
            if (num & lsb) {
                type1 ^= num;
            }
            else {
                type2 ^= num;
            }
        }
        return {type1, type2};
    }
};