题目描述

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

---

题目考察：

• 相同的两个数字相互异或值为0。
• 两个数字的异或值就是两个数不同数位的最直观表现。

解题思路：

如果是数组中只有一个数出现了一次，那么该数组所有的异或和就这个只出现了一次的数。要是能把原数组拆分成a数组和b 数组，a数组和b数组分别包含一个只出现了一次的数，和其他相同的数。拆分后的数组需要满足的条件：

• 两个只出现一次的数字在不同的组中。
• 相同的数字会被分到相同的组中。

题目解法：

• 遍历nums，将所有值进行异或，遍历完成后得到了两个只出现了一次的数字的异或值。

int ret = 0;
for (int n : nums) 
        ret ^= n;

• 寻找mask（数组分界的标签），前面题目考察的第二点就在这里发挥作用了， 异或值中不为0的位都是两个数的不同的数位。就选去第一个不同的数位作为mask（也可以选择别的数位）。

int mask= 1;
while ((mask& ret) == 0) 
    mask<<= 1

或

mask = ret& (-ret)  //负数的二进制表示，其实是负数的源码 除符号位取反，然后 +1.就是负数的补码就是真正的二进制标识，例如5是00000000 00000000 00000000 00000101，-5是11111111 11111111 11111111 11111011

（这里是详解）

图解

• 将数组按mask分组，然后将分组内的值分别异或，最终得到两个只出现了一次的数字

int a = 0, b = 0;for (int n : nums) {
    if ((div & n) != 0) 
        a ^= n; 
    else
         b ^= n; 
}

最后这篇简书是学习 大佬题解 后自己的理解整理出来的，最最后附上 leetcode原题