位运算相关算法

一、异或运算介绍

1、性质介绍

异或运算（XOR，Exclusive OR）是一种位运算符。对于两个位进行异或操作，当且仅当这两个位不同时，结果为 1；如果相同，则结果为 0。

A	B	A^B
0	0	0
0	1	1
1	0	1
1	1	0

• 任何数与自身异或结果为 0。
• 任何数与 0 异或结果为自身。
• 交换性: a^b=b^a。
• 结合性: (a^b)^c=a^(b^c)。

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. 异或运算：先对数组中所有数字进行异或，结果就是目标的两个数的异或值。

2. 区分两数：找到异或结果中任意为1的位置，用于区分这两个数。这可以通过 xor & (-xor) 来实现，提取出最低有效位的 1。

3. 分组异或：根据该位是否为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的位组合起来，最终得到结果。

1. 位计数：使用一个大小为32的数组bitCount来统计数组中所有数字在每个位上1的出现次数。对于每个数字，遍历其32位中的每一位，更新bitCount数组。

2. 寻找结果：遍历bitCount数组，如果某一位的计数不是M的倍数，那么这位一定属于那个出现K次的数。

3. 重建结果：将这些位组合起来得到目标数字。

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;}

运行结果：