Chinaunix首页 | 论坛 | 博客
  • 博客访问: 558601
  • 博文数量: 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.     }
阅读(29393) | 评论(22) | 转发(9) |
给主人留下些什么吧!~~

liubird2012-09-04 22:30:27

x5miao: void main()
{
   int a[2] = {1, 2};
   exchange(a[0], a[1]); //交换a[0]和a[1]的值
   printf("1---a[0]=%d a[1]=%d\n", a[0], a[1]);
   excha.....
多谢指出错误。写void main是受谭浩强的那本《C语言程序设计》所影响的,另外现在基本上不怎么写C/C++程序, 只是偶尔写写算法才用这个,所以写的时候也没有太在意这个。

amarant2012-01-01 11:08:24

liubird: 请问什么地方错了?.....
你这里交换后出现错误答案,是因为交换两个数的存储地址是同一个地址。而不是因为两个数相等。之前没仔细看你的帖子,以为你认为只要a和b相等函数就会错误

x5miao2012-01-01 03:03:21

pmerofc: exchange(a[0], a[0]);
“实参却变成了int指针”
不理解
能否详细解释一下.....
“通常我们在对数组进行操作的时候,会交换数组中的两个元素,如exchang(&a, &b[j])...”

这里,明显应该是exchange(a[ i ],b[j])而不应该是exchang(&a, &b[j]) ,声明的时候写int &a和调用的时候&a的含义可完全不一样!

x5miao2012-01-01 02:58:20

void main()
{
   int a[2] = {1, 2};
   exchange(a[0], a[1]); //交换a[0]和a[1]的值
   printf("1---a[0]=%d a[1]=%d\n", a[0], a[1]);
   exchange(a[0], a[0]); //将a[0]与自己进行交换
   printf("2---a[0]=%d a[1]=%d\n", a[0], a[1]);
}

时间长了,我不知道lz是不是修改过原文,貌似和我上次看到的有改动。但即使改了,lz你的程序还是用点小bug的,main()函数的类型不管是在C还是C++都只能是int型的——main的返回值很多时候是我判断一本C/C++的书好坏的直观标准,而且我发现国外的一半都是用int main()的而国内的很多

bingzheaaa2011-12-30 12:26:38

liubird: 另外交换同一个变量在某些情况下是存在的,尤其是当交换数组中的元素,如果边界判断没有处理得很好的情况下, 在i=j时, 仍然交换a 和a[j] 。一旦,遇到这种情.....
嗯,明白。