`
baobaoupup
  • 浏览: 466797 次
文章分类
社区版块
存档分类
最新评论

不使用第三方变量交换函数的两个参数

 
阅读更多

在学习程序语言和进行程序设计的时候,交换两个变量的值是经常要使用的。通常我们的做法是(尤其是在学习阶段):定义一个新的变量,借助它完成交换。代码如下:
int a,b;
a=10; b=15;
int t;
t=a; a=b; b=t;
这种算法易于理解,特别适合帮助初学者了解计算机程序的特点,是赋值语句的经典应用。在实际软件开发当中,此算法简单明了,不会产生歧义,便于程序员之间的交流,一般情况下碰到交换变量值的问题,都应采用此算法(以下称为标准算法)。

上面的算法最大的缺点就是需要借助一个临时变量。那么不借助临时变量可以实现交换吗?答案是肯定的!这里我们可以用三种算法来实现:1)算术运算;2)指针地址操作;3)位运算。

1) 算术运算
简单来说,就是通过普通的+和-运算来实现。代码如下:
int a,b;
a=10;b=12;
a=b-a; //a=2;b=12
b=b-a; //a=2;b=10
a=b+a; //a=10;b=10
通过以上运算,a和b中的值就进行了交换。表面上看起来很简单,但是不容易想到,尤其是在习惯标准算法之后。
它的原理是:把a、b看做数轴上的点,围绕两点间的距离来进行计算。
具体过程:第一句“a=b-a”求出ab两点的距离,并且将其保存在a中;第二句“b=b-a”求出a到原点的距离(b到原点的距离与ab两点距离之差),并且将其保存在b中;第三句“a=b+a”求出b到原点的距离(a到原点距离与ab两点距离之和),并且将其保存在a中。完成交换。
此算法与标准算法相比,多了三个计算的过程,但是没有借助临时变量。(以下称为算术算法)

2) 指针地址操作
因为对地址的操作实际上进行的是整数运算,比如:两个地址相减得到一个整数,表示两个变量在内存中的储存位置隔了多少个字节;地址和一个整数相加即“a+10”表示以a为基地址的在a后10个a类数据单元的地址。所以理论上可以通过和算术算法类似的运算来完成地址的交换,从而达到交换变量的目的。即:
int *a,*b; //假设
*a=new int(10);
*b=new int(20); //&a=0x00001000h,&b=0x00001200h
a=(int*)(b-a); //&a=0x00000200h,&b=0x00001200h
b=(int*)(b-a); //&a=0x00000200h,&b=0x00001000h
a=(int*)(b+int(a)); //&a=0x00001200h,&b=0x00001000h
通过以上运算a、b的地址真的已经完成了交换,且a指向了原先b指向的值,b指向原先a指向的值了吗?上面的代码可以通过编译,但是执行结果却令人匪夷所思!原因何在?
首先必须了解,操作系统把内存分为几个区域:系统代码/数据区、应用程序代码/数据区、堆栈区、全局数据区等等。在编译源程序时,常量、全局变量等都放入全局数据区,局部变量、动态变量则放入堆栈区。这样当算法执行到“a=(int*)(b-a)”时,a的值并不是0x00000200h,而是要加上变量a所在内存区的基地址,实际的结果是:0x008f0200h,其中0x008f即为基地址,0200即为a在该内存区的位移。它是由编译器自动添加的。因此导致以后的地址计算均不正确,使得a,b指向所在区的其他内存单元。再次,地址运算不能出现负数,即当a的地址大于b的地址时,b-a<0,系统自动采用补码的形式表示负的位移,由此会产生错误,导致与前面同样的结果。
有办法解决吗?当然!以下是改进的算法:
if(a<b)
{
a=(int*)(b-a);
b=(int*)(b-(int(a)&0x0000ffff));
a=(int*)(b+(int(a)&0x0000ffff));
}
else
{
b=(int*)(a-b);
a=(int*)(a-(int(b)&0x0000ffff));
b=(int*)(a+(int(b)&0x0000ffff));
}
算法做的最大改进就是采用位运算中的与运算“int(a)&0x0000ffff”,因为地址中高16位为段地址,后16位为位移地址,将它和0x0000ffff进行与运算后,段地址被屏蔽,只保留位移地址。这样就原始算法吻合,从而得到正确的结果。
此算法同样没有使用第三变量就完成了值的交换,与算术算法比较它显得不好理解,但是它有它的优点即在交换很大的数据类型时,它的执行速度比算术算法快。因为它交换的时地址,而变量值在内存中是没有移动过的。(以下称为地址算法)

3) 位运算
通过异或运算也能实现变量的交换,这也许是最为神奇的,请看以下代码:
int a=10,b=12; //a=1010^b=1100;
a=a^b; //a=0110^b=1100;
b=a^b; //a=0110^b=1010;
a=a^b; //a=1100=12;b=1010;
此算法能够实现是由异或运算的特点决定的,通过异或运算能够使数据中的某些位翻转,其他位不变。这就意味着任意一个数与任意一个给定的值连续异或两次,值不变。
即:a^b^b=a。将a=a^b代入b=a^b则得b=a^b^b=a;同理可以得到a=b^a^a=b;轻松完成交换。

以上三个算法均实现了不借助其他变量来完成两个变量值的交换,相比较而言算术算法和位算法计算量相当,地址算法中计算较复杂,却可以很轻松的实现大类型(比如自定义的类或结构)的交换,而前两种只能进行整形数据的交换(理论上重载“^”运算符,也可以实现任意结构的交换)。

介绍这三种算法并不是要应用到实践当中,而是为了探讨技术,展示程序设计的魅力。从中可以看出,数学中的小技巧对程序设计而言具有相当的影响力,运用得当会有意想不到的神奇效果。而从实际的软件开发看,标准算法无疑是最好的,能够解决任意类型的交换问题。

分享到:
评论

相关推荐

    不用第三方变量交换两数的值

    不用第三方变量交换两数的值 不用第三方变量交换两数的值 不用第三方变量交换两数的值

    两个数字的交换,三种方法

    方法一:使用第三方变量交换数据; 方法二:使用加减法,并且不使用第三方变量 思路:a加上b的和,减去a,就等于b,再用这个数减去b,就等于a。 方法三:使用异或方法交换,并且不使用第三方变量 ...

    你必须知道的495个C语言问题

    3.18 需要根据条件把一个复杂的表达式赋给两个变量中的一个。可以用下面这样的代码吗?((condition)?a:b)=complicated_expression; 3.19 我有些代码包含这样的表达式。a?b=c:d有些编译器可以接受,有些却不能。为...

    《你必须知道的495个C语言问题》

    3.18 需要根据条件把一个复杂的表达式赋给两个变量中的一个。可以用下面这样的代码吗?((condition) ? a : b)= complicated_expression; 41  3.19 我有些代码包含这样的表达式。a ? b=c : d 有些编译器可以接受...

    C语言经典例题100道

    两个字符串连接程序 87.结构体变量传递 88.读取数字的整数值并打印出该值个数的* 89.数据加密 90.专升本一题 91.时间函数举例1 92.时间函数举例2 93.时间函数举例3 94.一个猜数游戏 95.家庭财务管理小程序 96.计算...

    组态软件开发平台SuperCxHMI.zip

    VBScript具备丰富的函数库,可以轻松与第三方基于COM模型的软件系统交换,如使用ADO访问数据库,调用Excel等。 强大的编辑器 支持事件响应函数框架自动生成。 结合上下文列出方法和属性表帮助...

    c语言经典案例

    实例098 不使用strcpy()函数实现 字符串复制功能 127 实例099 逆序存放数据 129 实例100 相邻元素之和 130 实例101 选票统计 131 实例102 使用数组统计学生成绩 132 实例103 查找数组中的最值 134 实例104 判断一个...

    C++MFC教程

    +-- 第三章 文档视结构 |------ 3.1 文档 视图 框架窗口间的关系和消息传送规律 |------ 3.2 接收用户输入 |------ 3.3 使用菜单 |------ 3.4 文档,视,框架之间相互作用 |------ 3.5 利用序列化进行文件读写 |----...

    《C#经典编程220例》.(明日科技).【带书签】-共3部分

    实例007 为项目添加第三方控件 9 实例008 为项目添加已有窗体 11 第2章 c#语言基础 12 实例009 利用for循环输出多行语句 13 实例010 输入并输出姓名 14 实例011 使用值类型和引用类型输出不同的字段 15 实例012 判断...

    PHP3程序设计

    16.1.4 在数据交换方面不实用 251 16.2 XML解决方法 251 16.2.1 HTML和XML的差异 251 16.2.2 XML分析器的作用 252 16.3 XML核心 252 16.3.l 标识和文本 252 16.3.2 注解 256 16.3.3 总体文档结构 256 16.3.4 有效及...

    C#微软培训资料

    第三章 编写第一个应用程序 .20 3.1 Welcome 程序 .20 3.2 代 码 分 析 .20 3.3 运 行 程 序 .23 .4 添 加 注 释 .25 3.5 小 结 .27 第二部分 C#程序设计基础.28 第四章 数 据 类 型 .28 4.1 值 类 型...

    《数学分析习题课讲义(下册)》作者: 谢惠民 出版年: 2004年

    作者: 谢惠民 出版社: 高等教育 出版年: 2004-1 页数: 408 ...第二十三章 含参变量积分 第二十四章 曲线积分 第二十五章 曲面积分 第二十六章 场论初步 参考提示 参考文献 中文名词索引 外文名词索引

    windows驱动开发技术详解-part2

    共分为两个部分,这是第一部分。 本书由浅入深、循序渐进地介绍了Windows驱动程序的开发方法与调试技巧。本书共分23章,内容涵盖了 Windows操作系统的基本原理、NT驱动程序与WDM驱动程序的构造、驱动程序中的同步...

Global site tag (gtag.js) - Google Analytics