花式求GCD - plus studio

花式求GCD

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

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

#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)

#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;
}