算法与数据结构02：位运算

• 不使用额外变量，进行两个数的交换
• 一个数组中，一种数出现了奇数次，其余数出现偶数次，找到并打印这种数
• 一个数组中，两种数出现了奇数次，其余数出现偶数次，找到并打印这两种数

public class BitOperation01 {

    public static void main(String[] args) {
        int a = 2;
        int b = 3;

        a = a ^ b; // a = a ^ b
        b = a ^ b; // b = a ^ b ^ b = a
        a = a ^ b; // a = a ^ b ^ a = b

        System.out.println(a);
        System.out.println(b);
    }

}

public class BitOperation02 {

    public static void main(String[] args) {
        int[] arr = {1,4,6,1,6,8,4,9,9};

        int eor = arr[0];
        for (int i = 1; i < arr.length; i++) {
            eor ^= arr[i];
        }

        System.out.println(eor);
    }

}

因为相同的数做异或运算，得出的结果是0，而任何数跟0做异或运算，得出的结果都是该数自身，所以遍历数组中所有的数，进行异或运算，最后得出的结果就是出现了奇数次的数。

public class BitOperation03 {

    public static void main(String[] args) {
        int[] arr = {1,4,6,1,6,8,9,9}; //4和8出现奇数次，现在要找出4和8

        int eor = arr[0];
        for (int i = 1; i < arr.length; i++) {
            eor ^= arr[i];
        }

        //此时eor为 4 ^ 8
        //两个不等的数异或运算，得出的结果必然不等于0，取出eor最右侧的1
        eor = eor & (~eor + 1);

        //此时可以遍历数组，把数组分两组：1、和eor最右侧1相同二进制位上为1的；2、和eor最右侧1相同二进制位上为0的
        //此时出现奇数次的两个数，必然落在不同组，分别对这两组数进行异或运算，得出两个出现奇数次的数
        int a = 0;
        int b = 0;
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & eor) == 0) {
                a ^= arr[i];
            } else {
                b ^= arr[i];
            }
        }
        
        System.out.println(a);
        System.out.println(b);
    }

}