玄学辗转相除法求GCD

短短5行的gcd, 核心只有两行

1. in int gcd(int a,int b)
2. {
3.     while(b^=a^=b^=a%=b);
4.     return a;
5. }

我们知道%=优先级高于位运算^=
因此while中的语句可拆分为:

1. a%=b;
2. b^=a^=b^=a;

而同优先级的运算是从右往左的, 又可以拆成:

1. a%=b;
2. b^=a;
3. a^=b;
4. b^=a;

即

1. a%=b;
2. swap(a,b);

因为b^=…等缩写的运算会返回运算后的b值, 所有while中的一坨返回的是b的值, 那么执行条件就是b!=0

即

1. while(b!=0)
2. {
3.     a%=b; //运算后a<b
4.     swap(a,b); //要保证a中的值始终比b大
5. }

也就等同于正常的循环实现辗转相除大法