java的异或运算

一、题目

输入两个数，交换后输出

二、解题思路

        一开始学习的语言是c语言，里面非常有特色的是指针，通过传引用可以直接交换两个数。但java无法达成这种操作，翻阅资料找到了一种有趣的解法：异或!

异或原理：

a ^ a = 0 ; a ^ 0 = a ; a ^ ( b ^ c ) = ( a ^ b ) ^ c

假设输入两个数a，b，那么：

a = a ^ b

b = a ^ b = ( a ^ b ) ^ b = a ^ ( b ^ b) = a

a = b ^ a = a ^ ( a ^ b ) = ( a ^ a ) ^ b = b

交换成功(*^▽^*)

三、代码

@Test
    public void test2() {
        Scanner scan = new Scanner(System.in);
        int num1 = scan.nextInt();
        int num2 = scan.nextInt();

        num1 = num1 ^ num2;
        num2 = num1 ^ num2;
        num1 = num2 ^ num1;

        System.out.println(num1 + " " + num2);
    }

四、拓展

        学会了上面的简单操作，有两个扩展题大家可以研究一下：

        题目1：一个数组，只有一类数的次数是奇数，其他都是偶数，请找出那个奇数次的数。

        题目2：一个数组，只有两类数的次数是奇数，其他都是偶数，请找出那两个奇数次的数。

        大家可以先自己思考个五分钟，再看怎么解。

4.1 解题思路

        对于题目1大家应该很好理解，因为a ^ a = 0，所以我们只需用0去依次异或，最后那个数就是奇数次的偶数，因为偶数次的都相互抵消了。

        但题目2就有点难度了，假设两个奇数次的数分别是a、b，此时用题目1的解法去解的话，最后的答案是a ^ b。我们要怎么提取那两个数呢？

        里面用到的这个公式就是一个位运算提取的公式，如果大家不理解的话我给你们举个例子：

        100010100 取反得 011101011 

                              +1得 011101100

          和100010100&得 000000100

        仔细观察，此时得到的数是不是原本的数只取最右1。好了，现在我们就可以拿着这个数去依次&，得到a或b中的一个数，那只要再与 a ^ b 异或一次，就可以得到另一个数了。

        这个地方有点难以理解，总体思路就是找到a与b不同的那一位，再去&排除其中一个数，最后再异或即可得到另一个数。

4.2 代码

public class Eor {
    public static void main(String[] args) {
        eor1();
        eor2();
    }

    public static void eor1() {
        int[] arr = new int[]{1,2,2,3,3,3,3};//1是奇数次
        int eor = 0;

        for(int x : arr) {
            eor ^= x;
        }

        System.out.println(eor);
    }

    public static void eor2() {
        int[] arr = new int[]{1,2,2,3,3,3,3,4,4,4};//1和4是奇数次
        int eor = 0;

        for(int x : arr) {
            eor ^= x;
        }

        int right = eor & (~eor + 1);
        int theOne = 0;
        for(int x : arr) {
            //等于1等于0都无所谓，只要提取出其中一个就好
            if((right & x) == 1) {
                theOne ^= x;
            }
        }
        int other = eor ^ theOne;

        System.out.println(theOne + " " + other);
    }
}