整数数组 sockets 记录了一个袜子礼盒的颜色分布情况，其中 sockets[i] 表示该袜子的颜色编号。礼盒中除了一款撞色搭配的袜子，每种颜色的袜子均有两只。请设计一个程序，在时间复杂度 O(n)，空间复杂度O(1) 内找到这双撞色搭配袜子的两个颜色编号。

示例 1：

**输入：**sockets = [4, 5, 2, 4, 6, 6]
输出：[2,5] 或 [5,2]

示例 2：

**输入：**sockets = [1, 2, 4, 1, 4, 3, 12, 3]
输出：[2,12] 或 [12,2]

提示：

2 <= sockets.length <= 10000

寻找两个无配对的数字，因为对时间空间复杂度的要求，无法使用哈希表，我们只能在原数组上处理

需要知道相同数字异或结果为零，

假设两个数字为a，b，当我们把所有数字异或后，得到的结果就是a^b

再想分别得到a和b我们需要有一个条件，在异或时能把a，b分开

考虑到a，b的二进制表示，a^b的某一位为0说明a，b该位值相等，为一则不等，那我们就可以根据为一的那位值来区分a，b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> sockCollocation(vector<int> &sockets) {
        int sum = 0;
        for (int i : sockets)
            sum ^= i； int mid = 1;
        int a = 0, b = 0;
        while ((sum & 1) == 0) {
            sum >>= 1;
            mid <<= 1;
        }

        for (int i : sockets) {
            if ((i & mid) == mid) {
                a ^= i;
            } else {
                b ^= i;
            }
        }
        return {a, b};
    }
};