【剑指Offer 40】数组中只出现一次的数字

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

代码如下：

package demo;

/**
 * 数组中只出现一次的数字
 * 
 * @author xiangdonglee
 *
 */
public class Test40 {
    public static int[] findNumbersAppearanceOnce(int[] data) {
        int[] result = { 0, 0 };
        if (data == null || data.length < 2) {
            return result;
        }
        int resultExclusiveOR = 0;
        for (int i : data) {
            resultExclusiveOR ^= i;
        }
        int indexOf1 = findFirstBit1(resultExclusiveOR);
        for (int i : data) {
            if (isBit1(i, indexOf1)) {
                result[0] ^= i;
            } else {
                result[1] ^= i;
            }
        }
        return result;
    }

    /**
     * 在整数num的二进制表示中找到最右边是1的位
     * 
     * @param num
     * @return
     */
    private static int findFirstBit1(int num) {
        int index = 0;
        while ((num & 1) == 0 && index < 32) {
            num >>>= 1;
            index++;
        }
        return index;
    }

    /**
     * 判断在整数num的二进制表示中，从右边数起的indexBit位是不是1
     * 
     * @param num
     * @param indexBit
     * @return
     */
    private static boolean isBit1(int num, int indexBit) {
        num >>>= indexBit;
        return (num & 1) == 1;
    }

    public static void main(String[] args) {
        int[] data1 = { 2, 4, 3, 6, 3, 2, 5, 5 };
        int[] result1 = findNumbersAppearanceOnce(data1);
        System.out.println(result1[0] + " " + result1[1]);

        int[] data2 = { 4, 6 };
        int[] result2 = findNumbersAppearanceOnce(data2);
        System.out.println(result2[0] + " " + result2[1]);

        int[] data3 = { 4, 6, 1, 1, 1, 1 };
        int[] result3 = findNumbersAppearanceOnce(data3);
        System.out.println(result3[0] + " " + result3[1]);
    }
}

来源：http://blog.csdn.net/derrantcm/article/details/46771717