交换变量:笨办法、加减法还是位运算?

  1. 总览
  2. 介绍
    1. 法一:利用中间变量
    2. 法二:加减法
    3. 法三:位运算
  3. 隐藏的劣势与优势
  4. 总结

在看 glibc 的 qsort 源码的时候发现交换变量的方式居然是定义了一个中间变量这种“笨办法”而不是加减法或者位运算!这让我有了疑惑,这三种交换变量的方式有没有高低之分呢?

总览

在编程中常常有交换变量的值的需求,比如说在排序中就常常要交换变量。经过思考人们思考出了三种交换变量的方法:利用一个中间变量;利用算术运算;利用位运算。下面对这三种方法利用C语言进行介绍和优劣势对比

介绍

法一:利用中间变量

代码如下

int a = 1, b = 2, temp=0;
temp = a;
   a = b;
   b = temp;

这个方法是最初学的,清晰明了,所以大家也最爱用这个,可是很快人们发现了这个方法要多用一个变量,可能耗费了更多内存!于是乎人们又提出了接下来的两种不需要辅助变量的方法。

法二:加减法

代码如下

int a = 1, b = 2;
a = a + b;
b = a - b;
a = a - b;

这个方法看似很美好,同样是三步,但现在所需要的变量少了一个,确实更好。但其实这个方法饱受溢出问题的困扰,试想a与b如果相加后导致溢出,那么第一步之后的结果都不一定对了。如下:

char a=127;
int b=1;
a = a + b;
b = a - b;
a = a - b;

如果你用 char 或者 int 类型的中间变量来交换a和b都不会出现错误结果,但加减法就会让a的值会错误的成为-1。

法三:位运算

代码如下

int a = 1, b = 2;
a ^= b;_//a与b异或,得到一个中间值,赋值给a_
b ^= a;_//中间值与b异或,得到的是最开始的a,赋值给b_
a ^= b;_//中间值与b(先前的a)异或,得到最开始的b,赋值给a_

这个方法看上去无敌了,又不用中间变量,又无溢出之问题,简直是最完美的方法,那么学会这个方法之后就一直用这个方法吧。

但是为什么glibc这个大部分人都在用的C语言库的需要交换变量的qsort函数里不用这个方法呢?难道我们比GNU所有开发者30年的经验都聪明?

隐藏的劣势与优势

位运算的方法其实有3个缺点:

1.在可读性方面:对于从未接触过这个方法的人来说,如果你不写注释,可能大家都看不懂你这里是想做什么。(当然对于GNU的人来说这个根本不算问题)

2.在性能方面:在过去可能用位运算比起用中间变量要快得多,但我们已经来到了21世纪。硬件上,如今的处理器在处理传送数据的MOV指令时都有MOV-elimination的特性,也就是说MOV这条指令可以做到0延迟(某种意义上),在各种情况下能做到至少和位运算一样快的交换变量速度。

同时,现代处理器有设计并行处理的流水线,但异或运算的时候运算的顺序是不可改变的,故完全无法利用这个特性可以带来的性能提升。

软件上,现代编译器会检测到你用中间变量做交换来判断你的意图来优化,优化后最糟糕的情况性能也和位运算一样。但是如果你做了位运算,编译器便为了保证安全而完全不敢优化。所以现在位运算看上去变成了性能较差的那个交换变量的办法。

3.最根本的,在行为本身的正确性方面,位运算其实也会出错:假如遇到了交换的内容在内存中储存在同一个地方的情况,比如我们对指针指向的内容进行交换,这时两个指针指向同一个内容是很容易发生的情况。然而用位运算的方法会完全把数据搞丢。想象一个指针a,b都指向同一个位置,之后指针指向的内容*a与*b交换,我们的预期是a,b指向的内容没有变化。但是如果使用异或交换的话,*a^=*a;直接会将*a清零,于是后面的操作变得完全没有意义了。为了解决这个问题,人们还要判断两个指针变量是否相同,于是需加上一句if(a!=b),这时性能会下降的更厉害。但简单的用中间变量只要稍微注意交换次序便怎么滥用都完全没有出错的情况。

总结

用中间变量做交换吧,相信硬件和软件的优化。除了极端的缺乏内存以及你非常清除自己在做什么的情况下,不要使用奇技淫巧比如位运算(更不用提很明显有问题的算术法)来交换变量否则可能性能会损失或者丢失内容。

所以有一句话很对:不要过早的优化程序。我想,优化之前要明白在做什么优化,然后通过测试的方式评估来确认确实是优化了而且没有带来副作用。


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以邮件至 [email protected]

Title:交换变量:笨办法、加减法还是位运算?

Count:1.4k

Author:emon100

Created At:2019-08-01, 20:09:00

Updated At:2020-10-11, 21:48:09

Url:https://blog.emon100.me/2019/08/01/%E4%BA%A4%E6%8D%A2%E5%8F%98%E9%87%8F%EF%BC%9A%E7%AC%A8%E5%8A%9E%E6%B3%95%E3%80%81%E5%8A%A0%E5%87%8F%E6%B3%95%E8%BF%98%E6%98%AF%E4%BD%8D%E8%BF%90%E7%AE%97%EF%BC%9F/

Copyright: 'Attribution-non-commercial-shared in the same way 4.0' Reprint please keep the original link and author.