文档章节

交换两个变量的思考

r
 ranjiewen
发布于 2016/11/03 23:50
字数 1459
阅读 2
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

 

网上存在三种方法:
 
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=12;b=10

      通过以上运算,a和b中的值就进行了交换。表面上看起来很简单,但是不容易想到,尤其是在习惯标准算法之后。

      此算法与标准算法相比,多了三个计算的过程,但是没有借助临时变量。(以下称为算术算法)
      对于字符串做这种交换的话, 可以使用字符串连接和substr的方式来做, 建议在追加字符串的时候, insert到那个字符串的最前面, 防止其中一个字符串是另一个字符串的子串导致错误..
2) 指针操作
      对指针的操作实际上进行的是整数运算。比如:两个int指针相减得到一个整数N,该整数表示两个指针变量在内存中的储存位置隔了N*sizeof(int)个字节;int指针和一个整数相加,例如“a+10”表示以a为基地址,偏移为10*sizeof(int)处的int变量。所以我们完全可以通过和算术算法类似的运算来完成指针变量值的交换,从而达到交换变量的目的。即:
int *a,*b;    
a=new int(10);        //给指针赋值
b=new int(20);        //a=0x00030828,b=0x00030840
a=(int*)(b-a);        //a=0x00000006
b=(int*)(b-int(a));   //b=0x00030828
a=(int*)(b+int(a));   //a=0x00030840

需要注意的是:最后三句话中,只有第一句是两个指针之间的计算,其他都是指针和整数的计算,否则会导致计算错误,严重导致系统出错。

通过以上运算a、b的地址就完成了交换,a指向了原先b指向的值,b指向原先a指向的值!

     此算法同样没有使用第三变量就完成了值的交换,与算术算法比较它显得不好理解,但是它有它的优点即在交换很大的数据类型时,比如说自定义的大型结构或者类,它的执行速度比算术算法快。因为它交换的时地址,而变量值在内存中是没有移动过的。(以下称为地址算法)

3) 位运算
通过异或运算也能实现变量的交换,这也许是最为神奇的,请看以下代码:
int a=10,b=12;  //a=1010 b=1100;
a=a^b;    //a=1010^1100=0110;
b=a^b;    //b=0110^1100=1010;
a=a^b;    //a=0110^1010=1100;
//a=1100=12;b=1010;

异或操作, 对每一位而言, 0可以取得原数, 1可以取得该位的补码.   //异或----相同取0,不同取1

第一次异或, 用0填充了相同的位, 用1填充了不同的位.

第二次异或, 操作数b和第一次结果做异或, 第一次的结果用0(那些相同的位)取得了b自己的值(由于这些位相同), 而第一次结果是1的那些位, 则取得了操作数b的该位的补码, 这些位的值是不同的, 因此, 操作数b中该位的补码, 实际上就是操作数a中的原码.

这样, 第二次的异或中, 将第一个操作数a中的所有位就都覆盖到了操作数b中, 完成了将a赋值给b句柄的工作.

第三次异或, 原理和第二次一样, 将b赋值给a句柄.

    如果仔细思考,可以发现实际上有无数种方法。为什么需要第三个变量?我想这是绝大多数初学编程时都思考过的问题。我本身是做信号的,所以从信息的角度来分析。两个变量,必然存在两份信息(姑且以份为单位),如果直接交换,a=b,则a原来的信息丢失,所以引入一个临时变量来保存a的信息,以确保信息完整性。也就是说,temp的作用就是保存交换过程可能损失的信息量,那么只要这个信息量不损失,则无需temp.做编解码的人都知道,编码的是残差数据。残差数据包含的就是那额外的信息量。那么,完全可以在交换过程中传递额外信息,也就是a,b之间的耦合信息,则交换过程不会发生信息丢失,也就无需第三个变量。这耦合信息可以是a-b,也可以是a^b,还可以是a*b.如:
a=a*b;
a=a/b;
b=a/b;
同样可以完成交换(仅提供思路,未考虑除0溢出等问题)。举一反三,可以有无穷种方法,但原理都是一样的。

附上练习题目:
//题目描述
//
//请实现一个算法,在不使用额外数据结构和储存空间的情况下,翻转一个给定的字符串(可以使用单个过程变量)。
//给定一个string iniString,请返回一个string,为翻转后的字符串。保证字符串的长度小于等于5000。
//测试样例:
//"This is nowcoder"
//返回:"redocwon si sihT"

#include<iostream>
#include<string>
using namespace std;
class Reverse {
public:
    string reverseString(string iniString) {
        // write code here
        //string result;
        if(iniString.empty())
        {
            return  iniString;
        }
        //for (int i = iniString.size(); i >0; i--)  //error: control reaches end of non-void function [-Werror,-Wreturn-type]  //没有返回值啊
        //{
        //    cout << iniString[i - 1];
        //}
        //两个数字交换,可以借助第三变量,也可以不借助第三变量;有三种方法,自行总结
        //iniString[i] ^= iniString[j] ^= iniString[i] ^= iniString[j];//交换  
        for (int i = 0; i < iniString.size()/2; i++)
        {
            char temp = iniString[i];
            iniString[i] = iniString[iniString.size() - 1 - i];
            iniString[iniString.size() - 1 - i] = temp;
        }

        return iniString;
    }
};

 




本文转载自:http://www.cnblogs.com/ranjiewen/p/5305086.html

下一篇: Treap树
r
粉丝 1
博文 203
码字总数 28
作品 0
武汉
程序员
私信 提问
HTML5 postMessage 跨域交换数据

今天我们来学习一下HTML5的api,利用postMessage来跨域交换数据。和前面一些方式交换数据方式不同的是,利用postMessage不能和服务端交换数据,只能在两个窗口(iframe)之间交换数据,废话不...

罗马教堂的钟声
2015/12/29
115
0
Java交换两个Integer-一道无聊的题的思考

1.最近网上看到的一道题,有人说一道很无聊的题,但我觉得有必要记录一下。 2.题目

汉堡OSC
04/14
30
0
【技巧】不使用中间变量交换两个变量的值

最近在论坛里又看到一个很熟悉的问题:不使用中间变量交换两个变量的值。网上流传的大概有两种方法,在这里总结一下。 【方法一】 假设需要交换的两个变量都是整型,变量名分别为a和b。 a = ...

YHZhu
2010/07/08
615
0
C语言编程学习:使用函数必须知道的3点注意事项

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你学知识
2018/06/13
21
0
旋转字符串算法由浅入深

Author:bakari Date:2012.9.8 昨天在写一个旋转字符串的函数时,写着写着发现有好多种方法,最简单的莫过于替换然后覆盖再插入。不要小看这种小的算法,其实这其中蕴含着很多容易忽略的编程...

chambai
2012/09/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx反向代理+负载均衡+服务器宕机解决办法

反向代理 作用:保证系统安全,不暴露服务器IP,利用nginx服务器,利用内网ip进行访问,避免出现攻击服务器的情况 启动本地tomact,127.0.0.1:8080可以访问到tomcat管理页面 效果:通过 bbs....

Jack088
7分钟前
1
0
返回IEnumerable 与IQueryable相比 [关闭]

返回IQueryable<T>与IEnumerable<T>之间有什么区别? IQueryable<Customer> custs = from c in db.Customerswhere c.City == "<City>"select c;IEnumerable<Customer> custs = from c i......

技术盛宴
14分钟前
2
0
开放下载 | 《Knative 云原生应用开发指南》开启云原生时代 Serverless 之门

点击下载《Knative 云原生应用开发指南》 自 2018 年 Knative 项目开源后,就得到了广大开发者的密切关注。Knative 在 Kubernetes 之上提供了一套完整的应用 Serverless 编排服务,让应用开发...

阿里巴巴云原生
19分钟前
2
0
解密淘宝推荐实战,打造 “比你还懂你” 的个性化APP

手淘推荐简介 手淘推荐的快速发展源于2014年阿里“All in 无线”战略的提出。在无线时代,手机屏幕变小,用户无法同时浏览多个视窗,交互变得困难,在这样的情况下,手淘借助个性化推荐来提升...

阿里云官方博客
21分钟前
2
0
内核程序中进程的pid,handle,eprocess之间相互转换的方法

在内核程序开发中,我们常常需要取得某进程的pid或句柄,或者需要检索进程的eprocess结构,很多API函数需要的参数也不同,所以掌握pid<->handle<->eprocess相互转换的方法会大大提高我们的开...

simpower
23分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部