一、异或运算的基本介绍
异或运算,符号为‘^’,直接对底层二进制串进行运算,比算术运算快得多,规则为:相同为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 = b
- b = a ^ b :此时a = a ^ b, b = a ^ b ^ b = a
- a = 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的二进制位一定有一位是1 - 2)提取出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
}
}
运行结果:
文章来源:https://www.toymoban.com/news/detail-716807.html
四、异或运算小结
1.简便记忆异或:无进位相加
2.异或性质牢记
3.异或的简单操作要会使用
4.异或交换两个数,这两个数不能指向同一块内存空间,否则出错。文章来源地址https://www.toymoban.com/news/detail-716807.html
到了这里,关于异或运算的基本介绍以及使用技巧,剖析常见的异或题目的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!