玄学辗转相除法求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. }

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

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址