题意是给一个数组，里面有两个单独的数字，其他数字都出现了两次。请返回这两个单独的数字。返回数字的顺序无所谓，请试图不要利用额外空间。例子，

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]

思路是位运算。先复习一下版本一，找两个相同的数字需要用异或XOR，因为两个相同的数字异或之后为0，或者说一个数字自己异或自己为0，一个非0的数字和0异或会得到这个数字本身。但是看这个题的例子，[1, 2, 1, 3, 2, 5]，中间有两个1和两个2，如果只是处理1和2的部分的话，就非常容易，但是剩下的3和5异或之后并不能得到什么有用的结论，所以这里延伸一步的思路是，将数字分成两组，把两个不同的数字分到不同的组里。举个例子，如果能把input分成如下的两组，当同组的其他数字互相异或完毕之后，就会剩下这两个单独的数字了。

input, [1, 2, 1, 3, 2, 5]

group A, [1, 1, 3]

group B, [2, 2, 5]

首先，将相同的数字分到同一组很简单，因为把input中所有数字异或起来的结果一定不是0，所以可以用这个结果和1做&操作来找到第一个不为0的首位。

// 将数组所有元素进行异或，最后的结果一定是那两个单一数字的异或结果 // 用示例[4,4,6,1]最后的抑或结果就是 6和1异或的结果 7 for (int i = 0; i < nums.length; i++) {     sum ^= nums[i]; }   int first = 1; //通过与运算找到result第一个不为0的digit，7=>0111，也就是第一位 while ((sum & first) == 0) {     first = first << 1; }

找到sum中第一个不为0的digit之后，可以把这个first当做一个mask来帮助分组。因为两个不同元素之间做XOR操作的时候，二进制相同位置上的数字若不同会返回1，所以需要找到最低位的1，即可将两个不同的数字区别开了。当nums里的每个数字和这个first做&操作的时候，相同的数字一定会被分到同一组里。之后每一组里的数字互相做XOR操作，最后两组各自剩下的元素就是那两个单独的元素。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int[] singleNumber(int[] nums) {
 3         int sum = 0;
 4         // 将数组所有元素进行异或，最后的结果一定是那两个单一数字的异或结果。看上图示例
 5         // 用示例[4,4,6,1]最后的抑或结果就是 6和1异或的结果 7
 6         for (int i = 0; i < nums.length; i++) {
 7             sum ^= nums[i];
 8         }
 9         int first = 1;
10         // 通过与运算找到result第一个不为0的首位，7=>0111，也就是第一位
11         while ((sum & first) == 0) {
12             first = first << 1;
13         }
14         // first为1，所以我们可以根据数组元素的二进制低位第一位是否为1，将数组分为2类，
15         // 示例数组可以分为     低位第一位为0：[4,4,6]     低位第一位为1：[1]
16         // 此时再将两个数组两两异或就可以得到最终结果。
17         int[] result = new int[2];
18         for (int i = 0; i < nums.length; i++) {
19             //将数组分类。
20             if ((nums[i] & first) == 0) {
21                 result[0] ^= nums[i];
22             } else {
23                 result[1] ^= nums[i];
24             }
25         }
26         return result;
27     }
28 }