class 030 异或运算的骚操作

这篇文章是看了“左程云”老师在b站上的讲解之后写的, 自己感觉已经能理解了, 所以就将整个过程写下来了。

这个是“左程云”老师个人空间的b站的链接, 数据结构与算法讲的很好很好, 希望大家可以多多支持左程云老师, 真心推荐.
https://space.bilibili.com/8888480?spm_id_from=333.999.0.0

1. 异或运算的诠释

一定一定要注意的问题：在经过有位运算的代码实现的时候, 一定要时刻想着 2进制 和 溢出问题, 不然会理解困难.

1.1 异或运算性质

1.1.1 异或运算就是无进位相加

举一个例子：

用 8 位举例A：01101110
B：10011101A^B = 11110011

进位相加就是 1 + 1 == 2, 此时应该是将前面一位进一, 1 + 1 == 0 , 然后将前面一位数字进一.
无进位相加： 不进一, 此时 1 + 1 == 0.

1.1.2 异或运算满足交换律, 结合律

这个就不用多解释：比如 a, b, c, d, e, 这几个数字做异或运算,
无论是 (a^b)^c^d^e 还是 (a^d)^e^b^c 都是一样的. 最后的结果都是一样的, 可以用加法来理解.

1.1.3 0^n = n, n^n = 0

可以用无进位相加来理解.

0^n = n.
10010011
00000000 ^   因为按照无进位相加来进行实现的话, 这样做就是什么都没改变啊, 任何数字加上0都没有意义.
--------
10010011n^n = 0
10010011
10010011 ^   也按照无进位相加来进行实现, 二进制只有0和1, 两个相同的数字相加, 最后肯定是0.
--------     或者直接按照相同为0, 不同为1, 每一位都是相同的, 所以肯定最后的结果是0.
00000000

1.1.4 整体异或和如果是 x, 整体中某个部分的异或和如果是 y, 那么剩下部分的异或和是 x^y

比如有一个数组 arr[20], 将所有的数字都进行异或运算, 得到最后的结果是：x, 若是其中下标 3, 4, 5, 9, 的数字进行异或运算, 最后的结果是 y, 那这个数组中剩下的数字都进行异或运算的结果是：x^y.

比如：a^b = c, 那 a = b^c, b = a^c.

1.2 黑白球问题

在最上方的图片中已经描述了该问题.

其中有 a个白球, b个黑球, 要是拿出一个黑球和一个白球, 就往袋子里放入一个黑球, 要是拿出两个都是黑球或者白球就往袋子里放入一个白球, 所以对应的, 我们可以将白球视为：0, 黑球视为：1, 所以这两个条件就相当于做异或运算：1 0 , 0 1 相遇, 最后结果是1, 1 1, 0 0 相遇, 最后结果是0.

所以就相当于：每一次都拿出来两个数字 x^y = z, 然后将 z 放回去, 而且这个 z 不是 0 就是 1,

注意：白球是 0000, 黑球是 0001, 不是说每一个白球占据一个 0位置, 每一个黑球占据一个 1 位置. 所以无论怎样异或, 都是 0000 0001 这两个数字之间进行异或.

最后相当于将 a个 0 和 b个 1 整体都 ^(异或) 起来, 最后的结果和 0(白球)个数 是没有关系的. 因为无论 0000 有几个, 都不影响 0001 的 ^(异或) 结果. 要是有奇数个 0001 那最后的结果肯定是：1, 要是有偶数个 0001, 那最后的结果肯定是：0.

2. 题目一：交换两个数

2.1 代码实例

最主要的代码是这三行：

    假设：a = 甲, b = 乙.a = a ^ b;  此时：a = 甲^乙, b = 乙.b = a ^ b;  此时：a = 甲^乙, b = (甲^乙)^乙,结合交换律：b = 甲^(乙^乙) = 甲^0 = 甲.a = a ^ b;  此时：b = 甲, a = (甲^乙)^甲,结合交换律：a = (甲^甲)^乙 = 乙^0 = 乙.三行代码之后：a = 乙, b = 甲.

注意：用这个方法实现两个数的交换的前提是：必须要满足两个数都有独立的内存区域.

比如：假设有一个数组：arr[2], 假设 arr[0] = 甲. 交换 arr[0] 和 arr[0] 位置的数字(肯定会出现这种情况的, 比如随机快速排序), 那此时 arr[0] = 甲, 第一步就是arr[0] = 甲^甲 = 0, 后面两步就已经没有意义了. 所以这样的写法直到就行, 不推荐.

public static void main(String[] args) {  int a = -2323;  int b = 10;  a = a ^ b;  b = a ^ b;  a = a ^ b;  System.out.println(a);  System.out.println(b);  int[] arr = { 3, 5 };  swap(arr, 0, 1);  System.out.println(arr[0]);  System.out.println(arr[1]);  swap(arr, 0, 0);  System.out.println(arr[0]);  
}  // 当i!=j，没问题，会完成交换功能  
// 当i==j，会出错  
// 所以知道这种写法即可，并不推荐  
public static void swap(int[] arr, int i, int j) {  arr[i] = arr[i] ^ arr[j];  arr[j] = arr[i] ^ arr[j];  arr[i] = arr[i] ^ arr[j];  
}

3. 题目二：不用比较操作返回最大值

比如我们想要找到两个数字中的最大值, 直接就 if(a>b) return a. 就行了, 但是这个题目中给的要求是：不能用比较操作.

3.1 代码实例

3.1.1 没有优化的方法 getMax1

其中需要重要的两个函数：sign函数(作用是提取符号位), flip函数(作用是将1和0相互转换),
若是此时 n 是非负数, 符号位是：0, 利用 sign函数提取符号位 0 之后 再利用 flip函数将 0 变成 1.
若是此时 n 是负数, 符号位是：1, 利用 sign函数提取符号位 1 之后 再利用 flip函数将 1 变成 0.

然后利用 getMax1函数, 设置 c = a - b, 通过 c 的正负来判断 a, b 的大小, 此时的 returnA 和 returnB 都在注释中列举了所有的情况, 最后, 直接将 a * returnA + b * returnB, 毕竟 returnA和returnB 中肯定有一个是 0, 另一个肯定是 1, 所以最后的结果不是 a, 就是b, 肯定能返回对应的最大的值.

这个方法有可能会失效, 因为 c = a - b 有可能会越界. 比如 a 是一个很大的数字, b 是一个非常小的负数.

3.1.2 经过优化后的方法 getMax2

getMax2 方法中, 关于前面几行都在代码的注释中说清楚了, 我直接说明最后的两行代码, returnA 和 returnB 的值：

int returnA = diffAB * sa + sameAB * sc;  
int returnB = flip(returnA);  

此时的 returnA 就能判断什么时候返回 a(说明 a > b), 除了下面两种情况, 剩余的情况都返回 b.

1. a, b 的符号不一样, 并且 a 非负,
2. a, b 的符号一样, 并且 c 非负,

returnB 就是将 returnA 取反, 或者直接用 flip函数.

// 不用任何判断语句和比较操作，返回两个数的最大值  
// 测试链接 : https://www.nowcoder.com/practice/d2707eaf98124f1e8f1d9c18ad487f76public class Code02_GetMaxWithoutJudge {  // 必须保证n一定是0或者1  // 0变1，1变0  public static int flip(int n) {  // 将“n”移动之后的数字^ 1, 这个的意义是将“1, 0相互转换”.return n ^ 1;    // 此时“n不是1 就是 0”, 所以将其和 1 进行异或运算(无进位相加).}                   // 就能实现相互转换.// 非负数返回1  // 负数返回0  public static int sign(int n) { // 这个函数的意义是将符号位移动到“0”位置. return flip(n >>> 31);    // 此时将“n”这个数字无符号右移, 一直移动到“0”位置, 但是不能是(>>)}                            // 因为(>>)会导致左边的“31”位都变成其符号位.// 有溢出风险的实现  public static int getMax1(int a, int b) {  int c = a - b;  // c非负，returnA -> 1  // c非负，returnB -> 0  // c负数，returnA -> 0  // c负数，returnB -> 1  int returnA = sign(c);  // 经过这一步之后, returnA肯定不是“1就是0”  int returnB = flip(returnA);  // 所以对应的：将returnA利用flip函数实现转换.  return a * returnA + b * returnB;  // 最后将对应的数字“* 1 或者 0”, 最后返回的就是比较大的数字.  }// 没有任何问题的实现  public static int getMax2(int a, int b) {  // c可能是溢出的  int c = a - b;  // a的符号  int sa = sign(a);  // b的符号  int sb = sign(b);  // c的符号  int sc = sign(c);  // 判断A和B，符号是不是不一样，如果不一样diffAB=1，如果一样diffAB=0  int diffAB = sa ^ sb;  // 判断A和B，符号是不是一样，如果一样sameAB=1，如果不一样sameAB=0  int sameAB = flip(diffAB);  int returnA = diffAB * sa + sameAB * sc;  int returnB = flip(returnA);  return a * returnA + b * returnB;  }  public static void main(String[] args) {  int a = Integer.MIN_VALUE;  int b = Integer.MAX_VALUE;  // getMax1方法会错误，因为溢出  System.out.println(getMax1(a, b));  // getMax2方法永远正确  System.out.println(getMax2(a, b));  }  }

4. 找到缺失的数字

4.1 题目描述

有一个数组：arr[10], 此时 n = 10, 所以对应的：0 ~ 10 有 11 个数字, 但是 arr 中只能放 10 个数字, 所以不能将 0 ~ 10 所有的数字都放到 arr[] 数组中, 所以肯定会缺少一个数字, 所以需要找到这个缺少的数字.

4.2 逻辑实现

将所有的数字都进行异或运算 (^), 假设最后结果是：x = arr[0] ^ arr[1] ^ ... ^ arr[9], 然后将 0 ~ n 所有的数字都进行异或运算 (^), 假设最后结果是：y = 0 ^ 1 ^ 2 ^ ... n. 最后将 x ^ y 就是那一个缺少了的数字.

4.3 代码实例

public static int missingNumber(int[] nums) {  int eorAll = 0, eorHas = 0;  for (int i = 0; i < nums.length; i++) {  eorAll ^= i;  // 这个是为了方便, 这样就不用两个for循环了, 直接 ^ i, 最后再 ^ num长度就行了.eorHas ^= nums[i];  }  eorAll ^= nums.length;  return eorAll ^ eorHas;  // 最后直接返回就可以.
}

5. 题目四：找唯一的出现奇数次数的数

5.1 题目描述

LeetCode 中将题目进行了阉割, 不用看 LeetCode 中的题目描述了.

就是在数组 arr[] 中, 有一种数字，比如说是：A A A A A, 出现了 5 次, 奇数次, 剩下的数字都是出现偶数次的, 比如：B B B B, C C, D D D D D D, 都是出现了偶数次, 所以我需要返回 A 这个数字, 因为只有 A 这个数字是出现了奇数次.

5.2 逻辑实现

直接使用对这个数组中的所有数字进行异或运算 ^, 得到最后的结果就是 A, 因为除了 A 之外所有的数字都是出现偶数次, 而异或运算 ^ 的一个性质是：两个相同的数字做异或运算的结果是 0, 所以除了 A 之外的所有数字全部异或最后结果一定是 0, 要是 A 出现了 5 次, 最后就是将最后一个 A 剩下, 要是 A 只出现了一次, 那就只剩下 A 了.

5.3 代码实例

public static int singleNumber(int[] nums) {  int eor = 0;  for (int num : nums) {  eor ^= num;  }  return eor;  
}

6. 题目五：找唯二的出现奇数次的数

Brian Kernighan算法：提取出二进制里最右侧的1
代码：n & (-n). 这段代码就是 Brian Kernighan 算法的实现

10001100
01110011 先进行取反.
01110100 然后进行取反.
-------- 
00000100 最后的结果.(注意：这个结果不是说最后就是00000001：1了, 这个是将最右侧的1提取出来, 这是一个状态, 最后的结果是：00000100)

6.1 题目描述

数组中有两种数字出现了奇数次, 其他的数字出现了偶数次, 返回这两种出现了奇数次的数字. (和上面的题目描述是一样的, 只是现在有两个数字了)

6.2 逻辑实现

有一个数组 arr[], 还是先将所有的数字都进行异或运算 ^, 最后的结果 eor1 一定是 A ^ B, 因为数组中只有 A 和 B 这两个数字是奇数次出现的.(而且 A 和 B 肯定不相等).

那此时 A ^ B 之后, 结果肯定是一个二进制的数字, 而且肯定有一个二进制位置上是 1, 不管是哪一个, 可能有多个, 但是此时我们就要最右侧的那一个 1, 举一个例子：假设 A = 3, B = 5, 所以最后的结果是：0000 0110, 此时从右往左数第二个位置上的数字是 1, 这就说明：A 和 B 在二进制最右侧位置上肯定有一个是 1, 有一个不是 1 是 0.

此时我们将数组中的所有数字都分为两份, 假设一个是 arr2[] 二进制最右侧 (从右往左数第二个位置) 的数字是 1 的和另一个 arr3[] 二进制最右侧 (从右往左数第二个位置) 的数字是 0 (不是 1 )的, 要是 A 在 arr2[] 中, 那 B 肯定在 arr3[] 中, 那么我们此时直接继续遍历一遍 arr2或者arr3 就行了. 假设我们遍历的是 arr3, 那么我们肯定能得到 B 这个数字(因为偶数次数的都肯定被消除了). 此时我们就直接将 B ^ (A ^ B) 最后的结果肯定是 A 此时我们的 A 和 B 就都找到了.

注意：为什么一定会在 arr 2 或者 arr 3 中一个数字出现偶数次数, 因为任何一个数字都肯定在最右侧位置有 1 或者没有 1, 题目中也说明了, 除了 A 和 B 两个数字, 剩余的数字全都是出现偶数次, 那肯定会有出现偶数次的数字到 arr2 或者 arr3 中(而且是全部的这个数字, 肯定是偶数个), 但是没关系, 反正最后进行异或运算之后都会消除.

6.3 代码实例

public static int[] singleNumber(int[] nums) {  int eor1 = 0;  for (int num : nums) {  // nums中有2种数a、b出现了奇数次，其他的数都出现了偶数次  eor1 ^= num;  // 此时 eor1 肯定是：a ^ b.}  // eor1 : a ^ b  // Brian Kernighan算法  // 提取出二进制里最右侧的1  int rightOne = eor1 & (-eor1);  int eor2 = 0;  for (int num : nums) {  if ((num & rightOne) == 0) {  // 这里相当于我们只遍历了上面说的arr3[]数组.eor2 ^= num;  }  }  return new int[] { eor2, eor1 ^ eor2 };  
}

7. 题目六：找唯一的出现次数少于 m 的数

7.1 题目描述

数组中只有 1 种数出现次数少于 m 次，其他数都出现了 m 次，返回出现次数小于 m 次的那种数

7.2 逻辑实现

有一个数组：arr[], 这个数组中假设 6 这个数组出现了 m 次, 6 的二进制：0110, 所以对应的：不同位置的数字：

1. 0 位置的数字：出现了 0 次
2. 1 位置的数字：出现了 m 次
3. 2 位置的数字：出现了 m 次
4. 3 位置的数字：出现了 0 次

然后继续后来的数字, 有数字出现了 m 次, 那这样来看, 最后的结果, 无论哪一个位置的数字都是 m 的倍数(每一个位置的数字 % m == 0), 但是此时有一个数字出现了 k (k < m) 次, 这样就导致肯定有几个位置的数字不是 m 的倍数(? (因为有可能不是所有位置上的数字)位置的数字 % m == k).

然后将每一个位置上的数字 % m, 要是最后的结果是：0, 那就说明这个数字在这一位置上是 0, 要是最后的结果是：k, 那就说明这个位置上的数字是 1.

7.3 代码实例

最后 ans 的结果当然不可能直接将其装换, 所以这里需要先将 ans 的所有位置都设置为 0, 然后将所有位置应该修改为 1 的数字分别和 1 进行 |(与运算), 这样就能保证 ans 中原本是 0 的位置不进行修改, ans 应该是 1 的部分全部修改为 1.

ans |= 1 << i.

public static int singleNumber(int[] nums) {  return find(nums, 3);  
}  // 更通用的方法  
// 已知数组中只有1种数出现次数少于m次，其他数都出现了m次  
// 返回出现次数小于m次的那种数  
public static int find(int[] arr, int m) {  // cnts[0] : 0位上有多少个1  // cnts[i] : i位上有多少个1  // cnts[31] : 31位上有多少个1  int[] cnts = new int[32];  for (int num : arr) {  for (int i = 0; i < 32; i++) {  // 将所有数字每一个位置的数字进行统计.cnts[i] += (num >> i) & 1;  }  }  int ans = 0;  for (int i = 0; i < 32; i++) {  if (cnts[i] % m != 0) {  // 再将每一个位置的数字遍历一遍, 看看哪一个数字最后的结果 % m != 0.ans |= 1 << i;        // 判断哪一个位置的数字是：1.}  }  return ans;  
}