二進(jìn)制空間
See, I'm living...

隨筆 - 62 文章 - 257 trackbacks - 0

2025年11月

>

日

一

二

三

四

五

六

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

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

常用鏈接

留言簿(7)

隨筆分類(64)

隨筆檔案(62)

文章分類(11)

文章檔案(11)

相冊(cè)

BlOoD

Sammy's Blog

FriEnds

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

搞起的人們

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

搜索

積分與排名

積分 - 120257
排名 - 214

閱讀排行榜

評(píng)論排行榜

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

??? 全部用移位和++，--實(shí)現(xiàn)，沒有費(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 閱讀(2194) 評(píng)論(15) 編輯收藏引用所屬分類: 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類型優(yōu)勢(shì)并不明顯，但是對(duì)于unsigned __int64和其他大整數(shù)類來(lái)說(shuō)，速度確實(shí)快很多……
如果你有更好的算法記得告訴我啊……我的郵箱是jimmy1006@163.com 回復(fù) 更多評(píng)論

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

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

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

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

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

。。。。沒看到用過(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è)用戶登錄后才能發(fā)表評(píng)論。


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

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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

常用鏈接

留言簿(7)

隨筆分類(64)

隨筆檔案(62)

文章分類(11)

文章檔案(11)

相冊(cè)

BlOoD

FriEnds

搞起的人們

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜