这里分享一道leetcode里的算法题目，链接leetcode

这个题目很巧妙的利用了位运算。

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

如果用容器，比如HashMap，那空间复杂度不可能是O(1)。看用位运算是如何解决这个问题的。

java异或运算（^）

异或的运算方法，是二进制运算。

1^1 = 0 ,
0^0 = 0,
1^0 = 1,
0^1 = 1
简单一句话，相同为0，不同为1

举个例子， 4^3

4的二进制：100
6的二进制：110
然后看4^6 ：010 转化成十进制就是2

异或运算法则
1. a ^ b = b ^ a
2. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
3. d = a ^ b ^ c 可以推出 a = d ^ b ^ c.
4. a ^ b ^ a = b
很显然：
a^a = 0，即与自身异或，得0;
a^0 = a，即与0异或，得自身

回到本文的那个算法题目，如果是，数组里，仅有一个出现了一次，其它都出现了两次，那将数组里所有的数字异或，最后的结果就是那个出现一次的。

比如[1,2,3,4,3,2,1]  那么：1^2^3^4^3^2^1 = 1^1^2^2^3^3^4 = 4    因为a^a = 0  a^0 = a

如果这个理解的话，这个算法题目就可以入手了。把数组分成两部分，每部分中都满足：仅有一个数字出现一次，其它出现两次。那就可以找到这两个数字了。

怎么分成两部分呢？ 假设数组nums中，a和b仅出现了一次。

nums中所有数字异或结果=a^b

假如 a^b = 2（二进制10），即二进制低二位上，a和b不一样。那么 a&2 和 b&2 一定不相等。这样就把a和b分开了。 ----即二进制位中，找一个是1的。

nums中，其它的数字，同样和2做相与操作（x&2），即可分成两部分。
文字叙述不好理解，咱们上代码

    public int[] singleNumbers(int[] nums) {if(null == nums){return null;}int bit = 0; // 所有数字异或的结果for(int num : nums){bit ^= num;}int last = 1; // 获取异或结果中低位1while((last & bit) == 0){last <<= 1;}int a = 0;int b = 0;for(int num : nums){// 分成两组（a和b如何分，上文说过了。同一个数字，相与num，结果一定相同，即一定分到同一组）if((last & num) == 0){a ^= num;}else{b ^= num;}}return new int[]{a,b};}