隨筆 - 62 文章 - 257 trackbacks - 0

2006年10月

日

一

二

三

四

五

六

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

常用鏈接

留言簿(7)

隨筆分類(64)

隨筆檔案(62)

文章分類(11)

文章檔案(11)

相冊

BlOoD

Sammy's Blog

FriEnds

木甘—甜
大學(xué)同學(xué)，比較可愛……
若愚's Blog
愛好照相的室友……

搞起的人們

Alpc01's Blog
NUDT校隊牛人……
beyonlin's Blog
fan's Blog
朋友的室友……
Optimistic's Algorithm Blog
學(xué)校里面編程最猛的男人...
Pengkuny
豪's blog

搜索

積分與排名

積分 - 118654
排名 - 215

閱讀排行榜

評論排行榜

最快的最大公約數(shù)的算法

??? 全部用移位和++，--實現(xiàn)，沒有費時的%……

// Source?Code

// common?divisor最大公約數(shù)

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 閱讀(2175) 評論(15) 編輯收藏引用所屬分類: Ar!thmEt!c

FeedBack:

# re: 最快的最大公約數(shù)的算法 2006-10-23 00:17 beyonlin

真的是最快嗎？
你個人看法吧？回復(fù) 更多評論

# re: 最快的最大公約數(shù)的算法 2006-10-23 10:12 Asp

雖然不知道是不是公認(rèn)，不過很多地方都是這么說的……
比輾轉(zhuǎn)相除來說這個算法對于unsigned int類型優(yōu)勢并不明顯，但是對于unsigned __int64和其他大整數(shù)類來說，速度確實快很多……
如果你有更好的算法記得告訴我啊……我的郵箱是jimmy1006@163.com 回復(fù) 更多評論

# re: 最快的最大公約數(shù)的算法 2006-10-24 00:30 beyonlin

@Asp
我菜鳥一只^_^ 回復(fù) 更多評論

# re: 最快的最大公約數(shù)的算法 2006-10-24 12:41 Asp

我比你還菜些…… 嘿嘿…… 回復(fù) 更多評論

# re: 最快的最大公約數(shù)的算法 2006-11-02 18:48 Optimistic

。。。。沒看到用過阿？。。。回復(fù) 更多評論

# re: 最快的最大公約數(shù)的算法 2006-11-03 00:19 Asp

確實很少用…… 回復(fù) 更多評論

# re: 最快的最大公約數(shù)的算法 2006-11-05 11:01 追月土狗

不錯的思路。采用位移運算確實比%的除法運算快很多。頂！回復(fù) 更多評論

# re: 最快的最大公約數(shù)的算法 2006-11-05 12:09 Asp

快是確實快些…… 好多高手用位運算都好強，我也好想練啊…… 只是不知道怎么練…… 回復(fù) 更多評論

# re: 最快的最大公約數(shù)的算法 2007-09-20 10:02 drizzlecrj

這個就是Stein算法。。。回復(fù) 更多評論

# re: 最快的最大公約數(shù)的算法 2008-07-26 10:05 zhzhzoo

這是中國古代的更相減損法回復(fù) 更多評論

# re: 最快的最大公約數(shù)的算法 2008-11-05 17:14 hzhua

實際上展轉(zhuǎn)相除要比相減快回復(fù) 更多評論

# re: 最快的最大公約數(shù)的算法 2009-11-01 21:48 zzdr

有意思么回復(fù) 更多評論

# re: 最快的最大公約數(shù)的算法 2011-07-02 10:56 dnf

............................ 回復(fù) 更多評論

# re: 最快的最大公約數(shù)的算法 2011-07-02 10:56 dnf

................. 回復(fù) 更多評論

# re: 最快的最大公約數(shù)的算法 2011-07-02 10:56 dnf

........... 回復(fù) 更多評論

刷新評論列表

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 自己寫的一些常見算法的實現(xiàn) 最快的最大公約數(shù)的算法 BM匹配算法

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

常用鏈接

留言簿(7)

隨筆分類(64)

隨筆檔案(62)

文章分類(11)

文章檔案(11)

相冊

BlOoD

FriEnds

搞起的人們

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜