随笔 - 62  文章 - 257  trackbacks - 0
<2006年10月>
日一二三四五六
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

I Love Programming & Music.... CS Became CSed....

常用链接

留言簿(7)

随笔分类(64)

随笔档案(62)

文章分类(11)

文章档案(11)

相册

BlOoD

FriEnds

搞起的人们

搜索

  •  

积分与排名

  • 积分 - 114717
  • 排名 - 216

最新评论

阅读排行榜

评论排行榜

最快的最大公约数的算法
    全部用移位和++，--实现，没有费时的%……
// Source Code
 // common divisor最大公约数
inline unsigned  int  cd(unsigned  int  x,unsigned  int  y)   
 
 {   
    unsigned  int  i,j,t;   
     if (x == 0 )  return  y;   
     if (y == 0 )  return  x;   
     for (i = 0 ; 0 == (x & 1 );x >>= 1 , ++ i);   
     for (j = 0 ; 0 == (y & 1 );y >>= 1 , ++ j);   
     if (j < i) i = j;   
     for (;;)   
     {   
         if (x < y) t = y,y = x,x = t;   
         if ( 0 == (x -= y))  return  y << i;   
         for (; 0 == (x & 1 );x >>= 1 );   
    }    
}  
posted on 2006-10-22 19:18 Asp 阅读(2134) 评论(15)  编辑 收藏 引用 所属分类: Ar!thmEt!c

FeedBack:
# re: 最快的最大公约数的算法 2006-10-23 00:17 beyonlin
真的是最快吗？
你个人看法吧？  回复  更多评论
  
# re: 最快的最大公约数的算法 2006-10-23 10:12 Asp
虽然不知道是不是公认，不过很多地方都是这么说的……
比辗转相除来说这个算法对于unsigned int类型优势并不明显，但是对于unsigned __int64和其他大整数类来说，速度确实快很多……
如果你有更好的算法记得告诉我啊……我的邮箱是jimmy1006@163.com  回复  更多评论
  
# re: 最快的最大公约数的算法 2006-10-24 00:30 beyonlin
@Asp
我菜鸟一只^_^  回复  更多评论
  
# re: 最快的最大公约数的算法 2006-10-24 12:41 Asp
我比你还菜些…… 嘿嘿……  回复  更多评论
  
# re: 最快的最大公约数的算法 2006-11-02 18:48 Optimistic
。。。。没看到用过阿？。。。  回复  更多评论
  
# re: 最快的最大公约数的算法 2006-11-03 00:19 Asp
确实很少用……  回复  更多评论
  
# re: 最快的最大公约数的算法 2006-11-05 11:01 追月土狗
不错的思路。采用位移运算确实比%的除法运算快很多。顶！  回复  更多评论
  
# re: 最快的最大公约数的算法 2006-11-05 12:09 Asp
快是确实快些…… 好多高手用位运算都好强，我也好想练啊…… 只是不知道怎么练……  回复  更多评论
  
# re: 最快的最大公约数的算法 2007-09-20 10:02 drizzlecrj
这个就是Stein算法。。。  回复  更多评论
  
# re: 最快的最大公约数的算法 2008-07-26 10:05 zhzhzoo
这是中国古代的更相减损法  回复  更多评论
  
# re: 最快的最大公约数的算法 2008-11-05 17:14 hzhua
实际上 展转相除要比相减快  回复  更多评论
  
# re: 最快的最大公约数的算法 2009-11-01 21:48 zzdr
有意思么  回复  更多评论
  
# re: 最快的最大公约数的算法 2011-07-02 10:56 dnf
............................  回复  更多评论
  
# re: 最快的最大公约数的算法 2011-07-02 10:56 dnf
.................  回复  更多评论
  
# re: 最快的最大公约数的算法 2011-07-02 10:56 dnf
...........  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


Copyright ©2024 Asp Powered by: 博客园 模板提供：沪江博客