`

论一面试题:怎样在不使用第三方变量交换两个参数的值

 
阅读更多

   在学习程序语言和进行程序设计的时候,交换两个变量的值是经常要使用的。通常我们的做法是(尤其是在学习阶段):定义一个新的变量,借助它完成交换。代码如下:  
         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;轻松完成交换。     
  以上三个算法均实现了不借助其他变量来完成两个变量值的交换,相比较而言算术算法和位算法计算量相当,地址算法中计算较复杂,却可以很轻松的实现大类型(比如自定义的类或结构)的交换,而前两种只能进行整形数据的交换(理论上重载“^”运算符,也可以实现任意结构的交换)。  
   
  介绍这三种算法并不是要应用到实践当中,而是为了探讨技术,展示程序设计的魅力。从中可以看出,数学中的小技巧对程序设计而言具有相当的影响力,运用得当会有意想不到的神奇效果。而从实际的软件开发看,标准算法无疑是最好的,能够解决任意类型的交换问题。

分享到:
评论

相关推荐

    示例代码:不经过中间变量交换两个数

    以下是一段C语言代码示例,演示了如何使用位异或运算符实现不使用额外变量交换两个数的值: ```c void main() { int a = 3; int b = 1; // 第一步:a = a ^ b a = a ^ b; // a 的值现在是 3 ^ 1 = 2 // 第二...

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

    使用三种方法交换来个数字 方法一:使用第三方变量交换数据; 方法二:使用加减法,并且不使用第三方...方法三:使用异或方法交换,并且不使用第三方变量 思路:一个数异或另一个数偶次,都等于这个数本身。

    每日一题:不适用第三个变量,实现交换两个输入参数1

    "每日一题:不适用第三个变量,实现交换两个输入参数1"和【描述】描述了一个这样的问题,要求编写一个名为`swap`的函数,该函数接受两个参数`a`和`b`,并且在不使用第三个变量的情况下交换它们的值。 在【标签】...

    Python3之不使用第三方变量,实现交换两个变量的值

    ### Python3之不使用第三方变量实现交换两个变量的值 在编程中,交换两个变量的值是一个常见的操作。通常的做法是引入一个临时变量来完成这一过程。然而,在Python这种动态语言中,我们可以采用更为简洁的方式来...

    交换两个变量的值,不使用第三个变量的方法及实现.docx

    在编程中,交换两个变量的值是一个常见的任务,但有时我们可能希望避免使用第三个临时变量。本文探讨了几种不依赖额外变量实现交换的方法,主要针对C/C++编程语言。 1. **算术运算**: 算术运算方法利用加减法或乘...

    BAT批处理脚本-加密解密-交换两个变量的值而不使用临时变量.zip

    在标题提到的"BAT批处理脚本-加密解密-交换两个变量的值而不使用临时变量.zip"中,主要涉及到以下几个知识点: 1. **批处理脚本基础**: - BAT脚本是一种基于DOS命令的文本文件,扩展名为.bat,里面包含了各种DOS...

    用异或来交换两个变量能提高速度是错误的

    ### 使用异或交换两个变量是否能提升速度? #### 引言 在计算机编程领域,特别是对于初学者来说,经常会接触到一些看似巧妙但实际上并无益处甚至有害的编程技巧。其中一个经常被提及的例子就是利用异或运算来交换...

    kettle变量参数设置

    命名参数在运行时被映射为变量,例如定义了一个名为 `foo` 的命名参数,则可以通过 `${foo}` 的形式在转换或作业中引用该参数。 #### 五、总结 通过对Kettle中的变量(Variable)、位置参数(Argument)和命名参数...

    函数指针来交换两个数

    用一个函数指针来交换两个数

    用引用交换两个整形或字符串型

    在`main`函数中,我们首先定义了两个整型变量`a`和`b`,并调用`swap`函数交换它们的值。然后输出这两个变量的值,可以看到它们的值已经被成功交换。 接着定义了两个指向字符串的指针`pa`和`pb`,并通过`swap1`函数...

    第8章 指针-2指针变量作函数参数 - 典型实例 - 两数交换new1

    在这里,`Swap`函数接受两个整数指针作为参数,`*x`和`*y`分别代表它们所指向的值。通过解引用操作,我们可以直接修改`a`和`b`的值,从而实现了两数的交换。 值得注意的是,当传递数组作为函数参数时,数组名在函数...

    Delphi交换两个变量值的方法(含示例)

    在编程领域,交换两个变量的值是一个常见的操作。在Delphi这种基于Pascal语言的环境中,我们可以使用多种方法来实现这一目标。本文将探讨几种在Delphi中交换两个变量值的常见方法,并通过示例代码进行详细解释。 一...

    c代码-2.功能:不用第三个变量,实现两个数的对调操作。

    在C语言编程中,对调两个变量的值是一项常见的任务,通常我们使用第三个临时变量来完成这个过程。但是,有一种巧妙的方法可以在不使用第三个变量的情况下实现两个数的对调,这种方法利用了算术运算和赋值操作的结合...

    Java 程序交换两个数字.docx

    Java 程序交换两个数字的方法主要有三种:使用第三个变量、不使用额外变量以及使用异或操作。下面分别详细介绍这三种方法。 1. 使用第三个变量交换值 这种方法是最直观的,也是大多数初学者首选的方式。它涉及到...

    用C#语言实现两个数的交换

    对于多线程环境,可以使用`Interlocked`类的`Exchange`方法来原子地交换两个变量的值,确保在并发情况下不会出现数据不一致的问题: ```csharp int a = 5; int b = 10; Interlocked.Exchange(ref a, b); ``...

    Informatica+PowerCenter+V8参数和变量使用指南

    《Informatica PowerCenter V8参数和变量使用指南》是一份深度解析Informatica PowerCenter V8在处理数据集成任务时如何有效利用参数和变量的详细文档。Informatica PowerCenter是一款强大的企业级数据集成工具,它...

    Jenkins高级篇之Pipeline技巧篇-2-如何处理多个参数化变量.rar

    可以使用`params`的组合,例如,根据两个参数的值决定是否触发某些操作。同时,可以利用`active Choices Plugin`等插件为参数设置依赖关系,实现动态参数生成和验证。 9. **参数存储与重用** 用户输入的参数值...

    两变量值互换

    在标题“两变量值互换”中提到的方法,实际上是指在不借助额外辅助变量的情况下,通过位运算来实现两个变量的值互换。这种技术在内存有限或者对效率有较高要求的场景下特别有用。 首先,我们来看传统的加法方法。...

    kettle8 模拟表输入查询表名,然后在另一个表输入中使用变量使用

    在这个过程中,变量的使用是关键,它允许我们灵活地处理不确定或需要动态设置的数据源。 首先,让我们详细了解一下“模拟表输入”组件。在Kettle8中,模拟表输入实际上可能指的是“表输入”步骤,它可以连接到...

    不使用中间变量,交换int型的 a, b两个变量的值。

    在编程中,交换两个变量的值是一个常见的操作。在给定的标题和描述中,讨论的是如何不使用中间变量来实现这个操作。这里给出了四种不同的方法,分别由四位不同的贡献者提出,每种方法都有其独特之处。我们将逐一分析...

Global site tag (gtag.js) - Google Analytics