文章目录
异或的性质
异或是一种<mark>基于二进制的位运算</mark>，用<mark>符号XOR或者 ^</mark> 表示
其运算法则是对运算符两侧数的每一个二进制位，<mark>同值取0，异值取1</mark>。
它与布尔运算的区别在于，当运算符两侧均为1时，布尔运算的结果为1，异或运算的结果为0。
<mark>简单理解就是不进位加法，如1+1=0，,0+0=0,1+0=1。</mark>
性质
- <mark>交换律</mark> 可任意交换运算因子的位置，结果不变
- 结合律（即(a^ b )^c ==a ^ (b ^ c)）
- 对于任何数x，都有<mark>x^x=0</mark>，<mark>x ^ 0=x</mark>，同自己求异或为0，同0求异或为自己
- <mark>自反性 A ^ B ^ B = A ^ 0 = A ，连续和同一个因子做异或运算，最终结果为自己</mark>（ 最重要的性质）
- <mark>（保留信息） A^B 之后，只要有 A 或者 B 都肯定能算出另外一个数。</mark>
例一：不引入第三个变量，交换两个变量(整数)的值
// 假设存在 a b 两个整数
a = a^b
b = a^b
a = a^b
是不是很神奇，如果不理解，请仔细推算，推算完后脑洞会开一点吧。
例二：判断奇偶数更简单高效的做法
奇数二进制的最低位一定是1，偶数二进制的最低位一定是0，所以 a^1==1?偶数:奇数 ，代码就不写了吧。。。脑洞再开
和0做与运算也是可以的a&0==0?偶数:奇数
Java测试：
int a,b ,c ;
System.out.println(a = 0b1111); // 15
System.out.println(b = a^0b1); // 14 1110
System.out.println(c = a^1); // 14 1110
int d ;
System.out.println(d=15^1);
System.out.println(d&1);
System.out.println("----判断偶数---");
for(int i=0 ; i<10 ; i++) {
if(((i^0)&1) == 0 ) {
System.out.println(i);
}
}
例三：找出那个唯一成对的数
1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现 一次。
每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空 间，能否设计一个算法实现？
-
解法一：显然已经有人提出了一个比较精彩的解法，将所有数加起来，减去（1+2+…+1000）的和。 这个算法已经足够完美了，相信出题者的标准答案也就是这个算法，唯一的问题是，如果数列过大，则可能会导致溢出。
-
解法二：异或就没有这个问题，并且性能更好。
将所有的数全部异或(1 ^ 2 ^ … ^ 1000 ^ k,k为重复数)，得到的结果与(1 ^ 2 ^ 3 ^ … ^ 1000)的结果进行异或，得到的结果就是重复数。 即(1 ^ 2 ^ … ^ 1000 ^ k ) ^ (1 ^ 2 ^ 3 ^ … ^ 1000)，由于有结合律、交换律存在，我们可以这么调整为(1 ^ 1 ^ 2 ^ 2 ^ … . ^ 1000 ^ 1000 ^ k)那结果当然就是k了，哈哈哈
Java测试：
int n = 1001 ;
//1000个数中，随机插入一个重复的。
int ran = new Random().nextInt(n);
ArrayList<Integer> list = new ArrayList<Integer>(n);
for(int i=1 ; i<n ; i++) {
list.add(i);
if(i==ran){
list.add(ran);
}
}
//取得那个数
int num = 0 ;
for(int i=0 ; i<list.size() ; i++) {
num = num^list.get(i)^i;
}
System.out.println("猜测："+num);
System.out.println("答案："+ran);
例四：上例变形，找出出现奇数次的数
google面试题的变形：
- 一个数组存放若干整数，其中一个数出现奇数次，其余数均出现偶数次。
找出这个出现奇数次的数?
结果=a[0] ^ a[1] ^ . . . ^ a[n-1]
因为奇数个数字连续异或之后是自己，偶数个数连续异或后为0，自己和0异或还是自己。。。真的很神奇
例六：突然变难，找出数组中落单的两个数
题目：
- 一个整型数组里除了两个数字之外，其他的数字都出现了两次。
<mark>请写程序找出这两个只出现一次的数字。</mark>
<mark>要求时间复杂度是O(n)，</mark>
<mark>空间复杂度是O(1)。</mark>
java测试：
//有两个落单的数，用异或找出来
//3和7落单
Integer[] a = new Integer[]{1,9,2,5,3,4,8,5,2,6,6,7,4,8,9,1};
Integer value = new Integer(0);
for (Integer i : a) {
}
这里加了代码实现，
原文章《异或的用途》：
https://blog.csdn.net/qq_39705793/article/details/81237005?from=singlemessage
京公网安备 11010502036488号