用XOR(异或)做数值交换

2020年11月23日 / 33次阅读 / Last Modified 2021年2月22日
算法

经常看到别人的代码,用3个XOR异或操作,就完成了数值交换,有点炫酷,本文记录一点关于这个骚操作的思考。

先上代码(C):

void swap(int *a, int *b)
{
    *a ^= *b ^= *a ^= *b;
}

这段代码的执行顺序是从右到左的。先执行 *a ^= *b,然后 *b ^= *a,此时 *a 值已变,执行后 *b == 最初的 *a,最后执行 *a ^= *b,此时 *a == 最初的 *b。

代码写成这样,还是因为编译后执行速度更快!

有人这样解释XOR(异或)操作:a ^ b,从b的角度看,得到的结果是与a不一样的bit位全部为1,一样的bit位全为0,即做了一次bit位探测。如果此时对结果再做一次异或,a^b^b 就会等于 a。

看下面的测试(python):

>>> 1^0^0
1
>>> 1^1^1
1
>>> 0^1^1
0
>>> 0^0^0
0
>>> 12^34^34
12
>>> 123^34^34
123
>>> 23^34^34
23

连续异或两个相同的值,结果回到原值!这就是用异或做交换的数学原理。

不过,上面的swap函数有一个“坑”!

有人说这是坑,我个人觉得应该不算。上面那个swap函数,如果传入的两个地址相同,就不再是swap了,而是清零。也许,本就不应该把同一个int(两个指向同一地址的指针)传入swap函数,逻辑上就有问题。

-- EOF --

本文链接:https://www.pynote.net/archives/2874

留言区

《用XOR(异或)做数值交换》有1条留言

邮箱地址不会被公开。 必填项已用*标注

  • 麦新杰

    Python的数值交换,也是一行代码:

    >>> a = 1
    >>> b = 2
    >>> a,b = b,a
    >>> a
    2
    >>> b
    1
    
     [回复]


前一篇:
后一篇:

More


©Copyright 麦新杰 Since 2019 Python笔记

go to top