玄学辗转相除法求GCD

  • A+
所属分类:代码笔记 信息技术

短短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. }  

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

xcc

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:2   其中:访客  2   博主  0

    • avatar Zerosking 1

      压成两行不是更妙吗/滑稽

        • xcc xcc 2

          @Zerosking 极限压行int gcd(int a,int b){while(b^=a^=b^=a%=b);return a;}