位异或运算

位异或运算

位异或运算

• 位异或

位异或

位异或运算在一些场景中使用的话，会得到意想不到的效果。比如通过三次 位异或 运算可以用于交换两个数的值：

  // 通过三次位运算可以实现两个整数的交换
    int a = 12;
    int b = 10;
    a = a ^ b;  // a = 12 ^ 10; b = 10
    b = a ^ b;  // b = 12 ^ 10 ^ 10 = 12 ^ (10 ^ 10) = 12 ^ 0 = 12; a = 12 ^ 10;
    a = a ^ b;  // a = 12 ^ 10 ^ 12 = (12 ^ 12) ^ 10 = 0 ^ 10 = 10

位异或运算满足如下：
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

即位异或运算相同为0， 不同为1（无进位相加）

位异或运算满足交换律和结合律
a ^ b = b ^ a
(a ^ b) ^ c = a ^ (b ^ c)

注意：特殊情况
a ^ a = 0
a ^ 0 = a
可以通过以下的Java代码看异或运算的一些使用示例：

public class Code07_EvenTimesOddTimes {
    // 一个int数组中有一个数出现奇数次，其他数都出现偶数次，请找出这个出现奇数次的数
    // 开心消消乐游戏：是不是也是基于异或算法
    public static int printOddTimesNum1(int[] arr) {
        int eor = 0;
        for (int cur : arr) {
            eor ^= cur;
        }
        //System.out.println(eor);
        return eor;
    }

    // 交换arr数组中下标分别为i和j的元素值
    public static void swap1(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 通过位运算异或交换arr数组中下标分别为i和j的元素值
    public static void swap2(int[] arr, int i, int j) {
       arr[i] = arr[i] ^ arr[j];
       arr[j] = arr[i] ^ arr[j];
       arr[i] = arr[i] ^ arr[j];
    }

    // 打印数组
    static void PrintArray(int[] arr) {
        for (int cur : arr) {
            System.out.print(cur + "t");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = { 1, 3, 4, 9, 15, 1, 3, 15, 9 };
        System.out.println("The xor result is: " + printOddTimesNum1(arr));

        int a = 12;
        int b = 10;
        System.out.println(a + "^" + b + "=" + (a ^ b));
        System.out.println(b + "^" + a + "=" + (b ^ a));
        System.out.println(a + "^" + a + "=" + (a ^ a));
        System.out.println(a + "^" + 0 + "=" + (a ^ 0));

        // 通过三次位异或来交换数组arr2中的9和10
        int arr2[] = { 12, 9, 45, 10, 78, 120 };
        PrintArray(arr2);
        swap2(arr2, 1, 3);
        System.out.println("After xor swap:");
        PrintArray(arr2);
    }
}

上面的运行结果如下图所示：