【算法笔记】异或运算的奇妙之处

x33g5p2x  于2022-02-28 转载在 其他  
字(2.1k)|赞(0)|评价(0)|浏览(322)

前言: 本章主要是针对异或运算相关问题总结的几个小题目,掌握了它们,在写一些算法题时或许有意想不到的惊喜!

1. 基础介绍

  • 任何两个相同的数异或结果为0
  • 一个数和0异或结果不变
  • 多个数异或遵循交换律
  • 可以通过 ans |= (1 << i) 将 ans 二进制的 i 位置设置为1

2. 题目

题一:如何不用额外变量交换两个数 a 和 b

方法模板:

  1. a = a ^ b;
  2. b = a ^ b;
  3. a = a ^ b;

示例代码:

  1. int a = 3;
  2. int b = 5;
  3. a = a ^ b;
  4. b = a ^ b;
  5. a = a ^ b;
  6. System.out.println(a + " " + b);
  7. // 结果为:5 3

注意:

交换数组中的两个值也可以使用异或,但是要注意数组的两个下标不能相同,否则交换后的值不正确

题二:一个数组中有一种数出现了奇数次,其它数都出现了偶数次,怎么找到并打印这种数

方法模板: 让所有的数一起异或,出现偶数次的值异或结果为0,出现奇数次的值结果为该值本身,任何一个值和0异或结果不变

  1. public static void printOddTimesNum1(int[] arr) {
  2. int eor = 0;
  3. for (int i = 0; i < arr.length; i++) {
  4. eor ^= arr[i];
  5. }
  6. System.out.println(eor);
  7. }

示例代码:

  1. public static void main(String args[]) {
  2. int[] arr = {1, 1, 2, 3, 3, 4, 4};
  3. printOddTimesNum1(arr);
  4. }
  5. // 结果为:2

题三:怎么把一个 int 类型的数 a,提取出只保留其二进制中最右侧为1位置,其余位值都修改为0时的值(如 1110 -> 0010)

方法模板:

  1. a = a & (~a + 1)
  2. a = a & (-a)

示例代码:

  1. int num = 10; // 10 的二进制为 1010
  2. int num1 = num & (~num + 1);
  3. int num2 = num & (-num);
  4. System.out.println(num1);
  5. System.out.println(num2);
  6. // 结果都为:2 (2 的二进制为 0010)

题四:一个数组中有两种数 a 和 b 出现了奇数次,其它数都出现了偶数次,怎么找到并打印这两种数

方法模板: 将该数组的所有数都进行异或,结果就为 a ^ b,由于 a 和 b 不相等,则异或结果肯定不为0,即结果的二进制的值肯定有一位为1,因此可以该结果二进制的某位置为1的位置作为分界,数组肯定有一些数该位置的值都为1,因此可以找出所有该位置都为1的数,对他们进行异或,假设异或结果为 a,则 a 再与 a ^ b 进行异或就能得到 b

  1. public static void printOddTimesNum2(int[] arr) {
  2. int eor = 0;
  3. for (int i = 0; i < arr.length; i++) {
  4. eor ^= arr[i];
  5. }
  6. int rightOne = eor & (-eor); // 提取出最右的1
  7. int a = 0;
  8. for (int i = 0 ; i < arr.length;i++) {
  9. if ((arr[i] & rightOne) != 0) {
  10. a ^= arr[i];
  11. }
  12. }
  13. int b = eor ^ a;
  14. System.out.println(a + " " + b);
  15. }

示例代码:

  1. public static void main(String args[]) {
  2. int[] arr = {1, 1, 2, 3, 3, 4, 4, 5};
  3. printOddTimesNum2(arr);
  4. }
  5. // 结果为:5 2

题五:一个数组中有一种数出现了 K 次,其它数都出现了 M 次(M > 1,K < M),找到出现了 K 次的数,要求额外空间复杂度为 O(1),时间复杂度为 O(N)

模板方法: 可以申请一个数组长度为32的数组,该数组其实表示一个数组二进制的32位,用来计算原数组中所有数,在二进制的每个位置中1的总数。将申请的数组的每位的值都模上 M,如果结果为0,则表示出现次数为 K 的数的该位的值为0;如果结果不为0,则表示出现次数为 K 的数的该位的值为1。注意当出现次数为 K 的值为0,不满足上述条件,需要特殊处理

  1. public static int onlyKTimes(int[] arr, int K, int M) {
  2. int[] bin = new int[32];
  3. for(int num : arr) {
  4. for(int i = 0; i < 32; i++) {
  5. bin[i] += (num >> i) & 1;
  6. }
  7. }
  8. int ans = 0;
  9. for(int i = 0; i < 32; i++) {
  10. if(bin[i] % M == 0) {
  11. continue;
  12. }
  13. // 模的值必须为 K 才满足条件,如果不满足就返回一个 -1
  14. if(bin[i] % M == K) {
  15. // 将 ans 的 i 位置设置为1
  16. ans |= (1 << i);
  17. }else {
  18. return -1;
  19. }
  20. }
  21. return ans;
  22. }

示例代码:

  1. public static void main(String args[]) {
  2. int[] arr = {1, 1, 1, 9, 9, 3, 3, 3, 4, 4, 4};
  3. System.out.println(onlyKTimes(arr,2,3));
  4. }
  5. // 结果为:9

相关文章