位异或运算在一些场景中使用的话,会得到意想不到的效果。比如通过三次 位异或 运算可以用于交换两个数的值:
// 通过三次位运算可以实现两个整数的交换
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代码看异或运算的一些使用示例:
/*
位异或运算
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
通过三次位运算可以实现两个整数的交换
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
*/
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);
}
}
上面的运行结果如下图所示: