1. 异或的理解
我们通常把异或定义为不同为1，相同为0，即如如下真值表所显示：
| a | b | a ^ b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
但从另外一方面想，我们可以将异或运算认为是二进制的无进位相加：
设 a = 10110101
b = 01011101
则 a ^ b = 11101000
相当于每位各自相加但是没有进位。
2. 异或的运算性质
-
0 ^ N = N N ^ N = 0
-
a ^ b = b ^ a (交换律) a ^ b ^ c = a ^ (b ^ c) (结合律)
-
同样的一组数异或得到的数一定相同，因为不论这组数怎样调换顺序、组合，经过2中的交换率和结合律都可以得到相同顺序的一组数。
3. 异或的应用
3.1 用于交换两个数的变量值
int a = 甲; //假设a的值为甲，b的值为乙
int b = 乙;
/*下面的程序用于交换两个数的值*/
a = a ^ b;
b = a ^ b;
a = a ^ b;
就这样，a和b的值就已经进行了交换，是不是有点不可思议！😄
下面我们来具体分析一下三步运算中a和b的值：
-
a = a ^ b;a = 甲 ^ 乙 b = 乙 -
b = a ^ b;a = 甲 ^ 乙 b = 乙 ^ 甲 ^ 乙 = 甲 ^ (乙 ^ 乙) = 甲 -
a = a ^ b;a = 甲 ^ 乙 ^ 甲 = (甲 ^ 甲) ^ 乙 = 乙 b = 甲
是不是清楚了很多呢？有没有觉得这种方法很神奇？😁
但这种方法也有一定的限制😥，使用时一定要注意这两个变量是否指向一个内存地址！！！(应用到数组中就是数组下标是否相同)，如果两个变量指向一个内存地址，那么异或操作会将变量的值置为0。
3.2 用于解决奇次数问题
- 一个数组中，一种数出现了奇数次，其他数出现了偶数次，如何找出这个出现奇数次的数？
分析：经过上面的分析，很容易就想到了用异或的方法，因为只有一个奇数次数，其它都是偶数次数，如果将数组中所有数进行异或操作，那么最后剩下的那个数便是我们所求的奇数次数。
解决：定义一个初值为0的变量，分别与数组中的每个数异或，最后这个变量中保存的值就是所求的奇数次数。
- 一个数组中，两种数出现奇数次，其他数出现偶数次，如何求出这两个出现奇数次的数？
分析：😶这下有两个奇数次数了，该怎么办呢？不慌，让我们看看这组数异或后的结果是什么。
显然，这组数异或最后就剩这两个奇数次数了。设这两个数分别为a和b。则异或的最后结果为a ^ b。因为是两种数，所以a != b，则a ^ b != 0，即a和b至少有一个位上是不同的，a ^ b至少在某一位上为1，由a ^ b的结果可以求得这个位。将该数组分成两种，一种是该位上为1的，另一种是该位上不为1的，则a和b分别位于两种数组中。取一个eor'，令其该位置为1其他位置为0，用eor'异或数组中所有该位上为1的数，则最后结果一定为a或b。再将a或b与之前所求的a ^ b在进行异或操作，就可以求出另外一个数。至此，a和b都已求出。
有没有觉得异或运算很神奇呢？😁
本人系菜鸟一枚，所写文章皆为学习总结，大佬请轻喷:😱
谢谢阅读:😘，欢迎补充！
网友评论