算法题（25）：只出现一次的数字（三）

审题：

该题中有两个元素只出现一次并且其他元素都出现两次，需要返回这两个只出现一次的数，并且不要求返回顺序

思路:

由于对空间复杂度有要求，我们这里不考虑哈希表。我们采用位运算的方法解题

方法：位运算

首先，由于其他元素都会出现两次，所以我们对整个nums数组的元素进行异或运算之后的结果就等于answer1和answer2的异或结果

根据异或的性质（对应二进制位相同则为0，不同则为1），我们可以找到第一个为1的位，成为第i个位置（在这位置两个只出现一次的数的值一定不同），该位置有两种可能的值，一个是1，一个是0。

于是我们把nums的数据分成两类，第一类是第i位是1，第二类是第i位是0

注意：

对于出现两次的元素：一定会出现在同一类中，要么第i位是1，要么是0。

对于两个出现一次的元素：一定会出现在不同类中。

于是我们可以分情况进行异或运算

当nums的第i位是1：用type1进行异或运算，得到的最终结果就是其中一个只出现一次的数据

当nums的第i位是0：用type2进行异或运算，得到的最终结果就是另一个只出现一次的数据

这是因为出现两次的数据一定出现在同一个类中（比如某个数第i位是1，那么由于它出现了两次，他就会参与到type1的异或运算，然后被消掉），在异或计算中根据异或的结合律和分布律，可以把出现两次的数据消掉

解题：

核心代码解释

（1）找到sum第一个二进制位置为1的位置，并取得只有该位置为1的数：

num = sum & (-sum)

sum是answer1和answer2的异或结果，而-sum是由sum的二进制数全部按位取反，然后加一的结果，从第32位开始看，-sum第一个出现1的位置就是sum第一个出现1的位置。

因为取反之后加一会让取反为1的进位，第一个取反为0的会因为前面的进位而变成1，而第一个取反为0的位置，取反前就是1。所以sum和-sum第一个出现1的位置是同一个位置，而其他位置进行位与操作后都会变成0（第i个位置前的sum和-sum都为0，第i个位置后则是相反）

（2）判断第i位是否为1：e & num

由于num除了第i位是1，其他位都是0，所以e的第i位若是1，则结果非0.否则结果为0

260. 只出现一次的数字 III - 力扣（LeetCode）