小菜毛毛技术分享
与大家共同成长
BlogJava
::
首页
::
联系
::
聚合
::
管理
164 Posts :: 141 Stories :: 94 Comments :: 0 Trackbacks
常用链接
我的随笔
我的评论
我的参与
最新评论
留言簿
(15)
给我留言
查看公开留言
查看私人留言
我参与的团队
随笔分类
andriod(23)
appfuse 集成J2EE框架(2)
eclipse 插件相关(3)
English(5)
FckEditor(2)
FLEX(9)
google app engine(2)
googleAnalytics(1)
htmlunit(1)
httpclient(1)
IDE(8)
java基础运用(11)
java定时器(5)
jQuery(1)
JSON-LIB快速入门(1)
JSTL(3)
LOG4J(1)
maven(1)
mysql(1)
servlet(3)
SMC(stateMachine)(1)
spring 框架(1)
struts2(1)
SVN(1)
tiles 框架(1)
velocity(1)
webservice(6)
XML(3)
协议相关(3)
应用服务器(5)
性能优化(3)
技术族谱:软件开发相关知识体系的整理心得(图)(1)
搜索引擎(5)
操作系统(4)
数据建模(8)
电信综合施工调度系统-剖析(2)
规则引擎(1)
计算机基础(1)
设计模式(2)
资源(2)
集群与负载均衡(2)
面试(37)
随笔档案
2011年5月 (1)
2011年2月 (1)
2011年1月 (2)
2010年12月 (7)
2010年11月 (18)
2010年10月 (7)
2010年9月 (8)
2010年8月 (4)
2010年7月 (5)
2010年6月 (4)
2010年5月 (7)
2010年4月 (8)
2010年3月 (24)
2010年2月 (12)
2010年1月 (7)
2009年12月 (2)
2009年11月 (3)
2009年10月 (2)
2009年9月 (8)
2009年8月 (15)
2009年7月 (13)
2009年6月 (2)
2009年5月 (4)
文章分类
AJAX(9)
ANT(4)
EXTJS(15)
HTML+div+css实践(16)
J2EE相关技术与框架(26)
java基础及其原理(9)
JBPM(9)
JSTL(2)
rbac 权限管理模型(1)
webservice(1)
XML(3)
个人日志(4)
技术类英文文档翻译学习(1)
数据库(33)
数据结构
权限管理(2)
电信行业(2)
文章档案
2010年9月 (1)
2010年5月 (1)
2010年3月 (3)
2010年2月 (12)
2010年1月 (17)
2009年12月 (9)
2009年11月 (2)
2009年10月 (1)
2009年9月 (2)
2009年8月 (17)
2009年7月 (9)
2009年6月 (25)
2009年5月 (42)
新闻档案
2010年2月 (1)
收藏夹
TEST(2)
搜索
最新评论
1. re: Apache Commons fileUpload实现文件上传
good
--未来不是梦
2. re: js操作html的table,包括添加行,添加列,删除行,删除列
共和国分隔符
--菊花菊花姐
3. re: WAP网站可以用Google Analytics统计分析流量
请问ga中对wap站的跟踪在哪里可以查看,我操作的方式和pc站一样,都是把网址输入,就出来一段网址,这样似乎不对,是吗,前辈
--ga菜鸟
4. re: Velocity模板(VM)语言介绍
博主写的很详细,学习啦
--winclpt
5. re: 利用Java编写简单的WebService实例[未登录]
11
--111
阅读排行榜
1. Velocity模板(VM)语言介绍(30197)
2. JSTL对Map集合的操作(21115)
3. htmlunit 示例(16659)
4. 利用Java编写简单的WebService实例(13372)
5. webservice和soap原理(12074)
评论排行榜
1. Flex Builder 3 Help 中文版 (CHM/PDF)下载(19)
2. aptana汉化(3)
3. WAP网站可以用Google Analytics统计分析流量(2)
4. Android中添加Admob广告(转(2)
5. axis2 java.lang.reflect.InvocationTargetException (2)
交换两个变量的值,不使用第三个变量
字体大小:
大
中
小
正文
交换两个变量的值,不使用第三个变量
(2009-09-16 18:19:18)
标签:
杂谈
分类:
计算机
通常我们的做法是(尤其是在学习阶段):定义一个新的变量,借助它完成交换。代码如下:
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;轻松完成交换。
以上三个算法均实现了不借助其他变量来完成两个变量值的交换,相比较而言算术算法和位算法计算量相当,地址算法中计算较复杂,却可以很轻松的实现大类型(比如自定义的类或结构)的交换,而前两种只能进行整形数据的交换(理论上重载“^”运算符,也可以实现任意结构的交换)。
介绍这三种算法并不是要应用到实践当中,而是为了探讨技术,展示程序设计的魅力。从中可以看出,数学中的小技巧对程序设计而言具有相当的影响力,运用得当会有意想不到的神奇效果。而从实际的软件开发看,标准算法无疑是最好的,能够解决任意类型的交换问题
posted on 2009-12-02 14:55
小菜毛毛
阅读(7521)
评论(0)
编辑
收藏
所属分类:
java基础运用
、
面试
新用户注册
刷新评论列表
只有注册用户
登录
后才能发表评论。
网站导航:
博客园
IT新闻
知识库
C++博客
博问
管理
相关文章:
java sax 解析 实例
java反射详解
java中文汉字排序
javac -classpath的使用
JAVAC 命令详解(http://www.cnblogs.com/jeffchen/archive/2008/01/16/1041783.html)
Java虚拟机参数详解
用java实现comet,基于 HTTP长连接的实现,用于从服务端实时发送信息到客户端
字符,字节和编码
交换两个变量的值,不使用第三个变量
JAVA 书籍比较全的网站 http://ajava.org/book/
Copyright @ 小菜毛毛
Powered by:
.Text
and
ASP.NET
Theme by:
.NET Monster