[ = 链接直达 - 只出现一次的数字III = ]

---

2 解题思路

给定一个数组, 数组中只有两个出现一位的数;

• 假设这两个数设为a, b那么通过异或^所有数就可以得到最终的结果一定是 a^b;

  • 为什么有上面的这个结论?

    设几组数据:

    vector<int> nums1 = [1,2,1,3,2,5];
    vector<int> nums2 = [2,2,3,3,5,9,1,1,4,4];
    

    异或得出的答案为相同为0, 相异为1, 因此出现两次的数将会互相抵消, 如:

    2^2
    
    0010
    0010
    ----
    0000
    

    因此最终所有出现偶数次数的数将会被另一个相同的数抵消, 因此得出来的结果一定是a^b;

从上述结论我们就可以将问题简化, 假设上文出现的[1, 2, 1, 3, 2, 5], 其所有数字相异或^的结果为 3^5得6;

现在的答案就是如何将6分为3^5;

这里有一个小巧思, 我们需要用上原反补码的知识, 即通过原码去&补码, 那么我们绝对能得到一个二进制位某一位为1的数;

• 以6为例

  6的原码为0000 0110, 通过&-6;

  其中我们知道, -6的原码为 1000 0110, 而负数在内存中的存储方式是补码的方式, 而补码为反码+1;

  因此能得到, -6的反码为 1111 1001, 其补码为 1111 1010;

  通过正数&负数, 那么一定能得到其中一位保留位:

  1111 1010
  	0000 0110
  ----------------
  	0000 0010
  

由于在按位与之前, 我们知道这个数是通过两个数异或而来的(简化为两个数[a^b], 其他数都相互抵消), 因此这个相同按位&出来的保留位, 一定是a与b在二进制中的不同一位;

此时我们已经知道了两个数在这个二进制位上不同, 因此可以将所有的数进行相&进行分组;

• 与这个位相 & 结果为1的分一组

  2, 2, 3
  

• 与这个位相& 结果为0的分一组

  1, 1, 5
  

将两个分组进行再异或一次就能得到最终答案;

---

2.1 解题思路简化

1. 得出所有数的异或结果得到a^b

2. 将a^b按位与&上他的负数

   即 (a^b) & -(a^b);

   根据补码计算, 会留下一位保留位(掩码);

   这个保留位是a与b中不同的一位;

3. 将所有数按位与&这个结果( (a^b) & -(a^b))来进行分组

4. 将所分的两组再次按位异或^

---

2.2 核心动作讲解

其实本题的核心是怎么将两个数去进行区分, 而这里做了一个很明显的动作就是将按位异或得到的结果去按位与上他们的负数通过补码操作来取不同值;

我们来进行实验, 是否属实;

该题类似的所有数据我们都将简化为a^b的结果, 不再去考虑出现两次的数据;

• 第一组

  int a = 10, b = 8;
  

  

• 第二组

  int a = 52, b = 66;
  

  

• 第三组

  int a = 168, b = 21474836473;
  

  

从给出的这几组数据中可以看到, 当出现a!=b时, -(a^b) & (a^b)一定能找到a与b在二进制位中第一个不同的位;

---

2.3 溢出防治

在上述解题思路中, 我们得到了一个结论 —— =="当出现a!=b时, -(a^b) & (a^b)一定能找到a与b在二进制位中第一个不同的位"== ;

在这个操作中, 我们进行了一个数对其负数进行按位与运算从而取得a与b中在二进制中, 由低位向高位的第一位为1的位结果;

而在这种操作下, 我们需要做出一定的防溢出;

首先我们得知道为什么需要防溢出, 在c++中, int类型的范围为[-2147483648, 2147483647];

其中-2147483648在c++中被定义为INT_MIN, 对应的 2147483647被定义为 INT_MAX;

且我们需要对一个负数进行取反操作;

对应的, 2147483648的二进制为:

1000 0000 0000 0000 0000 0000 0000 0000

如果将这个数变为负数, 将会变为:

1 1000 0000 0000 0000 0000 0000 0000 0000 [原码]
1 0111 1111 1111 1111 1111 1111 1111 1111 [反码]
1 1000 0000 0000 0000 0000 0000 0000 0000 [补码]

这个行为将是一个未定义行为, 即一个数的负数仍是他自己;

• 方法一

  方法一是, 我们可以使用所给数据中更大的数值类型来存储对应的数据从而避免溢出问题;

  如该题中所给的数据为INT类型, 我们可以采用long long长整型来对数据进行存储以避免出现溢出现象, 这是可取的, 但是治标不治本;

  如果题目中所给的类型longlong, 那么是否需要使用更大的数值类型来进行存储, 如数组?

• 方法二

  从上述结果我们可以知道, INT_MIN在取反后仍是他自己, 这样会出现未定义行为, 而在力扣中这种行为将会被阻止;

  因此我们只需要判断数组内所有成员按位异或后是否为INT_MIN, 是则不再去进行&它的负数以避免该未定义行为;

---

3 代码

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xornum = 0;
        for(auto it:nums) xornum^=it;

        int lsb = xornum==INT_MIN?INT_MIN:xornum&(-xornum);
        int ret1=0, ret2=0;
        for(auto it:nums){
            if(it & lsb) ret1^=it;
            else ret2^=it;
        }
        return {ret1, ret2};
    }
};