随笔 - 62  文章 - 190  trackbacks - 0
<2008年11月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

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

常用链接

留言簿(2)

随笔分类(64)

随笔档案(62)

文章分类(11)

文章档案(11)

相册

BlOoD

FriEnds

搞起的人们

搜索

  •  

积分与排名

  • 积分 - 31539
  • 排名 - 81

最新评论

阅读排行榜

评论排行榜

最快的最大公约数的算法
    全部用移位和++，--实现，没有费时的%……
// 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 阅读(543) 评论(11)  编辑 收藏 引用 所属分类: 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
实际上 展转相除要比相减快  回复  更多评论
  

标题  
姓名  
主页
验证码 *
内容(提交失败后,可以通过“恢复上次提交”恢复刚刚提交的内容)  
  登录  使用高级评论  新用户注册  返回页首  恢复上次提交      
[使用Ctrl+Enter键可以直接提交]
相关链接:
网站导航:
Copyright ©2008 Asp Powered by: 博客园 模板提供：沪江博客