Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1006657
  • 博文数量: 150
  • 博客积分: 3017
  • 博客等级: 少校
  • 技术积分: 3829
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-19 14:40
个人简介

Now in Baidu WISE team

文章分类

全部博文(150)

文章存档

2014年(8)

2013年(31)

2012年(111)

分类: C/C++

2012-12-17 21:20:54

今天在写快排,习惯性的使用异或的宏来交换两个变量,结果在codepad.org上无论如何都跑不过,改了一个小时也没发现哪里出错。
晚上终于看出是swap这个宏的问题。
//#define swap(a,b) {a^=b; b^=a; a^=b;}
这是一个看起来没问题的宏, 但是在类似排序这种事情中,这个宏里面藏着一个陷阱,
假设对于一个数组input[],我们需要交换i,j两个元素,
     swap(input[i],input[j]);
一般情况下是没问题的,但是,当i = j时,就出现问题了,这个语句执行的结果是input[i]=input[j]=0;

分析:
在这种情况下,input[i],input[j]其实指向的是同一个int变量,那么swap(a,b)就变成了swap(a,a)了,整个或陈个就被替换成了:
   {input[i]^=input[i]; input[i]^=input[i]; input[i]^=input[i]; }
显然,执行后最终的值是0

疑问:
利用异或交换两个变量的宏有不同的写法,原理一样,但是实际效果却很意外的不一样。
//#define swap(a,b) {a^=b; b^=a; a^=b;}
//#define swap(a, b) a^=b^=a^=b
以上两种写法表达的意思其实是一样的,但是
1.在codepad.org上,第一种写法无法避免上面提到的陷阱,但是第二种写法在codepad.org上却能正确执行,执行后变量值没有被置0
2.在本机的gcc下,两种写法都存在上述问题。但是两个运行结果不同。并且第二种报一个很难懂的warning

结论:
建议的写法
#define swap(a,b) {if(a!=b){(a)^=(b); (b)^=(a); (a)^=(b);}}

参考程序见:
阅读(1095) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~