数组中只出现一次的两个数字（异或法思路）

题目简介

一个数组中只有2个数字只有一个，其他数字都有两个。找出这两个数字。a, b

用HashMap记录就不说了。

这里记录一下用异或的方式解决。

1. 由于异或特性为自己异或自己为0。a^a = 0;
2. 所以可以异或数组中的所有数字得出 a^b 的结果，其他相同的都消掉了。
3. 又a != b 因此，a^b 的结果在二进制中，肯定有一位是1。这个也好理解。

下面就是我半天不能理解的点了。这里记录一下。

上面说a^b 肯定有一位是1。然后通过遍历数组的所有项，以这一位是不是为1分成两组。

我就很纳闷，理解了很久，为什么以这个条件分成两组。

后来终于想到

因为a^b至少有一位是1的话，那么在a 和b的二进制当中，这一位一定是1个为0，一个为1。

比如：

a: xxx0xx,
b: xxx1xx,

这样通过这一位去分组的话。就拿到两个数组，分别存在a和b。这两个数组的其他项不用担心，也一定是有重复，可以异或成0的。

如：

arr1: [a, 1, 1, 2, 2];
arr2: [b, 2, 2, 3, 3];

进一步理解，既然a的这一位为0（举例），那么数组中其他这一位 为0的就不可能是b。

那我怎么知道其他这些数字能两两成对呢？

因为这一位是0 的数字有一个满足的话，那和他相同的那个数字也能满足。就一定是成对出现的。（反证法了属于😂）

这样通过遍历arr1 的所有项就能获取a的值了。

获取b的值也可以复用刚才a^b 的结果。使a^b^a = b了；

至于怎么获取这一位变成 0001000，就看其他文章，本文不做讨论。

代码就不放了。思路最重要。