随笔 - 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

搞起的人们

搜索

  •  

积分与排名

  • 积分 - 111534
  • 排名 - 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 阅读(2107) 评论(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   知识库   博问   管理