异或运算的基本介绍以及使用技巧，剖析常见的异或题目

2024-06-06 10:08| 来源: 网络整理| 查看: 265

关于异或运算一、异或运算的基本介绍二、异或运算的性质三、异或运算的经典题目1.题目12.题目23.题目34.题目45.题目5 四、异或运算小结

一、异或运算的基本介绍

异或运算，符号为‘^’，直接对底层二进制串进行运算，比算术运算快得多，规则为：相同为0，不同为1。在这里插入图片描述

二、异或运算的性质

假设N为任意实数性质1：0 ^ N = N 性质2：N ^ N = 0 性质3：异或运算满足交换律与结合律重点：我们可以将异或运算理解为二进制的无进位相加！也就是说，当两个数异或的时候，如果某一位同为1，则该位为0并且不向前进位。

三、异或运算的经典题目 1.题目1

题名：如何不使用额外的变量交换两个数字需求：给定一个int类型的a = 1,与一个int类型的b = 2，请交换这两个数思路分析：我们可以利用异或的性质来完成这个题目。

a = a ^ b :此时a = a ^ b, b = bb = a ^ b :此时a = a ^ b, b = a ^ b ^ b = aa = a ^ b :此时a = a ^ b ^ a = b, b = a 最后两个数就交换过来了注意：如果变量a与变量b是指向的同一块内存空间，那么就不能使用这种方法交换，因为同一个内存空间的话，一次异或就相当于这块空间自己与自己异或，结果为0，此时0结果无法改变了。代码： public class no_02_题目1如何不用额外变量交换两个数 { public static void main(String[] args) { //测试一把 int a = 1; int b = 2; System.out.println("交换前："); System.out.println("a = " + a);//1 System.out.println("b = " + b);//2 //异或交换 a = a ^ b; b = a ^ b; a = a ^ b; System.out.println("交换后："); System.out.println("a = " + a);//2 System.out.println("b = " + b);//1 //测试对同一块空间异或会发生什么 int[] arr = {1,2}; //异或前 System.out.println(arr[0]);//1 arr[0] = arr[0] ^ arr[0]; arr[0] = arr[0] ^ arr[0]; arr[0] = arr[0] ^ arr[0]; //异或后 System.out.println(arr[0]);//0 } }

运行结果：在这里插入图片描述

2.题目2

题目：一个数组中有一种数出现了奇数次，其他的数都出现了偶数次，怎么找到并打印这个出现了奇数次的数？思路分析： 1）准备一个变量 eor = 0 2）让这个变量eor 和数组arr中所有的数字都进行异或运算 3）最终得到的eor就是我们要找的出现了奇数次的数

解释：利用异或性质，因为出现了偶数次的数异或为0，出现了奇数次的数异或为该奇数本身，让0与所有数异或最后0就会变为那个奇数代码： public class no_02_题目2 { public static void main(String[] args) { //测试一把 int[] arr = {1,1,1,2,2,2,2,3,3,3,3,4,4};//1出现了3次 int eor = 0; //使用了加强for循环 for (int i:arr) eor ^= i;//eor与arr中所有数进行异或 System.out.println("出现了奇数次的数为：" + eor);//1 } }

运行结果：在这里插入图片描述

3.题目3

题目3讲解的内容与异或无关，但是也很重要，是一种经常使用的操作。题目：提取一个数的二进制串最右侧的1 思路分析：一步到位：int righrOne = num & (~num + 1)

解释：比如num = 1000111010 1000 1.先取反 num = 0111000101 0111 2.加1 num = 0111000101 1000 3.和原来的num按位与&(只有都是1才是1，其余为0) 1000111010 1000 0111000101 1000 结果是：0000000000 1000 这样就得到了最右边的1 代码： public class no_03_题目3提取最右侧的1 { public static void main(String[] args) { //测试一把 int num = 100;//二进制：101 0100 int rightOne = num & (~num + 1); System.out.println(num + "二进制最右侧的1转化为10进制是：" + rightOne);//4 :二进制000 0100 } }

运行结果：在这里插入图片描述

4.题目4

题目：一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种出现了奇数次的数？假设a与b是要找的这两个数。思路分析：

1）首先让变量eor与数组所有数异或一次，eor就变为了a异或b eor = a ^ b 注意：（a != b），所以eor的二进制位一定有一位是12）提取出eor二进制最右侧的1 rightOne = eor & (~eor + 1)3）准备新的变量onlyOne,让数组中所有在rightOne位上是1的数与onlyOne异或。只要和rightOne进行按位与，结果不是0，则该数在rightOne位上是1 int onlyOne = 0; for(int i = 0;i < arr.length;i++) if(rightOne & arr[i] != 0) onlyOne ^= arr[i];

4)此时得到的onlyOne就是a或者b的其中一个

解释：因为a与b在rightOne这个二进制为上一定是一个0，一个1，所以我们可以将数组arr中的数分为两部分，一部分是rightnOne位上是1的数，一部分是0的数，这样就将a与b区分开，单独让onlyOne与异或上其中一部分的数，就可以得到这个出现了奇数次的数，原理与题目2一模一样。

5）再让onlyOne与eor异或得到另一个数图解：在这里插入图片描述代码：

public class no_04_题目4 { public static void main(String[] args) { //注意：因为通过eor最右侧的1为特征，a和b在此位上必不相同，故可以用这位来划分区间 int eor = 0; int[] arr = {1,1,1,2,2,2,4,4,5,5,5,5,6,6,8,8,}; //1.数组所有数与其异或一次 for (int i:arr) eor ^= i;//eor = a ^ b; //2.提取eor最右侧的1【也就是a与b的划分位】 int rightOne = eor & (~eor + 1); //3.准备变量onlyOne与数组中在rightOne位上是1的异或，得到a与b其中一个 int onlyOne = 0; for (int i:arr) if ((rightOne & i) != 0) onlyOne ^= i; //4.onlyOne 就是其中一个，onlyOne ^ eor是另一个 System.out.println(onlyOne + " " + (onlyOne ^ eor)); } }

运行结果：在这里插入图片描述

5.题目5

题目：给你一个整数，提取其中二进制位上为1的个数思路分析：

1）获取最右位上的1 rightOne = num & (~num + 1)2）抹去最右位的1,同时计数器记数，重复步骤1，直到num = 0 num = num ^ rightOne;//抹去最右位的1 代码： public class no_05_题目5 { public static void main(String[] args) { int count = 0;//记数 int num = 25;//0000 1101 while(num != 0){ int rightOne = num & (~num + 1);//获取最右位的1 count++;//计数器 num = num ^ rightOne;//抹去最右位的1 } System.out.println("25二进制上1的个数为：" + count);//3 } }

运行结果：在这里插入图片描述

四、异或运算小结

1.简便记忆异或：无进位相加 2.异或性质牢记 3.异或的简单操作要会使用 4.异或交换两个数，这两个数不能指向同一块内存空间，否则出错。

【本文地址】

公司简介

联系我们