花式求GCD

花式求GCD

今天学校实验室纳新群有同学提到了a^=b^=a^=b​ 交换两个数的操作,我突然想到之前在知乎看到通过异或实现gcd的方法,一番翻找后没啥结果,便去问了下认识的oi大佬有没有一行求gcd的算法。

大佬很快给出了一个函数int gcd(int a,int b){return y?gcd(y,x%y):x;} 真的就是一行,完整的代码就是下面这个

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
int main(){
int a,b;
a=10;
b=20;
a = gcd(a,b);
cout<<a<<endl;
return 0;
}

但是我一像不对啊,我的异或呢?我又问了一下,大佬给了我一个截图

就是这个神奇的写法

这段代码的实现方式是,使用异或运算符(^)和取模运算符(%)来交换变量a和b的值。具体来说,代码中的while循环会一直执行,直到b的值为0为止。在每次循环中,代码会先将a对b取模,然后将结果赋值给a,接着将b对a取模,然后将结果赋值给b,最后使用异或运算符交换a和b的值。这样,当循环结束时,a和b的值就被成功地交换了。(来自copilot chat)

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b;
a=10;
b=20;
while(b^=a^=b^=a%=b);
cout<<a<<endl;
return 0;
}


花式求GCD
https://studyinglover.com/2023/08/02/花式求GCD/
作者
StudyingLover
发布于
2023年8月2日
许可协议