短短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大
- }
也就等同于正常的循环实现辗转相除大法
最新评论