3、交换两个数
交换两个数相信很多人天天写过,我也相信你每次都会使用一个额外来变量来辅助交换,例如,我们要交换 x 与 y 值,传统代码如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13539.html
int tmp = x;
x = y;
y = tmp;
这样写有问题吗?没问题,通俗易懂,万一哪天有人要为难你,不允许你使用额外的辅助变量来完成交换呢?你还别说,有人面试确实被问过,这个时候,位运算装逼大法就来了。代码如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13539.html
x = x ^ y // (1)
y = x ^ y // (2)
x = x ^ y // (3)
我靠,牛逼!三个都是 x ^ y,就莫名交换成功了。在此我解释下吧,我们知道,两个相同的数异或之后结果会等于 0,即 n ^ n = 0。并且任何数与 0 异或等于它本身,即 n ^ 0 = n。所以,解释如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13539.html
把(1)中的 x 带入 (2)中的 x,有文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13539.html
y = x^y = (x^y)^y = x^(y^y) = x^0 = x。 x 的值成功赋给了 y。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13539.html
对于(3),推导如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13539.html
x = x^y = (x^y)^x = (x^x)^y = 0^y = y。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13539.html
这里解释一下,异或运算支持运算的交换律和结合律哦。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13539.html
怎么样?有木觉得很多牛逼?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13539.html
作者:帅地
来源:知乎文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13539.html