数组中只出现一次的数字 JAVA

数组中只出现一次的数字——剑指OFFER原题

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

假设，数组A中只有一个数字出现一次，其余都是出现两次，我们可以用一次遍历异或解决，例如数组A｛1，2，1，2，3｝，将这五个数字异或的结果是3，不信你可以自己试试。原理就是两个相同的数字异或结果为0，0和任意数字异或，都是该数字本身

但是我们现在的问题是数组B｛1，2，1，2，3,4｝中有两个数字只出现一次，那你异或遍历数组的结果C显然不是我们要的。但是这个结果应该是两个只出现一次的两个数字的异或结果，结果应该是不为0的。既然我们能从一个数组A中找到只出现一次的数字，那么我们就要根据这个条件，将B数组分成两个A数组不久可以直到我们的结果了么！即我们要根据某种条件将两个只出现一次的数字分别分到两个数组中，再异或后，两个数组异或的结果就是两个只出现一次的数字。那么这个分离条件是什么呢？结果C可以告诉我们这两个只出现一次的数字的二进制数哪几位是1，我们根据这个条件将B数组分离，B数组的异或结果是7，说明两个只出现一次的数字在第一位，第二位，第三位都是不一样的。那么我们将这个结果的最高位不为1的位值，将B数组区分开来，分成{1,2,1,2,3}和｛4｝那分别异或后，结果就出来了

JAVA代码如下：

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        //找到整个数组异或结果最高的不为0 的位置
    	//根据这个位置将数组分成两个部分，部分内数字分别亦或，结果就是两个只出现一次的数字
    	int location = startXOR(array);
    	int result1 = 0;
    	int result2 = 0;
    	for(int i = 0; i< array.length; i++) {
    		if(IsBitOne(location,array[i])) {
    			result1 ^= array[i];
    		} else {
    			result2 ^= array[i];
    		}
    	}
    	num1[0] = result1;
    	num2[0] = result2;
    }
    
    public int startXOR(int[] array) {
    	int result = 0;
    	int len = array.length;
    	if(len <= 0) return -1;
    	for(int i = 0; i < len; i++) {
    		result ^= array[i];
    	}
    	return findFirstBitOne(result);
    }
    
    public int findFirstBitOne(int value) {
    	if( value == 0 ) return -1;
    	int count = 0;
    	while(value >0) {
    		count++;
    		value = value>>1;
    	}
    	return count;
    }
    
    public boolean IsBitOne(int location, int value) {
    	value = value>>(location-1);
    	return ((value&1) == 1);
    }
}