由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;
看起来对称极了。
~~~欢迎投稿
|