XOR的一些性质理解和骚操作

柔光的暖阳◎ 2023-05-21 12:56 32阅读 0赞

## 1.异或运算 ##

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

以上概念能长期记住的概率接近于0。所以，异或运算就记成无进位相加！  
实例：

*  6 对应的二进制：0 1 1 0
 *  4对应的二进制： 0 1 0 0
 *  异或操作的结果：0 0 1 0

## 2.异或的性质 ##

*  0^N == N
 *  N^N == 0
 *  异或运算满足交换律和结合率

以上的三个性质用无进位相加来理解就非常的容易（第三个按照加法的交换律和结合律来理解）

## 3.简单应用 ##

*  如何不用额外变量交换两个数

/** 如何不用额外变量交换两个数 * @author TaoistQu */
    public class XorTest { 
        public static void main(String[] args) { 
            int a = 6;
            int b = -1000;
            //分析将 a = x b = y
            a = a ^ b;  // a ==> x^y b ==>y
            b = a ^ b;  // b ==> x^y^y ==> x^0 == > x a ==>x^y
            a = a ^ b; // x^y^x ==> 0^y == > y
            System.out.println(a);
            System.out.println(b);
        }
    }
    
    结果：
    -1000
    6

*  一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找出打印这种数
 *  一个数组中两种数出现了奇数次，其他数都出现了偶数次，怎么找出打印这两种数

/** * 异或操作的应用 * * @author TaoistQu */
    public class EvenTimesOddTimes { 
        // arr中，只有一种数，出现奇数次
        public static void printOddTimesNum1(int[] arr) { 
            int eor = 0;
            for (int i = 0; i < arr.length; i++) { 
                eor ^= arr[i];
            }
            System.out.println(eor);
        }
    
        // arr中，有两种数，出现奇数次
        public static void printOddTimesNum2(int[] arr) { 
            int eor = 0;
            for (int i = 0; i < arr.length; i++) { 
                eor ^= arr[i];
            }
            // eor = a ^ b
            // eor != 0
            // eor必然有一个位置上是1
            int rightOne = eor & (~eor + 1); // 提取出最右的1
            int onlyOne = 0; // eor'
            for (int i = 0 ; i < arr.length;i++) { 
                if ((arr[i] & rightOne) != 0) { 
                    onlyOne ^= arr[i];
                }
            }
            System.out.println(onlyOne + " " + (eor ^ onlyOne));
        }
    
        public static void main(String[] args) { 
            int a = 5;
            int b = 7;
    
            a = a ^ b;
            b = a ^ b;
            a = a ^ b;
    
            System.out.println(a);
            System.out.println(b);
    
            int[] arr1 = {  3, 3, 2, 3, 1, 1, 1, 3, 1, 1, 1 };
            printOddTimesNum1(arr1);
    
            int[] arr2 = {  4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2 };
            printOddTimesNum2(arr2);
    
        }
    }
    结果：
    7
    5
    2
    3 2

[对应代码的github地址][github]

[github]: https://github.com/TaoistQu/AlgorithmsDataStructures/blob/master/Algorithms/src/main/java/cn/algorithms/part01/xor/EvenTimesOddTimes.java