加载中…
个人资料
云中卖马
云中卖马
  • 博客等级:
  • 博客积分:0
  • 博客访问:49,454
  • 关注人气:13
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

“异或宏实现数字交换”的隐瞒问题

(2013-11-11 08:47:27)
分类: 数据结构-算法
先给主角亮亮相:#define swap(a,b) {a=a^b;b=a^b;a=a^b},这个宏相信学习过c语言的大伙都认识。该宏算法有优点,也有隐藏的不足。

该宏存在的问题是我在论坛上帮人家跟踪个问题时候发现的。

要说这个算法的优点,就的先说说数字交换的其他几种实现了。
(特别说明,省去不必要的讨论,这里讨论的数字为int)
1) 用临时变量
 int t = a;
 a = b;
 b = t;
该算法为大多数人所用,因为——简单。
就是多用了一个int的内存。

2) 用两数和减去本身等于另外一个数的特点
 a = a + b;
 b = a - b;
 a = a - b;
该算法省去了一个临时变量,空间上比上一个算法有一点改进。
不过,相信大家都看得出,该算法有个致命的问题——溢出,这个问题的存在,所以该算法不被采用

3) 巧妙用两次异或一个数,等于本身的特点(加密算法中也有用这个特点作为加解密的)。
a ^= b;
b ^= a;
a ^= b;
这个也就是开头说的a=a^b;b=a^b;a=a^b了。因为一般人都喜欢把这窜编码定义成宏,所以。便有了该文章的讨论。
该算法相对前面两个的优点,很明显了。它省去了一个中间变量,异或操作在也是很快速的,更不存在算法2 的溢出问题。所以,该算法被公认是一个很完美的问题了。

回到开头的宏定义 #define swap(a,b) {a=a^b;b=a^b;a=a^b},这个宏也就被很多的人所采用。
但是该宏也存在一个问题,而且该问题隐藏的很深。

本文不讨论用 ++ -- 等引起的bug。

该宏的隐藏问题就是,如果使用不当,会将交换的数字清零
看,如果有人这样用呢?
int a = 100;
swap(a,a);

该宏的展开就是
a ^= a;
a ^= a;
a ^= a;

那么,问题显而易见了。 a ^= a; 这样就把a清理了。

或许,有的人会说,既然是两个数字交换,没有人那么脑残到把同一个数字作为交换的。
确实应该没有这样的程序猿。

但是,估计有不少在实现一个的倒叙时候,是(类似)这样写的:
int a[N]; 这里的N为一个大于1数
……
int *begin = &a[0];
int *end = &a[N-1];

while (end >= bengin) {
   swap(*begin,*end);
   begin++;
   end--;
}

写这个算法应该大家没有异议的吧!
细心的估计就看到问题了,但N为一个基数的时候,那么就存在出现begin == end 的情况,这个时候做交换,就清理了。
极端的N去最小值3(>1)。那么第二轮的循环的时候,begin = &a[1];end = &a[1].看到了没?这样在交换中就就把a[1]给清理了。其他的N为奇数时候都会把中间的一个数字清零,这估计不是大家想要的。

当然把上面的循环改成下面的,就能够避免该清零bug的问题了。
while (end > bengin)

但是,人家写的while (end >= bengin)也没有问题,有问题的只是宏内部而已。同时,这个也只是一个例子。而在*p1 和 *p2 交换时候,你有怎么知道p1 和p2 一定不指向同一个变量——不一定是在遍历?

ps:对于算法2,#define swap1(a,b) {(a)=(a)+(b);(b)=(a)-(b);(a)=(a)-(b);}也存在该(清零)问题



0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有