算法题：只出现一次的数字

最近看到了一个很有启发性的题目：

一个 int 类型的数组，除了【某两个】数字只出现了一次以外，其他数字均恰好出现了两次，找出这两个只出现一次的数。

当然，乃只能用常数级的额外空间（不然用哈希表计数就好了，还做个毛）。

——Leetcode 第 260 题。

---

如果出现一次的数字只有一个，那么显然直接把全部数字求异或（符号用 ⊕ 来表示）即可得出。现在有两个单独的元素（假设为 a 和 b），那么全部异或的结果就变成了 a ⊕ b。如何得到 a 和 b？

由于 a ≠ b，所以 a ⊕ b ≠ 0。也就是至少有一位是 1，如果我们任取其中为 1 的位，那么 a 和 b 分别与之异或后，一定有一个结果为 0，而另一个结果不为 0。对于数组中的每一个数字，我们检查这位是否为 1，为 1 的分到一组，为 0 的分到另一组。这样，a 和 b 必然被分到了不同的两组，其他相同的数字也必定被分到了同一组。酱紫的话，这两个数组就都变成了只有一个不重复的数字了。

所以，我们的算法步骤如下：

1. 对数组的全体元素求异或，得出的结果为 a ⊕ b。
2. 任取 a ⊕ b 中不为 0 的位，其他位置为 0，令这个数为 mask。
3. 针对数组中的每个数字，与 mask 求“与”（AND）操作，结果为 0 的分为 A 组，不为 0 的分为 B 组。
4. 按照上面的结论，a 和 b 必然被分在了不同的组里。此时我们对每组中的元素分别求异或，则两组数字最终的结果就是 a 和 b。

在实际编码过程中，我们并不需要真的将元素分到两个集合里面（这样的话空间复杂度就变成 O(n) 啦，还不如直接用哈希表计数），只需要计算与 mask 求与运算的结果不为 0 的数字，得到其中一个只重复一次的数。由于我们已经求出了 a ⊕ b，所以与 a ⊕ b 再次异或就可以求出另一个数。

那么这个 mask 怎么求呢？比较简单的方法是写一个循环遍历每一位，找到不为 0 的位即可（以下代码中，aXb 表示 a ⊕ b 的结果）：

            int mask = 1;
            for (int i = 0; i < 32; i++)
            {
                if ((aXb & mask) != 0) break;
                mask <<= 1;
            }

一个更好的办法是利用补码来求出（请自行脑补相关知识）：

mask = aXb & (-aXb)

酱紫的话，代码就一气呵成啦：

    public int[] singleNumber(int[] nums) {
        // 1. 求出 a ⊕ b
        int aXb = 0;
        for (int num : nums) aXb ^= num;

        // 2. 取 a ⊕ b 的最右不为 0 的位，取其他不为 0 的位也可
        int mask = aXb & (-aXb);

        // 3. 将数组中有与 mask 相同位的数字分到一组，求异或，得出 a 或 b 其中之一
        int a = 0;
        for (int num : nums) {
            if ((num & mask) != 0)
                a ^= num;
        }

        // 4. 则 b 为 a ⊕ (a ⊕ b)
        return new int[] {a, a ^ aXb};
    }