牛骨文教育服务平台(让学习变的简单)

文章:不借助if、switch等语句求两个数较大的一个

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