一个整形数组中除了两个数字外，其它的数字都出现了两次，将这两个数字打印出来

import com.google.common.base.Preconditions;

import java.util.Arrays;

/**
 * 一个整形数组中除了两个数字外，其它的数字都出现了两次，将这两个数字打印出来。
 */
public class FindSingleNumInArray {


    /**
     * 一个整形数组中除了两个数字外，其它的数字都出现了两次，获取这两个数字。
     *
     * 思路：
     * 1)任何一个数字和自己本身做异或操作的结果都为0，任何一个数字和0做异或操作的结果都为数字本身。
     * 2)将所有的元素一起做异或操作
     * 3)异或操作的结果的二进制表示中，按照从右往左的顺序，找到第一个1出现的位置bitNum
     * 4)将数组中的元素分为两类：
     *      1>第一类：从右边开始数第bitNum位上的数字为1的元素
     *      2>第二类：从右边开始数第bitNum位上的数字为0的元素
     * 5)分别对两类元素做异或操作，异或操作的结果即只出现一次的两个元素。
     *
     * @param array
     * @return
     */
    public static int[] getSingleNums(int[] array) {

        Preconditions.checkArgument(null != array && array.length > 2);

        int[] result = {0, 0};

        // 异或操作的结果
        int result4xor = 0;

        // 将所有的元素一起做异或操作
        for (int i = 0; i < array.length; i++) {
            result4xor ^= array[i];
        }

        // 异或操作的结果的二进制表示中，按照从右往左的顺序，找到第一个1出现的位置
        int bitNum = findFirst1(result4xor);

        /**
         * 将数组中的元素分为两类：
         *  第一类：从右边开始数第bitNum位上的数字为1的元素
         *  第二类：从右边开始数第bitNum位上的数字为0的元素
         *
         *  说明：
         *      1)若这两个只出现一次的元素都不为0，那么这两个元素一定不是同一类元素。
         *      2)若这两个只出现一次的元素中有一个元素为0，那么无论0属于哪一类元素，都不会对异或的结果造成影响，
         *          此时 两类元素分别做异或操作的结果必定为 只出现一次的非0元素 和 0，即结果仍然是这个两个元素。
         *
         */
        for (int number : array) {
            if (is1(number, bitNum)) {  // 第一类所有的元素做异或操作，最终的结果即只出现一次的元素
                result[0] ^= number;
            } else {                    // 第二类所有的元素做异或操作，最终的结果即只出现一次的元素
                result[1] ^= number;
            }
        }
        return result;
    }


    /**
     * 在number的二进制表示中，按照从右往左的顺序，找到第一个1出现的位置。
     * <p>
     * (number & 1) == 0 表示number是偶数，即在number的二进制表示中最后一位上的数字为0
     * (number & 1) == 1 表示number是奇数，即在number的二进制表示中最后一位上的数字为1
     *
     * @param number
     * @return
     */
    private static int findFirst1(int number) {

        Preconditions.checkArgument(number != 0);

        /**
         * 按照从右往左的顺序，第一个1出现的位置。
         * 因为number不等于0，故number的二进制表示中一定存在1，所以将bitNum初始化为1。
         */
        int bitNum = 1;

        // 若最后一位不为1，则将num无符号右移一位。
        while ((number & 1) == 0 && bitNum < 32) {
            number >>>= 1;
            bitNum++;
        }

        return bitNum;
    }


    /**
     * 判断number的二进制表示中，从右边开始数第bitNum位上的数字是否为1
     *
     * @param number
     * @param bitNum
     * @return
     */
    private static boolean is1(int number, int bitNum) {

        // number无符号右移 bitNum-1 位后，原本第bitNum位上的数字就被移动到最右边了
        number >>>= bitNum - 1;

        // 根据最右边上的数字来判断原本第bitNum位上的数字是否为1
        return (number & 1) == 1;

    }


    public static void main(String[] args) {
        int firstBit1 = findFirst1(9);
        boolean bit1 = is1(9, firstBit1);
        System.out.println(firstBit1);
        System.out.println(bit1);

        int[] array = {2, 2, 3, 3, 5, 5, 4, 6};
//        int[] array = {2, 2, 3, 3, 5, 5, 4, 0};
//        int[] array = {0, 0, 3, 3, 5, 5, 4, 6};
        int[] singleNums = getSingleNums(array);
        System.out.println(Arrays.toString(singleNums));

    }

}