“异或宏实现数字交换”问题讨论

“异或宏实现数字交换”问题讨论

【老文章,首发于新浪博客:http://blog.sina.com.cn/s/blog_6f50984a0101br7c.html

先给主角亮相:#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} 被很多的人所采用。
但是该宏也存在一个问题,而且该问题隐藏的很隐蔽,就是如果使用不当,会将交换的数字清零。

看,如果有人这样用呢?

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为奇数时候都会把中间的一个数字清零,这不是算法想要的。
当然把上面的循环改成while (end > bengin),就能够避免该清零bug的问题了。

但是,写的while (end >= bengin)也没有问题,有问题的只是宏内部而已。这个也只是一个简单的例子,工程的环境复杂时候问题可能更加隐瞒。在*p1 和 *p2 交换时候,你就怎么知道p1 和p2 一定不指向同一个变量——不一定是在遍历?

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

(全文完)

(欢迎转载本站文章,但请注明作者和出处 云域 – Yuccn

发表回复

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