56(1)-数组中数字出现的次数

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

我们知道，一个数字与自己做异或操作，肯定会得到0，和不同的数字异或，肯定不是0。假如数组中只有一个数字出现了一次，其他数字都出现了两次，那么利用上面的性质将所有数字异或，最终得到的就是出现一次的数字。

但是现在是两个数字出现了一次，如何利用上面的结论呢？二分法又要上场了，假如我们能将这俩个出现一次的数字拆开到两个数组里就能利用上面结论解决了。

我们首先将数组中的数字全部异或，那么肯定是得到一个不为0的数字，比如r=010101010，我们获取最终这个数字的一个为1的位，比如r的从右往左数的第二个数字，然后我们在重新遍历数组，将数字按照第二位是否是1进行分组，为1的分一组，为0的分一组，这样就能将这两个数字分到两个不同的数组中。

 public int[] singleNumbers2(int[] nums) {
        int x = 0, y = 0, n = 0, m = 1;
        for(int num : nums)               // 1. 遍历异或
            n ^= num;
        while((n & m) == 0)               // 2. 循环左移，计算 m
            m =  m << 1;
        for(int num: nums) {              // 3. 遍历 nums 分组
            if((num & m) != 0) x ^= num;  // 4. 当 num & m != 0
            else y ^= num;                // 4. 当 num & m == 0
        }
        return new int[] {x, y};          // 5. 返回出现一次的数字
}