摘录自某位神仙的代码
短短 5 行的 gcd, 核心只有两行
- in int gcd(int a,int b)
- {
- while(b^=a^=b^=a%=b);
- return a;
- }
我们知道 %= 优先级高于位运算 ^=
因此 while 中的语句可拆分为:
a%=b; b^=a^=b^=a;
而同优先级的运算是从右往左的, 又可以拆成:
- a%=b;
- b^=a;
- a^=b;
- b^=a;
即
a%=b;
swap(a,b);
因为 b^=... 等缩写的运算会返回运算后的 b 值, 所有 while 中的一坨返回的是 b 的值, 那么执行条件就是 b!=0
即
- while(b!=0)
- {
- a%=b; // 运算后 a<b
- swap(a,b); // 要保证 a 中的值始终比 b 大
- }
也就等同于正常的循环实现辗转相除大法
来源: http://www.bubuko.com/infodetail-2936053.html