剑指offer——40.数组中只出现一次的数字

题目描述

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

思路：
使用异或进行位运算。
由于数组中每个数字除了出现1次的两个数字外，剩下的数字都出现了两次。
因此，全数组异或的结果是两个只出现一次的数字异或的结果（相同数字异或=0,0异或任意数字=任意数字本身）。
拿到全数组异或的结果，为1的位置就是两个只出现了一次数字不同的位置，该位置一个数字是0，一个数字是1.
因此找到这个位置后，将全数组划分成两部分（此位置是0的，和，此位置是1的）——判断方法是该数字和判断数字&的结果，如果结果是0，则此数字该位置与判断数字不同。由此分成两部分。
两部分单独异或的结果就是相同的异或为0，最后异或只出现了一次的数字。
两部分的分别异或的结果即为所得。

代码：

//异或运算，A^A=0 0^A=A
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {

       int xor1 = 0;
        for(int i=0; i < array.length; i++)
            xor1 = xor1^array[i];
        //index通过这种方式，得到xor最右边为是1的位置，获得0000100这类的数据，1代表两个数不同的位置。
        int index = xor1&(~xor1+1);
        int result1 = 0;
        for(int i=0; i < array.length; i++){
            if((index & array[i]) == 0)
                result1 = result1^array[i];
        }
        //result1是一个数，将他和xor异或，得到第二个数。
        num1[0] = result1;
        num2[0] = result1^xor1;
    }
}