花式求GCD
花式求GCD
今天学校实验室纳新群有同学提到了a^=b^=a^=b
交换两个数的操作,我突然想到之前在知乎看到通过异或实现gcd的方法,一番翻找后没啥结果,便去问了下认识的oi大佬有没有一行求gcd的算法。
大佬很快给出了一个函数int gcd(int a,int b){return y?gcd(y,x%y):x;}
真的就是一行,完整的代码就是下面这个
1 |
|
但是我一像不对啊,我的异或呢?我又问了一下,大佬给了我一个截图
就是这个神奇的写法
这段代码的实现方式是,使用异或运算符(^)和取模运算符(%)来交换变量a和b的值。具体来说,代码中的while循环会一直执行,直到b的值为0为止。在每次循环中,代码会先将a对b取模,然后将结果赋值给a,接着将b对a取模,然后将结果赋值给b,最后使用异或运算符交换a和b的值。这样,当循环结束时,a和b的值就被成功地交换了。(来自copilot chat)
1 |
|
花式求GCD
https://studyinglover.com/2023/08/02/花式求GCD/