不借助变量交换两个数

叁歲伎倆 2022-08-07 05:54 165阅读 0赞

文章：[不借助if、switch等语句求两个数较大的一个][if_switch]

交换两个数在排序算法中用的很多：[冒泡排序中][Link 1] 、[插入排序中][Link 2]等等。正常的交换两个数是借助一个变量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;

\}\}

[if_switch]: http://blog.csdn.net/u013074465/article/details/42684559
[Link 1]: http://blog.csdn.net/u013074465/article/details/44339187
[Link 2]: http://blog.csdn.net/u013074465/article/details/42043665