锐客网

  1. 首页 > 睿知 > >

异或运算 是什么运算

睿知生活知识

XOR运算可以理解为无进位运算 。同为0，差为1 。
a: 1 0 1 1 0b: 0 0 1 1 1-------------- 1 0 0 0 1
数学上的异或满足定律
1)0^N = N N^N = 0
2)满足交换律和结合律 。
【异或运算 是什么运算】a^b = b^a (a^b)^c = a^(b^c)
用XOR交换两个变量的值 。//使用异或交换两个变量的值public static void swap(){ int a = 8; int b = 10; System.out.println("a=" a " " "b=" b); a = a ^ b; b = a ^ b; a = a ^ b; System.out.println("a=" a " " "b=" b);}//resulta=8 b=10a=10 b=8解释：int a = 甲;int b = 乙;a = a ^ b; //a=甲^乙 b=乙b = a ^ b; //a=甲^乙 b=甲^乙^乙=甲^0=甲a = a ^ b; //a=甲^乙^甲=甲^甲^乙=0^乙=乙 b = 甲
注意:用异或来交换两个变量的值的前提是变量A和变量B分别是不同的内存 。当A和B是同一个内存时，A B的值存储在这个内存中，内存值永远是0 。
独家或相关练习在整数数组中，要求时间复杂度o (n)和复杂度O(1)在空之间)
1)已知数组中只有一种数出现奇数次，其他数都出现偶数次 。找出奇数次出现的数字 。
public static void printOddTimesNum1(int[] arr){ int eor = 0; for (int cur : arr) { eor ^= cur; } System.out.println(eor); }
2)已知数组中有两种数是奇数次出现，其他数都是偶数次出现 。找出奇数次出现的数字 。
首先，定义一个变量对数组中的所有数字进行异或运算 。这时变量eor的值就是A B的值，因为是两种数，所以A！=b，所以eor！=0，所以一定有一个在eor的二进制位是1 。假设eor的第八位为1，那么A的第八位与B的第八位不同，那么A和B的值中的一个可以通过将该数与第八位为0的数进行异或运算得到，然后将得到的值与eor进行异或运算得到另一个值 。
将第八位为0的数进行异或运算，可以找到A和B的值之一:首先将数组分为两类，一类第八位为1，另一类第八位为0，所以A和B属于不同的类别 。
对第一类中的值进行异或运算得到A的值:为什么，其他数的异或不会有什么作用吗？
不，首先，其他数字甚至出现过几次 。XOR运算可以看作是一种没有进位的加法运算 。在二进制运算中，可以看出每个位的运算并不影响其他位的值 。由于A和B的第八位最后的异或结果是1，那么其他第八位的异或结果一定是0 。把这些数字分成两类 。那么其他第八位为1的数字最后一定是0甚至几次，也就是出现过甚至几次 。否则其他第八位为0的数不一样或者第八位为1的数(A除外)是奇数次，或者最后是1，然后和A异或是0，0 0是0，都是无效的 。所以第八位为1的其他数只能出现偶数次，其他数经过异或运算后为0，A的值会在第一类上进行异或运算得到 。
public static void printOddTimesNum2(int[] arr){ int eor = 0,onlyOne = 0; for (int curNum : arr) { eor ^= curNum; } //eor = a ^ b //eor != 0 //eor必然有一个位置上是1 int rightOne = eor

    推荐阅读


    上一篇：秋葵炒蒜蓉怎么做

    下一篇：臭氧的危害 如何躲避臭氧污染