黑马程序员技术交流社区

标题: 分享下我对于交换两个变量位置的心得 [打印本页]
作者: 大虾挂了    时间: 2013-9-12 01:40
标题: 分享下我对于交换两个变量位置的心得
※个人理解：想要交换两个变量，无论用什么方法，最核心的准则是：每次操作，必须保证任何一个量的信息都是直接或者间接的保存着。
比如：
int a=10,b=20;    //目标交换a和b变量的值

方法①：选用中间变量temp传递的方法

int temp;
a=temp;     //把a的内容存入temp，这样当我们给a赋值的时候就不会丢失a的信息了
a=b;       //如前所说，temp保存了a的信息，我们可以大胆的把b的值赋给a了，这样又保存了b的信息，所以接下来可以对b进行赋值了
b=temp;       //把temp的值（它存的是a的值）赋给b就一切ok了

这种方法没啥好说的，初学者必须掌握的方法，也很容易理解，很容易想到。

上述方法有个最大的弊端就是有第三个变量参与了，如何找到一个方法不涉及到第三个变量的参与呢。这里就涉及到我上面说到的那个问题，每次操作，任何一个量的信息都是直接或者间接的保存就ok。也就是说，当我们对a进行赋值的时候，a得到的信息要同时包含a和b的（若a只包含b的信息，b也是只包含自己的信息，a的信息就丢掉了，若a只包含a的信息，那么你不是什么都没做么？），至于怎么赋值，方法非常多，只要是数学上的可逆运算，应该都是可行的。

比如：

方法②：通过求和的方法
a=a+b;    //a中保存了a和b的信息
b=a-b;    //这里看似完全丢掉了b的信息，其实不是这样的，这里b保存了a的信息，a保存了a+b的信息，只要用再一次使用a-b，就可以获得b的信息
a=a-b;   //上面解释清楚了

刚才说了，只要是数学上的可逆运算，理论上都可以用来交换两个变量的位置。比如我们用乘积的方法:a=a*b;b=a/b;a=a/b;甚至我们可以用指数运算和对数运算的方法（不过这里可能会出现精度上的误差）。

方法②也有个弊端，如果a和b都是接近溢出的正数，那么相加之后会导致数据溢出。既然作和溢出，那作差好了，于是有这样的想法：

方法②改：
a=b-a;
b=b-a;
a=a+b;

关于这种方法，网上有通过数轴神马的去解释的，我感觉反而画蛇添足了，就如同我最开始说的，只要每次运算，每个变量的信息都是直接或者间接的保存着就OK。第一次给a的赋值必须是一个a和b同时参与的运算才可以。如果忽略变量类型的问题，加减乘除，指数对数，平方和平方差神马的随你便（考虑到变量是int类型，先除后乘就不行了，指数和对数也不行了）。这里只不过用了减法而已。
a中保存了b-a的信息，第二步只不过要让b获得最开始a的信息就可以。也就是我们要通过什么运算让b和b-a变成a，自然用b-(b-a)，现在就差让a中保存b的信息了。而a中保存的是b-a，b中保存的是a，我们要怎么用b-a和a得到b，自然相加了。

方法②改貌似比方法②好了，但也仅限于这个题，如果a大于b，那么b-a就变成负数了，但是我们又不喜欢负数呢？那么前面就要加个判断，始终让大的减小的，但是麻烦啊。甚至说如果大的是一个接近溢出的正数，小的是一个接近溢出的负数，大的一减小的，最终溢出了。这时还不如采用方法②呢，难道之前还要加个正负的判断么？麻烦透了有木有！！！

网上还有一种是使用指针的方法，C#中的指针我还不会用，不知道和C里的指针一不一样，而且指针这个东西，像我这种新手用起来容易悲剧有木有，所以这里不提这种偏激的方法了。

这里找到一个让很让我佩服的方法，也正是看到这个方法，才促使我想出那个交换变量的核心准则。

方法EX：位运算，异或

a=a^b;
b=a^b;
a=a^b;

任务完成，这样就完成了a和b值的交换，而且没有利用第三个量，不会出现数据溢出，完美的方法有木有。

位运算符有很多种（不知道的自己百度下）：
我们对每个运算符是否能解决这个问题进行分析（我只挑出不合理的地方）

&：与（这个类似于乘号）
a=a&b
当某一位计算结果为0且该位b的值为0时，我们已经丢失a在此位的信息，因为此时无论a在此位为0还是1都是可行的。

|：或（这个符号类似于加号，但是两个1相加仍是1）
a=a|b
当某一位计算结果为1且该位b的值为1时，我们又丢失了a在此位的信息，此时同样a的值无论是0还是1都是可行的

~：取补（这个是单目运算符，无法同时让a和b进来参与运算）

<<：左移；>>：右移。关于这两个运算符，也是不可行的。如果先a>>b，那么丢失好多数据（a的后b位都被置零了）。如果先a<<b，那么这到题就已经溢出了，就算不溢出，最后要让a中得到b的值那一步，涉及到对数运算的，超出int的范畴了，需要进行强制转换，这时候也许会因为小小的误差出现错误。算法大致这样：
  1. int a = 1;
  2.             int b = 8;
  3.                      
  4.             a = a << b;
  5.             b = a >> b;
  6.             
  7.             a = (int)(Math.Log(a / b) / Math.Log(2));
  8.             Console.WriteLine("{0},{1}",a,b);
  9.             Console.ReadKey();
复制代码
上面这个方法适用于b是很小的正整数才行（必须保证a左移b位依然没超过int的范围），纯属娱乐用吧。

最后说^：异或
0^0=0
0^1=1
1^0=1
1^1=0
看起来就是相同为0，不同为1，但是这里我觉得我的理解方式更好，就是把它当做进位忽略的加法运算，或者借位忽略的减法运算。这样有助于我们理解上面换位算法的正确性。

以不考虑进位的加法运算为例：
//这里用c表示a中某一位二进制数，d表示b中对应位置的二进制数
a=a^b;  //c=c+d
b=a^b;  //d=(c+d)+d=c+2d=c (d=0这个等式自然成立，由于是忽略进位，所以d=1时，2d进位被忽略，这个等式依然成立)
a=a^b;  //a=(c+d)+c=2c+d=d (原理同上)
通过这样的操作，a和b中每一位二进制数字都对换了位置，最终达到了a和b换位的目的。
真心是很不错的方法。

作者: haxyek    时间: 2013-9-12 10:20
很不错的总结。。
作者: 宋清飞    时间: 2013-9-12 18:22
总结的不错，只有理解了交换变量的核心思路，才能想出位运算这种方法。
不过“a=temp;   //把a的内容存入temp”，这里算得上是笔误了吧。
作者: 杨靖    时间: 2013-9-12 19:53
只能{:soso_e183:}{:soso_e183:}{:soso_e183:}
作者: 大虾挂了    时间: 2013-9-12 20:05
宋清飞 发表于 2013-9-12 18:22
总结的不错，只有理解了交换变量的核心思路，才能想出位运算这种方法。
不过“a=temp;   //把a的内容存入te ...

啊。。。。o(╯□╰)o了，{:soso_e141:}当时我一定是手残了，不是脑残！！！
作者: 王赟    时间: 2013-9-14 13:45
好高端！！！！



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2