坚持学习/暴露问题/不断提升

c++/设计模式/算法结构/系统
posts - 2, comments - 20, trackbacks - 0, articles - 0

本篇摘要

  交换两个变量是非常古老的话题了,然而本文绝对保证给你新鲜的感觉!本文涉及到最简单的“不用临时变量交换两个整数”还涉及到如果利用异或来实现两个指针、两个浮点数的交换,要知道指针的浮点数是不允许直接异或运算的哦;同时本文还阐述了如何交换用户自定义类型及其指针。

本文完全是个人自由发挥之作,欢迎广大砖家来拍砖,我个人感觉文中必然有很多不足,甚至错误之处,这并非我谦虚,事实上我写本文的目的就是希望在挨砖板中成长!新人或许看不懂很多东西,如果你看不懂,那么就不要随便膜拜,因为看不懂的或许原本就是错的,高手看完后如果本文写得还可以,那么请留下好评,以供新手参考本文是否有阅读本文的必要,如果觉得本文完全是垃圾,那么请不要客气,您可以赤裸地,露骨地指出本文的错误和不足,让本人在批评中进步,但请不要进行人身攻击,谢谢!

准备工作

  由于本文涉及到交换两个用户自定义类型的变量,为了举例方便,本文定义如下的Person类(其中省略了拷贝构造函数的重写,因为本文不用到它):

class Person
{
public:
         Person(
int age ,const char* name ):m_Age(age)
         {
                   
int len = strlen(name);
                   
this->m_Name = new char[len+1];
                   strcpy(
this->m_Name,name);
         }
         Person()
         {
                   
this->m_Age = -1;
                   
this->m_Name = 0;
         }
         
void PrintSelf()
         {
                   cout
<<this->m_Name<<":"<<this->m_Age<<endl;
         }
         Person
& operator= (const Person& other)
         {
                   
if (this == &other)
                   {
                            
return *this;
                   }
                   
else
                   {
                            
this->m_Age = other.m_Age;
                            delete 
this->m_Name;
                            
int len = strlen(other.m_Name);
                            
this->m_Name = new char[len+1];
                            strcpy(
this->m_Name,other.m_Name);
                            
return *this;
                   }
         }
         
~Person()
         {
                   delete 
this->m_Name;
         }
private:
         
int m_Age;
         
char* m_Name;
};

  为了后文表述方便,这里再定义Person类的两个对象和两个指针,定义如下:

Person youngMan(18,” young man”);

Person oldMan(81,” old man”);

Person* pYoungMan = &youngMan;

Person* pOldMan = &oldMan;

最常见的交换两个对象的方法:GeneralSwap

通常,我们为了交换两个变量都采取下面的方法来实现,它需要一个临时变量:

template<class T>
void GeneralSwap(T& a,T& b)
{
         T temp;
         temp 
= a;
         a 
= b;
         b 
= temp;
}

    显然人人都知道这个写法,但是我仍然觉得有必要重点申明几点:1、注意函数的参数是引用(也可指针),为什么我就不解释了;2、这个交换函数基本上是最简单、最通用的,简单到人人都会写,通用到它几乎可适用于任何数据类型:char , int , long , float, double等各种系统自定义数学类型(无符号的,带符号的),用户自定义数据类型(需要有默认构造函数,否则语句T temp;会报错),以及各种指针(系统自定义类型的指针,和用户自定义类型的指针)。当然用户自定义类型中如果包含了指针数据成员,那么需要重载赋值运算符,事实上这样的用户自定义类,你都应该自己重写赋值运算符、拷贝构造函数,否则不但不能使用GeneralSwap,其他涉及到拷贝和赋值的操作都可能导致出错!

利用GeneralSwap交换两个用户自定义对象

    下面深入探讨一下关于用户自定义对象的交换问题:针对准备工作中的Person类的两个对象youngMan和oldMan语句GeneralSwap(youngMan,oldMan);能实现他们的交换。短短一行代码就能实现将一个18岁的花季少男跟一个81岁的老头子掉包,这像不像是耍魔术啊,呵呵。要注意了,该交换代码虽短,但涉及到默认构造函数的调用(GeneralSwap中的T temp;语句)和赋值运算符重载函数的调用(GeneralSwap中的三个赋值语句)。

或许您很少这么用吧,事实上在我写本文之前,我都没真正交换过两个自定义的对象,通常我们都不愿意这么交换两个自定义对象。原因是效率太低!或许你要问,万一有的应用就是需要交换两个自定义的对象怎么办?好办,用指针啊!对,指针的好处就是效率高,为什么C++比java效率高,原因之一就是java取消了指针。下面的第一行代码就是交换两个Person类的指针:

GeneralSwap(pYoungMan,pOldMan);

//GeneralSwap(*pYoungMan,* pOldMan);     //效率低

    为什么使用指针就效率高了呢?原因是指针就是地址,地址就是整数,于是问题等价于交换两个整数,因此它不调用赋值运算符重载函数!只要你在应用程序中始终通过指向对象的指针来访问对象,那么交换两个指针就能达到交换对象的目的。注意被注释掉的第二行代码,它是正确的,但是它又回到了交换两个实际对象,其效率低,最好不要这么用!

对于这个最常见、最简单的GeneralSwap我都废话了一大堆,而且还扯出了一个没多少用的关于用户自定义对象的交换问题,这实属个人思维散射,请砖家们狠狠地拍。

在进行下一个方法之前,再次强调一点,这个方法的特点是简单、通用!后面的方法都将与之做比较。

利用加减法实现两个数的交换

    几乎人人都知道还可以利用加减法来实现两个数的交换,其代码也异常简单:

template<class T>
void Add_Sub_Swap_1(T& a, T& b)
{
        a 
= a+b;
        b 
= a-b;
         a 
= a-b;
}

    Add_Sub_Swap_1可以用于交换两个整数,但由于涉及加减法,因此有数据溢出的危险;也可以用于交换浮点数,但是有可能由于舍入误差导致结果不准确。

Add_Sub_Swap_1不能用于交换两个用户自定义的对象,下面的语句编译就通过不,编译器告诉你Person类没有定义operator +等符号:

Add_Sub_Swap_1(youngMan,oldMan);//编译通不过!

    Add_Sub_Swap_1不能用于交换两个指针,语句Add_Sub_Swap_1(pYoungMan,pOldMan);编译时将报错:error C2110: cannot add two pointers,是的,两个指针不能直接做加法运算(减法是可以的)。那么是不是就不能利用加减法实现两个指针的交换呢?答案是:“可以!”,接下来我将阐述如何实现。

利用加减法交换两个指针

    Add_Sub_Swap_1不能用于交换两个指针,前面我说可以用加减法来实现两个指针的交换,这是有根据的:指针仍然是变量,只不过它是存储普通变量的地址的变量。只要我们把指针“看作”变量,那么就能实现加法。那么如何把指针“看作”变量呢?答案是:“通过强制类型转换”!指针表示变量的地址,在32位平台上它是一个无符号的整数,因此可以将指针强制转换为无符号类型的整数。我对上面的Add_Sub_Swap_1进行了改进:

template<class T>
void Add_Sub_Swap_2(T& a, T& b)
{
         
*(( unsigned*)(&a)) = *(( unsigned*)(&a)) + *(( unsigned*)(&b));
         
*(( unsigned*)(&b)) = *(( unsigned*)(&a)) - *(( unsigned*)(&b));
         
*(( unsigned*)(&a)) = *(( unsigned*)(&a)) - *(( unsigned*)(&b));
}

    利用Add_Sub_Swap_2既可以交换两个普通的整数、浮点数同时它可以交换两个任意类型的指针(包含系统预定义类型和用户自定义类型的指针,其实本质上所有指针都属于同一种类型:32位无符号整数类型)。不信您试试Add_Sub_Swap_2(pYoungMan,pOldMan);它能得到正确答案。

虽然Add_Sub_Swap_2解决了Add_Sub_Swap_1无法交换两个指针的问题,但是它仍然无法交换两个用户自定义类型的变量,原因是用户自定义类型没有加减法运算。看来要想用加减法实现两个用户定义类型的交换是不可能的了(除非用户自定义的operator+和operator-能满足交换两个对象的目的,这很难,除非是非常简单的用户自定义类型,比如你不使用系统类型int非要定义一个MyInt类)。

利用异或实现两个整数的交换

    同样地,几乎人人都知道利用异或来交换两个数,其实现也非常简单:

template <class T>
void Xor_Swap_1(T& a,T& b)
{
         a 
= a^b;
         b 
= a^b;
         a 
= a^b;
}

    上面的函数的实用性非常有限,它只能交换两个整数(包含char,int,long),要想交换两个浮点数是不行的,因为浮点数不能参与位运算,要想交换两个指针也是不行的,编译器不允许你把两个指针拿来做位运算,要想交换两个用户自定义对象也是不行的,因为它仍然不能参与位运算。那么是不是利用异或交换两个变量就没法用于浮点数、指针和用户自定义的对象了呢?答案是“能”!后面几节我将阐述这些问题。

利用异或实现两个float和指针的交换

    前面的Xor_Swap_1无法实现两个浮点数和指针的交换,其原因是浮点数和指针均不直接支持位运算。那么如何才能利用异或来交换两个浮点数和指针呢?方法仍然是“强制类型转换”!因为浮点数在内存中仍然是用一串二进制bit来表示的嘛,只要把浮点数看作(强制类型转换)二进制bit构成的整数,那么就能进行位运算了,至于指针嘛,处理方法完全相同。具体如何做呢,其实现大概是这样的:

template <class T>
void Xor_Swap_2(T& a,T& b)
{
         
*((unsigned*)(&a)) = *((unsigned*)(&a)) ^ *((unsigned*)(&b));
         
*((unsigned*)(&b)) = *((unsigned*)(&a)) ^ *((unsigned*)(&b));
         
*((unsigned*)(&a)) = *((unsigned*)(&a)) ^ *((unsigned*)(&b));
}

    利用这个函数可以交换两个float类型的变量,也可以交换任意类型的指针!非常值得注意的是:用它交换两个double类型数据或者两个Person类的对象(youngMan,oldMan)均能编译通过,但是其结果却是错的。至于为什么,以及如何解决,这将是我下一节要阐述的内容。

利用异或实现两个double类型变量和用户自定义变量的交换

     Xor_Swap_2解决了利用异或不能交换两个float数据和指针的问题,然而它却不能正确地交换两个double数据和两个Person类对象。这是为什么呢?原因是函数内部是把参数强制类型转换成unsigned类型的,而sizeof(float)和sizeof(pointor)的值都等于sizeof(unsigned),但是sizeof(double)却不等于sizeof(unsigned),也就是说把double强制转换成unsigned类型时,发生了“位截断”(在概念是区别与数据截断),那么得到的结果肯定就不对了。至于无法交换两个Person类对象,其原因也相同。

这里我要深入分析一下强制类型转换是如何发生位截断的,首先看看以下测试的输出结果,注意代码中的注释,为了节约篇幅,我把值得注意的地方都放在注释中了:

Double a = 1.0,b=2.0;

Xor_Swap_2(a,b);//交换两个double数据

Cout<<a<<b;//输出仍然是1.0和2.0,a,b的值并未改变

Xor_Swap_2(youngMan,oldMan);//交换两个用户自定义对象

youngMan.PrintSelf();//输出young man:81

oldMan.PrintSelf();//输出old man:18

    可以看出两个double数据并没被交换,而两个Person对象在交换之后发生了怪异现象:产生了81岁的年轻人和18岁的老年人!这一点正好说明强制类型转换时发生了位截断,由于Person类的第一个数据成员m_Age正好是int型,在Xor_Swap_2内部做强制类型转换时正好取得了两个对象的m_Age成员,于是出现了两个对象被部分交换的情况,那么又如何解释两个double数据没有变法呢?事实上两个double数据仍然发生了部分交换,因为这里的两个double数(a,b)的前4个字节正好相同,因此看不出部分交换。

既然我们知道了Xor_Swap_2为什么不能用于交换两个double类型的数据和两个用户自定义的数据,那么就有办法对它进行改进。具体改进的思想就是把参数按照一个byte一个byte地分别异或,按照这个思路我实现了如下的函数:

template <class T>
void Xor_Swap_3(T& a,T& b)
{
         
int size = sizeof(T);
         
for (int i = 0;i<size;i++)
         {
                   
*((unsigned char*)(&a)+i) = (*((unsigned char*)(&a)+i)) ^ (*((unsigned char*)(&b)+i));
                   
*((unsigned char*)(&b)+i) = (*((unsigned char*)(&a)+i)) ^ (*((unsigned char*)(&b)+i));
                   
*((unsigned char*)(&a)+i) = (*((unsigned char*)(&a)+i)) ^ (*((unsigned char*)(&b)+i));
         }
}

     这个版本的函数不仅能交换两个整数、任何指针、float数和double数,更牛逼的是它能交换两个用户定义类型的变量!事实上它基本上是在内存一级上操作数据,而任何类型的数据对象最终都表现为内存对象。这其实就是通过内存拷贝实现两个对象的交换的一个版本吧,当然还有利用memcpy等手段进行内存拷贝来实现两个变量的交换的,这里我就不赘述了。

结束语

    本篇到此写完了,有种不好的感觉,因为文中大量使用“强制类型转换”而这个东西是C++中容易出错的地方,而我再写本文时,并没有去复习关于强制类型转换的相关知识,因此担心很多地方有潜在的出错可能,还请各位砖家指正!

@import url(http://www.cppblog.com/CuteSoft_Client/CuteEditor/Load.ashx?type=style&file=SyntaxHighlighter.css);@import url(/css/cuteeditor.css);

Feedback

# re: 绝对深入剖析各种方法实现两个变量的交换[未登录]  回复  更多评论   

2011-08-10 13:11 by Chipset
这不是4位机和8位机的时代了,这种交换容易出错。如果两个数相同这种交换是不是会出错?大的数据结构交换用move语义,C++0x,此时依赖大量数据拷贝的交换永远快不起来。

# re: 绝对深入剖析各种方法实现两个变量的交换  回复  更多评论   

2011-08-10 17:22 by 他她女鞋
好好了解学习一下。

# re: 绝对深入剖析各种方法实现两个变量的交换  回复  更多评论   

2011-08-10 21:33 by 疯狂的面包
还是 ^ 操作 本质还是玩这个。 我看不到有什么新意。还要注意自己和自己交换。

# re: 绝对深入剖析各种方法实现两个变量的交换  回复  更多评论   

2011-08-11 13:33 by right
虽然这种探索的意义不大,楼主的探索精神还是值得表扬的。
提一个函数,我没仔细看,可能楼主用的上
float IntBitsToFloat(int x)
{
union
{
int n;
float f;
} m;
m.n = x;
return m.f;
}
int FloatToIntBits(float x)
{
union
{
float f;
int n;
} m;
m.f = x;
return m.n;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理