数组中只出现一次的数字

题目描述

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

分析

我们知道异或运算可以用于找出数组中唯一一个只出现一次其余都出现两次的数字，因为相同的数异或后等于0。

• 首先将数组依次异或，得到题干中两个数字的异或结果。这个找出结果二进制中的第一个1，根据这这一位分组。比如第2位，也就说明两数在这一位不同。
• 如果将原数组根据这一位分组，就能将两数分到不同的组中，对于其余的数，因为出现了两次，那么相同的数也肯定会被分到一组。之后两组分别进行异或，得到的就是两个结果数字了。

实现

public void FindNumsAppearOnce(int[] array, int[] num1, int[] num2){
        int length = array.length;
        if(length == 2){
            num1[0] = array[0];
            num2[0] = array[1];
            return;
        }
        int bitResult = 0;
        for(int i = 0; i < length; ++i){
            bitResult ^= array[i];
        }
        int index = findFirst1(bitResult);
        for(int i = 0; i < length; ++i){
            if(isBit1(array[i], index)){
                num1[0] ^= array[i];
            }else{
                num2[0] ^= array[i];
            }
        }
    }

    private int findFirst1(int bitResult){
        int index = 0;
        while(((bitResult & 1) == 0) && index < 32){
            bitResult >>= 1;
            index++;
        }
        return index;
    }

    private boolean isBit1(int target, int index){
        return ((target >> index) & 1) == 1;
    }