啊哈磊_编程从这里起步

标题: 【小伙伴的们的算法】交换a和b [打印本页]

作者: 啊哈磊    时间: 2018-2-27 13:49
标题: 【小伙伴的们的算法】交换a和b
vfleaking供稿


什么?你说交换两个数?那直接
a = b
b = a
就行了吧。

显然是错的。比如a = 5, b = 3就会导致两个都变成3了。

考虑在现实中交换两张桌子,你肯定会把桌子a移动到某个空地去,把桌子b移动到桌子a原来的地方,把桌子a从空地上移回来吧。
所以,其实我们需要一块空地:
t = a;
a = b;
b = a;

嗯……看起来不错。
那么问题来了:有没有不用任何临时变量的方法?

技巧在于,交换前后,两个数之和是不会变的,而且知道了其中一个数以及两个数之和,就能得到另一个数。
所以:
sum = a + b;
b = sum - a;
a = sum - b;
看起来还是用了一个临时变量,没关系,我们发现sum和a似乎可以合并成一个:
a += b;
b -= a;
a -= b;
于是搞定!

但是要是加起来爆int了真的没问题么?事实上没问题的,因为2147483647 + 1 = -2147483648,而-2147483648 + 1 = 2147483647,尽管很匪夷所思,但int还是爆了爆就能爆回来的,所以不用担心。

观察上面这份代码,我们可以发现其实跟+、-无关,只跟他们可交换且互为逆运算有关对吧!
计算机的位运算中,异或是个特别的运算。它的特别之处在于,它自己是自己的逆运算,也就是说:
a ^ b = b ^ a
abab ^ b = a
所以交换两个数其实还能这么写:
a ^= b;
b ^= a;
a ^= b;

看起来对称极了。

~~~欢迎投稿



作者: 创世菌    时间: 2018-2-27 13:50
位运算会更快!
作者: 创世菌    时间: 2018-2-27 13:57
本帖最后由 创世菌 于 2018-3-3 09:34 编辑

投一稿!(不太完善)
http://www.ahalei.com/thread-10278-1-1.html
http://www.ahalei.com/thread-10534-1-1.html


作者: 逸飞扬_VbCNT    时间: 2018-2-28 12:45
【小伙伴们的算法】?
作者: pulvis    时间: 2018-2-28 12:53
来一个沙发                 
作者: 十甫    时间: 2018-3-14 16:55
cin>>a>>b;
cout<<b<<a;
完美解决
作者: Dr.Clef    时间: 2018-10-30 02:04
C++中有个函数叫swap。。。
swap(a, b)

作者: chen_zhe    时间: 2018-11-10 23:12
如果是黑盒测试,可以倒过来输出




欢迎光临 啊哈磊_编程从这里起步 (https://bbs.codeaha.com/) Powered by Discuz! X3.2