为什么三次异或操作可以交换两个数

野性酷女 2023-10-05 19:25 25阅读 0赞

##  ##

a和b是两个整数，经过以下三次异或操作，可以达到交换目的：  
a = a ^ b;  
b = a ^ b;  
a = a ^ b;

**首先要理解，什么是^(异或)操作：**  
　　二进制两数运算结果：  
　　0 ^ 0 = 0  
　　0 ^ 1 = 1  
　　1 ^ 0 = 1  
　　1 ^ 1 = 0  
相同为0，不同为1

假设:  
a = 10 , 其二进制数为: 1010  
b = 12 , 其二进制数为: 1100  
如果a和b交换，在二进制数看来，因为第一位和最后一位数相同，所以中间两位数只要交换一下就行了  
这个交换的过程，因为二制进中只有两个数值(0和1)，所以实际上只是0变1，1变0  
所以总结出来就是，交换两个数，就是它们的二进制数不一样的位数，只要各自取反(0变1，1变0)就行了  
如果两个数转换为二进制数的位数不一样，只要短的那个前面补0即可。

**第一次　　a = a ^ b**   
其结果a的值为: 0110，去掉前面的0，即110，仔细观察，此时的a其实是一个差异值(位数上的值是1的表示有差异)，它找到了原来a和b的二进制数不相同的位数，1表示不相同，0表示相同  
110表示，原来a和b在二进制里中间两位数是不一样的，这样就找到了在二进制中哪些位数是a和b不相同的。

**第二次　　b = a ^ b**   
此时a是一个差异值,b还是原来的数,它是如何变成a的原值呢  
异或运算可以从另一个角度去理解:  
当左边的数为0时，其结果就和右边的数一样  
当左边的数为1时，其结果就和右边的数取反  
所以此时的a ^ b就是:  
左边的a,如果位数为0，表示原值a和b的这个位数是一样的,那么b的这个位数就不需要改  
左边的a,如果位数为1，表示原值a和b的这个位数是不一样的,那么b的这个位数就需要取反  
所以b原来的值1100,前后两位数不变，中间两位数取反，其结果就是1010，这就符合上面交换两个数的结论。

**第三次　　a = a ^ b**

此时a还是差异值110，b已经变成原来a的值了，那么a ^ b还是像上面那样，对于b（现在已经是原来a的值），相同的位数不变，不同的位数取反，其结果就是原来b的值。

**简单结论：**

异或操作找出二进制数不相同的位数，然后各自取反