Chinaunix首页 | 论坛 | 博客
  • 博客访问: 649009
  • 博文数量: 45
  • 博客积分: 931
  • 博客等级: 准尉
  • 技术积分: 590
  • 用 户 组: 普通用户
  • 注册时间: 2005-04-17 13:27
文章分类

全部博文(45)

文章存档

2013年(6)

2012年(15)

2011年(23)

2005年(1)

分类: C/C++

2011-12-05 17:56:06

前面我们谈到了,可用通过异或运算交换两个数,而不需要任何的中间变量。 如下面:

  1. void exchange(int &a, int &b)
  2. {
  3.     a ^= b;
  4.     b ^= a;
  5.     a ^= b;
  6. }

然而,这里面却存在着一个非常隐蔽的陷阱。

通常我们在对数组进行操作的时候,会交换数组中的两个元素,如exchang(&a[i], &b[j]), 这儿如果i==j了(这种情况是很可能发生的),得到的结果就并非我们所期望的。

  1. void main()
  2. {
  3.    int a[2] = {1, 2};
  4.    exchange(a[0], a[1]); //交换a[0]和a[1]的值
  5.    printf("1---a[0]=%d a[1]=%d\n", a[0], a[1]);
  6.    exchange(a[0], a[0]); //将a[0]与自己进行交换
  7.    printf("2---a[0]=%d a[1]=%d\n", a[0], a[1]);
  8. }
 上面那段测试代码的输出是:
  1. 1---a[0]=2 a[1]=1
  2. 2---a[0]=0 a[1]=1
很意外吧,第一次的交换正确的执行了,但是第二次调用exchange的时候却将a[0]置为了0. 仔细分析,不难发现,这正是我们在exchange里面用异或实现交换所造成的。如果输入a和b是同一个数,exchange里面代码相当于:

  1. a ^= a;
  2. a ^= a;
  3. a ^= a;
成了a做了3次于自己的异或,其结果当然是0了。

既然这样,我们就不能够在任何使用交换的地方采用异或了,即使要用,也一定要在交换之前判断两个数是否已经相等了,如下:

  1.     void exchange(int &a, int &b)
  2.     {
  3.         if(a == b) return; //防止&a,&b指向同一个地址;那样结果会错误。
  4.         a ^= b;
  5.         b ^= a;
  6.         a ^= b;
  7.     }
阅读(32053) | 评论(22) | 转发(9) |
给主人留下些什么吧!~~

liubird2011-12-30 10:22:08

bingzheaaa: 我感觉这不是两不同变量的值相同的问题,而是交换双方为同一变量导致自己与自己异或引起的,假如 a[2] = {1, 1};不会出现一方为零的现象。而同一变量一般不需交.....
另外交换同一个变量在某些情况下是存在的,尤其是当交换数组中的元素,如果边界判断没有处理得很好的情况下, 在i=j时, 仍然交换a 和a[j] 。一旦,遇到这种情况,是很难发现的。这也正是我要在文章中表达的意思。

liubird2011-12-30 10:16:03

bingzheaaa: 同一个数这样的说法不准确,应该是同一变量。.....
同意

bingzheaaa2011-12-30 10:01:42

liubird: 是的, 我文章中的意思也是说要防止输入的两个是其实是同一个数。.....
同一个数这样的说法不准确,应该是同一变量。

liubird2011-12-30 09:56:54

x5miao: 难道就没人发现LZ的程序写错了吗。形参是int引用,实参却变成了int指针。而且异或变成0的情况也不是a==b,而是a和b是同一个对象的时候才会发生。所以C里.....
我在文中没有说是a==b是就一定会造成这个问题。 如下面的注释,用a==b判断是为了防止a,b是同一个数, 这样做是没有问题的;如果a、b不是同一个变量,但是它们的值相等, 也没有必要都它们进行交换。

if(a == b) return; //防止a,b是同个数;那样结果会错误。

当然,我们也可以在exchange里面只判断a,b是否是同一个变量。这样,如果a和b虽然不是同一个变量,但是值相等,将进行多余的交换操作。

        void exchange(in

liubird2011-12-30 09:46:17

bingzheaaa: 我感觉这不是两不同变量的值相同的问题,而是交换双方为同一变量导致自己与自己异或引起的,假如 a[2] = {1, 1};不会出现一方为零的现象。而同一变量一般不需交.....
是的, 我文章中的意思也是说要防止输入的两个是其实是同一个数。