不借助变量交换两个数
最后更新于：2022-04-01 16:17:20
文章：[不借助if、switch等语句求两个数较大的一个](http://blog.csdn.net/u013074465/article/details/42684559)
交换两个数在排序算法中用的很多：[冒泡排序中](http://blog.csdn.net/u013074465/article/details/44339187) 、[插入排序中](http://blog.csdn.net/u013074465/article/details/42043665)等等。正常的交换两个数是借助一个变量tmp：
~~~
void Swap(int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
}
~~~
在面试题中有这样的题目“不借助第三个变量，交换两个数”
~~~
//A方法
void Swap(int &a, int &b) {
a = a + b;
b = a - b;
a = a - b;
}
~~~
~~~
//B方法
void Swap(int &a, int &b) {
a ^= b; b ^= a; a ^= b;
}
~~~
上述的两种方式中，A方法缺点：中当数a或b较大时 a = a + b会发生越界。
方法B的原理：
~~~
a = a ^ b;
b = a ^ b; //那么 b = a ^ b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a，即将a赋值给了b
a = a ^ b; //那么 a = a ^ b = a ^ (a ^ b) = (a ^ a) ^ b = 0 ^ b = b，即实现了将b赋值为a
~~~
以上两种方法的共有bug：
当a、b指向的是同一个数时，即Swap(a, a)时，会发生错误，将a置为了0。但是a等于b的情况下（即a和b不是指向同一个地址时）是不会错误的。
解决方法：
为Swap函数增加判断语句：当a和b相等的时候不交换。
~~~
//A方法
void test(int &a, int &b) {
if (a != b) {
a = a + b;
b = a - b;
a = a - b;
cout << "OK " << endl;
}
}
//B方法
void Swap(int &a, int &b) {
if (a != b) {
a ^= b;
b ^= a;
a ^= b;
}}
~~~