`
mmdev
  • 浏览: 12845637 次
  • 性别: Icon_minigender_1
  • 来自: 大连
文章分类
社区版块
存档分类
最新评论

由教科书函数swap想到的

阅读更多
经典的Swap
几乎从远古时代至今的每一本程序设计语言的教材上, 都可以看到一个叫swap的函数, 书上这样告诉我们:(以C语言为例)
<!--<br /> <br /> Code highlighting produced by Actipro CodeHighlighter (freeware)<br /> http://www.CodeHighlighter.com/<br /> <br /> -->voidswap(int*a,int*b){
inttemp;
temp
=*a;
*a=*b;
*b=temp;
}

在时下最时尚的C#中,我们可以这样写:
<!--<br /> <br /> Code highlighting produced by Actipro CodeHighlighter (freeware)<br /> http://www.CodeHighlighter.com/<br /> <br /> -->staticvoidSwap<T>(refTa,refTb)
{
Ttemp
=a;
a
=b;
b
=temp;
}

上面的C#代码和前面的C大同小异,无非只是体现了一下C#泛型的优越性. 然而有的语言则要飘逸的多,比如说python,它可以支持以下写法:
<!--<br /> <br /> Code highlighting produced by Actipro CodeHighlighter (freeware)<br /> http://www.CodeHighlighter.com/<br /> <br /> -->a,b=b,a

呃,这只是一个表达式。不需要什么函数,不需要引用,最重要的是不需要麻烦临时变量

使用XOR的Swap
如果赋值运算符两边不支持多个操作数是不是就非要使用临时变量呢?那倒未必,请看下面的C代码:
<!--<br /> <br /> Code highlighting produced by Actipro CodeHighlighter (freeware)<br /> http://www.CodeHighlighter.com/<br /> <br /> -->voidswap2(int*a,int*b){
*a^=*b;
*b^=*a;
*a^=*b;
}

为什么异或有这样的功能呢?其实是由以下两个性质决定的:
1.b ^ a =b ^ a (交换律)
2.a ^ a = 0 (由异或的定义)
为了说明问题,这里我们将上述的函数展开并重新标记变量:
a1 = a ^ b
b1 = b ^ a1 = b ^ (a ^ b) = a ^ (b ^ b) = a
a2 = a1 ^ b1 = a ^ b ^ a = b ^ (a ^ a) = b


我们的swap中都应该选择XOR吗?
No,看上去这种不引入临时变量的写法的确比较屌,使用XOR做置换也的确比赋值要高效,但在背后,XOR也会带来一些隐患。例如:

<!--<br /> <br /> Code highlighting produced by Actipro CodeHighlighter (freeware)<br /> http://www.CodeHighlighter.com/<br /> <br /> -->inti=2;
int*a=&i;
int*b=a;
swap2(a,b);
printf(
"*a=%d,*b=%d",*a,*b);
这段代码中,我们期待的输出应该是:a = 2, b =2,因为两个同样的数经过交换应该还是一样的(=2)。但是根据先前提到的第2条规律,由于这里a,b都指向i的位置,所以这里swap2(a,b)=i^i=0;结果竟然等于“0”!。谁会想到一个小小的swap函数居然会弄丢数据。这对调试程序来说无疑增加了难度。所以代码还是写得越“老实”越好维护,正如大神Kernighan所言:

“Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.”

Freesc
2009年7月29日

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics