算法数据结构奇技淫巧3:交换两个数

2019年6月10日10:18:08 发表评论 91 views

3、交换两个数

交换两个数相信很多人天天写过,我也相信你每次都会使用一个额外来变量来辅助交换,例如,我们要交换 x 与 y 值,传统代码如下:

int tmp = x;
x = y;
y = tmp;

这样写有问题吗?没问题,通俗易懂,万一哪天有人要为难你,不允许你使用额外的辅助变量来完成交换呢?你还别说,有人面试确实被问过,这个时候,位运算装逼大法就来了。代码如下:

x = x ^ y   // (1)
y = x ^ y   // (2)
x = x ^ y   // (3)

我靠,牛逼!三个都是 x ^ y,就莫名交换成功了。在此我解释下吧,我们知道,两个相同的数异或之后结果会等于 0,即 n ^ n = 0。并且任何数与 0 异或等于它本身,即 n ^ 0 = n。所以,解释如下:

把(1)中的 x 带入 (2)中的 x,有

y = x^y = (x^y)^y = x^(y^y) = x^0 = x。 x 的值成功赋给了 y。

对于(3),推导如下:

x = x^y = (x^y)^x = (x^x)^y = 0^y = y。

这里解释一下,异或运算支持运算的交换律和结合律哦。

怎么样?有木觉得很多牛逼?

作者:帅地
来源:知乎

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: