不生成中间变量,交换两个数

时间:2022-12-22 19:31:45

普通程序员方法:  

     交换两个数是比较经典而且基础的算法之一。 我们要交换两个数字,一般的做法是定义个中间变量,然后交换赋值。例如:

int temp;
temp = a;
a = b;
b = temp;

    对于初学者来说,这可以说是除了 hello world 外,敲得最多的一段代码了。但在手持设备中,内存资源很宝贵,甚至要求不开辟新的空间,就地完成交换工作。


文艺程序员方法:

    这时又有很多人想出了以下的方法,用一个变量存储两个信息的集合,用另外一个变量存储任意一个信息,这种存储方式就可以完成交换的工作。例如:

a = a + b;
b = a - b;
a = a - b;

 

显然这是一个巧妙的方法,但是两个变量相加后却存在内存溢出的危险。于是又有人想出了第三种方法。


2B程序员方法:

到目前为止,思路是没错的,就是寻找另外一种数据存储的模式,用一个变量保存两条信息的集合,我们仍然需要采用这种模式解决这个问题,但原先的简单相加的模式是不行了。于是又有人想到,集合两个整型数字,是否可以从其二进制表达方面来考虑?

使用位异或来存储集合信息。

用 1 和 0 来做简单的验证,看是否可以用异或的方式,存储信息的集合:

如果两个数是a = 1和b = 0,则:
集合 = 1 ^ 0 = 1
0 ˆ 集合 = 1
1 ^ 集合 = 0

如果两个数是a = 1和b = 1,则
集合 = 1 ^ 1 = 0
1 ^ 集合 = 1

如果两个数是a = 0和b = 0,则
集合 = 0 ^ 0
0 ^ 集合 = 0

验证结果: 可以采用信息集合的方式存储

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

     这种方式不用担心数据溢出,应该算是就地交换两个数的最佳解决方案了。

    

    我记得在几年前,我的好朋友,国际非著名算法学家,国际著名大学博士后,2030年图灵奖获得者老卢先生就跟我聊过他的一个关于服务器上数据备份的想法。他说,服务器上的数据很重要,如果硬盘损坏,会造成难以估量的损失,所以需要对硬盘数据进行备份,但如果我们对每一块硬盘都提供等价大小的空间进行备份的话,我们就需要两倍数量的硬盘以保证备份的完整,这种冗余是 100%。我们使用了100块硬盘就必须再拿出100块硬盘进行备份。但如果我们能够将100块硬盘上所有的数据异或一次,然后用一块硬盘存储起来,我们就可以使用一块硬盘对100块硬盘进行备份。当然,具体将多少块硬盘的数据集合在一起,是需要进行概率计算的,因为如果有两块硬盘同时损坏,那么备份的数据就会失效。我们必须计算出多少块硬盘里,两块硬盘同时损坏的概率,小于使用100%冗余方法备份中,运行硬盘和备份硬盘同时损坏的概率。在计算出这个数量以后,我们即可使用这种备份的方式。

     老卢的这种思路不可谓不神奇,因此也列在这里,供大家参考。

 

不生成中间变量,交换两个数
参考及摘抄于: http://hi.baidu.com/tianyamingyuedao/blog/item/2d7db3098b8e72306a60fb01.html