不使用第三个变量交换两个变量值的方法

记得面试题中有次遇到一题为,不使用第三个变量,实现两个变量的值交换。回来带着思考搜索了如下几种方法,仅供学习参考。

int a = 1;
int b = 2;

方法一:巧用运算符特性实现

C++代码
  1. inline void swap(int& a, int& b) {     
  2.     a = b + (b = a) * 0;     
  3. }  

对于这段代码片段,如果将其转换为静态单赋值形式,并限制每个语句都是一个二元运算与一个赋值,就变成:
 

C++代码
  1. int a0 = 1;     
  2. int b0 = 2;     
  3. int b1 = a; // (b = a)     
  4. int temp1 = b1 * 0; // (b = a) * 0     
  5. int a1 = b0 + temp1; // b + (b = a) * 0   

这样就比较明显了:a0、b0是交换前的值,a1、b1是交换后的值。

方法二:巧用简单的算术运算实现

C++代码
  1. inline void swap(int *a, int *b) {   
  2.     *a = *b – *a;   
  3.     *b = *b – *a;   
  4.     *a = *b + *a;   
  5. }  

这种方法看似比较简洁,但考虑极端的情况,是否有溢出的可能?值得谨慎。

方法三:巧用异或位计算实现

C++代码
  1. inline void swap(int *a, int *b) {   
  2.     *a ^= *b;   
  3.     *b ^= *a;   
  4.     *a ^= *b;   
  5. }  

或简写为:

C++代码
  1. inline void swap(int *a, int *b) {   
  2.     *a = (*b  ^= *a  ^= *b) ^ *a;   
  3. }  

方法四:使用变量地址的指针计算实现

C++代码
  1. inline void swap(int *a, int *b) {   
  2.     if(a<b){   
  3.         a=(int*)(b-a);   
  4.         b=(int*)(b-(int(a)&0x0000ffff));   
  5.         a=(int*)(b+(int(a)&0x0000ffff));   
  6.     }   
  7.     else{   
  8.         b=(int*)(a-b);   
  9.         a=(int*)(a-(int(b)&0x0000ffff));   
  10.         b=(int*)(a+(int(b)&0x0000ffff));   
  11.     }   
  12. }  

这里采用位运算中的与运算“int(a)&0x0000ffff”,因为地址中高16位为段地址,后16位为位移地址,将它和0x0000ffff进行与运算后,段地址被屏蔽,只保留位移地址。这样就原始算法吻合,从而得到正确的结果。
 

此算法同样没有使用第三变量就完成了值的交换,与算术算法比较它显得不好理解,但是它有它的优点即在交换很大的数据类型时,它的执行速度比算术算法快。因为它交换的时地址,而变量值在内存中是没有移动过的。

其实以上的方法虽然没有显式的使用第三个变量,但编译器在编译处理过程中却会做更多的动作,相比于常规化的方式,实际上代价稍微更高,在实际的开发中并不提倡。有兴趣可转至参考链接,更深入地了解相关的对比分析。

参考:

http://www.iteye.com/problems/11221
http://rednaxelafx.iteye.com/blog/134002(分析很详细)
http://hi.baidu.com/%CE%E7%EC%E1%CF%C4/blog/item/a53d1b1e66be3306314e15e2.html
http://blog.csdn.net/Solstice/article/details/5166912

点赞 (0)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据