搜索
查看: 1006|回复: 19

【小伙伴的们的算法】交换a和b

[复制链接]
发表于 2018-2-27 13:49:07 | 显示全部楼层 |阅读模式
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-3-14 16:55:24 | 显示全部楼层
cin>>a>>b;
cout<<b<<a;
完美解决

点评

我们只要交换,不要输出!  发表于 2018-7-17 20:37
这不叫完美!  发表于 2018-7-17 20:37
我们正在谈C  发表于 2018-3-27 21:08
再谈C  发表于 2018-3-27 21:08
发表于 2018-2-28 12:45:16 | 显示全部楼层
【小伙伴们的算法】?

点评

居然没发现。  发表于 2018-2-28 13:39
发表于 2018-2-27 13:50:35 | 显示全部楼层
位运算会更快!

点评

位运算大法好!  发表于 2018-2-28 15:58
好安静诶……  发表于 2018-2-27 21:26
是添柴的……  发表于 2018-2-27 13:59
这个也省内存!  发表于 2018-2-27 13:51
沙发。  发表于 2018-2-27 13:50
发表于 2018-2-27 13:57:11 | 显示全部楼层
本帖最后由 创世菌 于 2018-3-3 09:34 编辑

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

发表于 2018-2-28 12:53:42 | 显示全部楼层
来一个沙发                 

点评

你连地板都算不上……  发表于 2018-2-28 13:40
发表于 2018-10-30 02:04:54 | 显示全部楼层
C++中有个函数叫swap。。。
swap(a, b)

点评

c++大好法  发表于 2018-11-10 23:13
发表于 2018-11-10 23:12:17 | 显示全部楼层
如果是黑盒测试,可以倒过来输出
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

广播台
特别关注
快速回复 返回顶部 返回列表