隨筆 - 62 文章 - 257 trackbacks - 0

2025年6月

日

一

二

三

四

五

六

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

常用鏈接

留言簿(7)

隨筆分類(64)

隨筆檔案(62)

文章分類(11)

文章檔案(11)

相冊

BlOoD

Sammy's Blog

FriEnds

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

搞起的人們

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

搜索

積分與排名

積分 - 117685
排名 - 214

閱讀排行榜

評論排行榜

最快的最大公約數的算法

??? 全部用移位和++，--實現，沒有費時的%……

// 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 閱讀(2160) 評論(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

........... 回復更多評論

刷新評論列表

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

相關文章: 自己寫的一些常見算法的實現最快的最大公約數的算法 BM匹配算法

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

常用鏈接

留言簿(7)

隨筆分類(64)

隨筆檔案(62)

文章分類(11)

文章檔案(11)

相冊

BlOoD

FriEnds

搞起的人們

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜