剑指offer：数组中只出现一次的数字

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

思路：首先想到遍历、哈希表等，遍历的话时间复杂度O(n²)，哈希表空间复杂度和时间负责都均为：O(n)，于是，想到了利用位运算去重的方法。

关于异或去重的原理，已经有很多博文讲过，推荐一篇http://blog.csdn.net/ns_code/article/details/27568975

直接上代码：

public class code_3_solution {
    /***
     * 数组中只出现一次的数字
     * 题目描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字
     */
    public static void findNumOnce(int[]arr) {
        int num = 0;
        for(int i=0;i<arr.length;i++) {
            num ^= arr[i];
        }
        int index = indexOfBit1(num);
        int num1=0;
        int num2=0;
        for (int i=0;i<arr.length;i++) {
            if(isBit1(arr[i], index)==0) num1 ^= arr[i];
            else num2 ^= arr[i];
        }
        System.out.println(num1+ ", "+ num2);
    }

    public static int isBit1(int num, int index) {
        return ((num >> (index-1)) & 1);
    }

    public static int indexOfBit1(int num) {
        /**
         * 二进制表示时右边第一个为1的位
         */
        int index = 1;
        while((num & 1) == 0) {
            index++;
            num = num >>1;
        }
        return index;
    }

    public static void main(String[]args) {
        int[] arr= {2,4,3,6,3,2,5,5};
        findNumOnce(arr);
    }
}