Single Number III(Medium)

题目: Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.(给定一个整数数组，其中除两个数字只出现一次外，其余数字均出现两次。找出这两个只出现一次的数字。)

例如：

给定 nums = [1, 2, 1, 3, 2, 5]，返回 [3, 5]

解题思路： 首先计算nums数组中所有数字的异或，记为xor

令lowbit = xor & -xor，lowbit的含义为xor从低位向高位(从右往左)，第一个非0位所对应的数字

例如假设xor = 6（二进制：0110），则-xor为（二进制：1010，-6的补码，two's complement）

则lowbit = 2（二进制：0010）

根据异或运算的性质，“同0异1”

记只出现一次的两个数字分别为a与b

可知a & lowbit与b & lowbit的结果一定不同

通过这种方式，即可将a与b拆分开来

public int[] singleNumber(int[] nums) {
        // go through the array and XOR every element, for example, result = 6 (3^5)
        int result = 0;
        for(int num : nums)
                result ^= num;

        // notice that 6^5 = 3, 6^3 = 5
        // now how to find 3 and 5 from 6
        int[] r = new int[2];
        // find the lowest bit of the result
        // let's say 6 (0110), -6 = 1010  0110 & 1010 = 0010
        int lowbit = result & -result;
        // since this bit from the result is 1, we can be sure that
        // a & lowbit and b & lowbit have different result
        for(int n : nums){
            if((n & lowbit) == 0)
                r[0] ^= n;
            else
                r[1] ^=n;
        }
        return r;
    }