先上代码

$a = 123;
$b = 45;

$a = $a ^ $b;
$b = $a ^ $b;
$a = $a ^ $b;

echo $a, '  ', $b, PHP_EOL;

就酱紫,两个数字相同也是可以成功交换的。

先说两个事实

  1. 两个相同的数异或总是 0
  2. 任意数字与 0 做异或值不变

交换流程

  1. $a = $a ^ $b
  2. $b = $a ^ $b
    要注意此时等号右边的 $a 已经等于 $a ^ $b
    所以上的面等式可以转化为 $b = $a ^ $b ^ $b = $a
  3. $a = $a ^ $b
    此时 $a 等于 $a ^ $b $b 已经等于 $a 的初始值
    所以上的面等式可以转化为 $a = $a ^ $b ^ $a = $b

成功交换两个数

理解上述流程可以类比下列交换 a b 值的方式
a = a + b
b = a - b
a = a - b

网上有几个帖子没说清楚,里面提到不能交换两个相同的数,注意这个说法是错误的!
仅仅是不能交换指向同一个地址空间的两个数

如果 a b 两个变量指向同一个地址空间这样做是不行的

$c = 45;

$a = &$c;
$b = &$c;

$a = $a^$b;
$b = $a^$b;
$a = $a^$b;

echo $a, '  ', $b, PHP_EOL;

相当于每次都是两个相同的数字做异或,最终结果都是 0

这只是一种解题思路,看起来很巧妙,但是并不一定快,通常我们都是采用中间变量的形式来交换。
现在的编译器很聪明,对我们写的代码做了很多优化,所以不要以为异或的方式交换更快。
具体论证可以看这里

标签: 位运算

添加新评论