XOR的一些性质理解和骚操作

1.异或运算

• 异或运算：相同为0，不同为1
• 同或运算：相同以1，不同为0

以上概念能长期记住的概率接近于0。所以，异或运算就记成无进位相加！
实例：

• 6 对应的二进制：0 1 1 0
• 4对应的二进制： 0 1 0 0
• 异或操作的结果：0 0 1 0

2.异或的性质

• 0^N == N
• N^N == 0
• 异或运算满足交换律和结合率

以上的三个性质用无进位相加来理解就非常的容易（第三个按照加法的交换律和结合律来理解）

3.简单应用

• 如何不用额外变量交换两个数

/**
如何不用额外变量交换两个数
* @author TaoistQu
*/
public class XorTest {
public static void main(String[] args) {
int a = 6;
int b = -1000;
//分析将 a = x
b = y
a = a ^ b;
// a ==> x^y
b ==>y
b = a ^ b;
// b ==> x^y^y ==> x^0 == > x
a ==>x^y
a = a ^ b; // x^y^x
==> 0^y == > y
System.out.println(a);
System.out.println(b);
}
}
结果：
-1000
6

• 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找出打印这种数
• 一个数组中两种数出现了奇数次，其他数都出现了偶数次，怎么找出打印这两种数

/**
* 异或操作的应用
*
* @author TaoistQu
*/
public class EvenTimesOddTimes {
// arr中，只有一种数，出现奇数次
public static void printOddTimesNum1(int[] arr) {
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
}
System.out.println(eor);
}
// arr中，有两种数，出现奇数次
public static void printOddTimesNum2(int[] arr) {
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
}
// eor = a ^ b
// eor != 0
// eor必然有一个位置上是1
int rightOne = eor & (~eor + 1); // 提取出最右的1
int onlyOne = 0; // eor'
for (int i = 0 ; i < arr.length;i++) {
if ((arr[i] & rightOne) != 0) {
onlyOne ^= arr[i];
}
}
System.out.println(onlyOne + " " + (eor ^ onlyOne));
}
public static void main(String[] args) {
int a = 5;
int b = 7;
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println(a);
System.out.println(b);
int[] arr1 = { 3, 3, 2, 3, 1, 1, 1, 3, 1, 1, 1 };
printOddTimesNum1(arr1);
int[] arr2 = { 4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2 };
printOddTimesNum2(arr2);
}
}
结果：
7
5
2
3 2

对应代码的github地址

最后

以上就是活力蜜粉为你收集整理的XOR的一些性质理解和骚操作的全部内容，希望文章能够帮你解决XOR的一些性质理解和骚操作所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。