一、异或运算介绍
1、性质介绍
异或运算(XOR,Exclusive OR)是一种位运算符。对于两个位进行异或操作,当且仅当这两个位不同时,结果为 1;如果相同,则结果为 0。
A | B | A^B |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
2、结论
由于上面我们提到了异或运算是满足交换律和结合律的,所以异或运算就有以下特性:
对于 a, b, c 三个变量相异或,无论异或的顺序是什么,结果都是相同的。
a ^ b ^ c = a ^ c ^ b = b ^ c ^ a = b ^ a ^ c = c ^ a ^ b = c ^ b ^ a
二、位运算的应用
1、不用中间变量交换两个数的值
1)介绍
int a = 3;int b = 5;System.out.println("Before swap:\n" + "a = " + a + "\nb = " + b);a = a ^ b;b = a ^ b;a = a ^ b;System.out.println("After swap:\n" + "a = " + a + "\nb = " + b);
运行结果:
2)具体原理图解
3)补充
这样交换只能交换两个不同位置的变量,如果对同一个变量交换,会把这个变量的值变成 0。
所以需要添加一个条件,如果是同一个元素,就不进行交换。
public static void swap(int[] arr, int i , int j) {if(arr[i] != arr[j]) {arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];}}
2、找出只出现一次的元素
1)介绍
在一个数组中,其他元素都出现偶数次,只有一个元素出现奇数次,可以用异或找出它。
public static int findOddTimes(int[] arr) {int ans = 0;for(int i : arr) {ans ^= i;}return ans;}
运行结果:
2)原理图解
3、提取二进制最低有效位的1(最右侧的1)
1)介绍
在之前的文章《Java——二进制原码、反码和补码_原码反码补码-CSDN博客》中有提到过,求一个数的相反数可以使用取反加一的方法,对于变量 a,其相反数为 -a,-a = ~a + 1。
2)详细原理图解
4、求出两个出现奇数次的数
1)介绍
输入数据为一个数组,数组中有两个不同的数 a 和 b 分别出现了奇数次,其他的数都是出现了偶数次。求出这两个不同的数。
首先我们先将数组中的所有数异或起来,然后这时的结果就是这两个不同的数的异或,也就是 a ^ b 的结果。由于这两个数是不同的,所以结果一定不为零,也就是说 a ^ b != 0。所以说这个结果的二进制中一定有某一位是 1,我们就可以通过上面给出的提取最右边的 1 的方法,将最右边的 1 提取出来。然后通过这个 1,我们就可以分辨 a 和 b,因为结果的这一位为 1,所以 a 和 b 的这一位必然不同。
然后我们再将这一数组的所有数分组异或起来,使用上面提取出的最右位置的 1 来分组,这样就可以将 a 和 b 分在不同组中,对于其他数,相同的数一定分在同一组,异或的结果就是 0,所以其他的数是没有什么影响的。
简化一下就是以下步骤:
-
区分两数:找到异或结果中任意为1的位置,用于区分这两个数。这可以通过
xor & (-xor)
来实现,提取出最低有效位的 1。
2)代码
public static void findTwoOddTimesNums(int[] arr) {int xor = 0;for (int i : arr) {xor ^= i;}int diff = xor & (-xor);int a = 0;int b = 0;for (int i : arr) {if ((i & diff) == 0) {a ^= i;} else {b ^= i;}}System.out.println("Two nums: " + a + ", " + b);}
运行结果:
上面的代码也可以改成下面这样:
public static void findTwoOddTimesNums(int[] arr) {int xor = 0;for (int i : arr) {xor ^= i;}int diff = xor & (-xor);int a = 0;for(int i : arr) {if((i & diff) != 0) {a ^= i;}}System.out.println("Two nums: " + a + ", " + (xor ^ a));//这里求出了其中一个数a,由于xor是a ^ b,所以xor ^ a就得到了b}
得到的结果是类似的:
5、找到出现K次的数
1)介绍
输入一个数组,数组中有一个数是出现了K次,其他数都出现了M次,M>1,K<M,找到这个出现了K次的数。
我们可以使用一个数组bitCount统计所有数字在每个位上1的出现次数。
然后就是遍历bitCount数组,如果某一位的计数不是M倍数,就可以证明出现K次的数的这一位一定为1,反之,某一位的计数是M的倍数,则出现K次的数的这一位是0。(能够这样判断的前提是题目中的限制条件,也就是M>1,M>K,而且出现K次的数只有一个,所以说最终某位计数可能是K + M*n,也可能是M*n,由于K<M,显然K + M*n不是M的倍数,而M*n是M的倍数)
然后就可以将出现K次的数的是1的位组合起来,最终得到结果。
-
位计数:使用一个大小为32的数组
bitCount
来统计数组中所有数字在每个位上1的出现次数。对于每个数字,遍历其32位中的每一位,更新bitCount
数组。 -
寻找结果:遍历
bitCount
数组,如果某一位的计数不是M的倍数,那么这位一定属于那个出现K次的数。 -
重建结果:将这些位组合起来得到目标数字。
2)代码
public static int findTimesNum(int[] arr, int K, int M) {int[] bitCount = new int[32];for(int i : arr) {for(int j = 0; j < 32; j++) {if((i & (1 << j)) != 0) {bitCount[j]++;}}}int result = 0;for(int i = 0; i < 32; i++) {if(bitCount[i] % M != 0) {// 不能被M整除,则有出现K次的数在这一位为1result |= (1 << i);// 将最终结果的这一位置为1}}return result;}
运行结果: