异或

异或运算：相同为0，不同为1

口诀：无进位相加

异或运算的性质：①0^N==N   N^N==0

　　　　　　　　②异或运算满足交换律和结合律

练习一：如何不用额外变量交换两个数（A、B）

　　int a = A；   int b = B；

　　int a = a^b;     //A^B

　　int b = a^b;     //A^B^B = A

　　int a = a^b;     //A^B^A = A^A^B = B

练习二：一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数

　　解题方法：将该数组中的全部元素进行异或运算

　　解题原理：若数组中元素为[A,B,C,F,G,B,G,F,C]，该数组中只有A出现奇数次

　　　　　　　A^B^C^F^G^B^G^F^C = A^B^B^C^C^F^F^G^G = A

练习三：如何把一个整形的数的二进制值中提取出最右侧的1

　　　　例如：N                 = 0。。。01101010000要得到最右侧的1，只需要N&((~N)+1)

　　　　　　　~N               = 1。。。10010101111

　　　　　　　~N + 1         = 1。。。10010110000

　　　　　　　N&((~N)+1) = 0。。。00000010000

练习四：一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数(假设，数组中a和b出现的次数为奇数次)

　　思路：①将数组中所有的元素进行异或==>eor = a^b ；

　　　　　　此时说明a与b的二进制一定在某一位上有一个数为1，另一个数为0

　　　　　②此时我们进行(a^b)&((~(a^b))+1)操作，提取出最右侧的1，记为rightOne

　　　　　③遍历数组，数组元素arr[i]&rightOne进行判断

　　　　　　若==0，让通过的元素进行异或操作，得到其中一个出现奇数次的元素，假设为a

　　　　　④eor^a = b

        int[] arr = {5,3,4,8,7,1,4,3,1,8,7,2};
        int eor = 0;
        int rightOne = 0;
        int one = 0;
        int nextOne = 0;

        for (int i = 0; i < arr.length; i++){
            eor ^= arr[i];
        }
        //获取二进制最右边的1
        rightOne = eor&(~eor+1);
        //按照最右边的1将数组进行分组
        for (int i = 0; i < arr.length; i++){
            if ((arr[i] & rightOne) == 0){
                one ^= arr[i];
            }
        }
        nextOne = eor ^ one;
        System.out.println("one is" + one + "the nextOne is" + nextOne);    

练习五：计算出一个二进制数中1的个数(假设该值为a)

　　思路：①while循环中，rightOne = a&(~a+1); 

　　　　　②count++; 

　　　　　③a^a&(~a+1);