大家好,欢迎来到IT知识分享网。
目录
异或运算的含义
异或运算(^)简单来说就是相同为0,不同为1;还有一种理解就是无进位相加,例如对于两个变量a=,b=011101,a^b=,也就是两者相加,不进位。
异或运算的性质
(1)0^N=N,N^N=0;
(2)异或运算满足交换律和结合律,a^b=b^a (a^b)^c=a^(b^c)
异或运算的应用
不用额外变量交换两个整数的值
如果给定两个整数的值,可以使用以下三行代码,不用额外变量交换两个整数的值:
//假设定义a=甲,b=乙 a=a^b;//a=甲^乙,b=乙 b=a^b;//a=甲^乙,b=甲^乙^乙=甲^0=甲 a=a^b;//a=甲^乙^甲=甲^甲^乙=0^乙=乙,b=甲
但是注意的是,使用异或运算交换两个变量值时必须保证两个变量的地址不同。
经典例题
(1)一个数组中有一种数出现了奇数次,其它数都出现了偶数次,怎么找到这一种数?
public static void printOddTimesNum1(int[] arr) { int eO = 0; for (int cur=0;cur<=arr.length-1; cur++) {//从第一个数开始,两个两个依次异或所有数 eO ^= cur; } System.out.println(eO); }
对数组中的所有数两两分别异或就可以解决这个问题,异或运算满足交换律(交换律可以使用无进位相加去理解,一组数字,如果某个数字有偶数个,不管几个,异或出来的结果都是0,和异或的先后没有关系)所有的偶数放到一起先异或,结果均为0,最终剩下的就是奇数。
(2)一个数组中有两种数出现了奇数次,其它数都出现了偶数次,怎么找到这两种数?
public static void printOddTimesNum2(int[] arr) { int eO = 0; for (int i=0;i<arr.length: i++) {//将数组中的每两个数字两两异或 eO ^= arr[i]; }//最终得到的结果eO一定为a^b,其它数都出现偶数次,异或结果为0 int rightOne = eO & (~eO + 1);//提取出最右侧的1,因为得到的e0中的1表示的就是a与b在此处不同,所以为1,提取一个作为区分,赋值给rightOne int onlyOne = 0; for (int i=0;i<arr.length: i++) { if ((a[i] & rightOne) == 1) {//与rightOne比较,和rightOne进行&运算,将数组分成了两组,那一位是1的和那一位是0的,a和b分别位于两组之中,取得是那一位是1的数 onlyOne^= cur;//对那一位是1的那一组进行异或运算,最终得到的结果为a或b,因为那一组中其他的数字都出现了偶数次 } } System.out.println(eOhasOne + " " + (eO ^ onlyOne));//另一个结果,结果也为a或b }
这个问题同样首先先对整个数组中的数进行异或运算,得到的结果是a^b,两者相异,记录两者异或运算的结果,提取两者异或运算结果中最右侧的1,表示a与b在此处不同,可以对两者进行划分。对所有数字重新进行了分组,在其中一组进行异或运算,得到的结果为a或b,然后将a^b异或上它,得到另一个a或b
提取出最右侧的1
在上面这个题目中用到了位运算的一个技巧,怎么把一个整数,提取出最右侧的1,使用的是将这个数与自身取反加1的数做&运算。也就是假设这个数是a,则提取最右侧的1的操作b为
b=a & (~a + 1)
找到出现了K次的数
[题目]在一个数组中有一种数出现K次,其他数都出现了M次,M>1,K<M。找到出现了K次的数。要求时间复杂度,额外空间复杂度。实现的思路如下:
- int类型的数拥有32位,那么创建一个32位的数组
- 数组的每个位置记录的是数组中每个数的指定位上的值的累加
- 然后遍历数组,判断其中的每个数是否为M的倍数,如果是,那么出现K次的数在该位上是0,如果不是并且余数为K,那么说明出现K次的数在该位上是1
- 依次计算每个位上的数,即可得到出现K次的数
public static int findKTimeNum(int[] arr, int m, int k) { int[] help = new int[32]; for (int num : arr) { //将数组中的数转化为二进制数 for (int i = 0; i < 32; i++) { //num右移,看哪个位置有1,help数组在对应位置累加1. help[i] += (num >> i) & 1; } } int target = 0; for (int i = 0; i < help.length; i++) { //不为0,说明出现k次的数在此处有值 if (help[i] % m != 0) { target |= (1 << i);//将出现K次的位置变为1 } } return target; }
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/136229.html