隨筆 - 62 文章 - 257 trackbacks - 0

2025年8月

日

一

二

三

四

五

六

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

常用鏈接

留言簿(7)

隨筆分類(lèi)(64)

隨筆檔案(62)

文章分類(lèi)(11)

文章檔案(11)

相冊(cè)

BlOoD

Sammy's Blog

FriEnds

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

搞起的人們

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

搜索

積分與排名

積分 - 118642
排名 - 215

閱讀排行榜

評(píng)論排行榜

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

??? 全部用移位和++，--實(shí)現(xiàn)，沒(méi)有費(fèi)時(shí)的%……

// 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) 評(píng)論(15) 編輯收藏引用所屬分類(lèi): Ar!thmEt!c

FeedBack:

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

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

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

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

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

@Asp
我菜鳥(niǎo)一只^_^ 回復(fù) 更多評(píng)論

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

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

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

。。。。沒(méi)看到用過(guò)阿？。。。回復(fù) 更多評(píng)論

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

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

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

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

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

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

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

這個(gè)就是Stein算法。。。回復(fù) 更多評(píng)論

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

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

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

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

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

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

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

............................ 回復(fù) 更多評(píng)論

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

................. 回復(fù) 更多評(píng)論

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

........... 回復(fù) 更多評(píng)論

刷新評(píng)論列表

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

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

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

常用鏈接

留言簿(7)

隨筆分類(lèi)(64)

隨筆檔案(62)

文章分類(lèi)(11)

文章檔案(11)

相冊(cè)

BlOoD

FriEnds

搞起的人們

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜