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

是什么运算(异或运算)

XOR运算可以理解为无进位运算。

用XOR交换两个变量的值。

独家或相关练习

相关推荐