呵呵，出道题大家做，看谁的方法好。

tarkey

我的解决方案：
int GetMaxFactor(int a, int b)
{
    if ((a %=  b) == 0) return b;
    else return GetMaxFactor(b, a);
}

tarkey

lobo: Re:呵呵，出道题大家做，看谁的方法好。

其实关键就是a、b的互换，这一次是a%b那下一次一定是b%a，那有什么办法可以减去这个互换的开销呢？其实3楼的...

你的方法有问题，用：
905969664, 838860800
试不出来，但是答案应该是：
33554432

你自己去试试。。。
我一会帖出各个方法的时间消耗。。。

tarkey

用减法的那个方法，执行10000次时间：0.000944533453
我的方法，执行10000次时间：        0.000955428693
位运算的方法，执行10000次时间：    0.001065219183

其他的方法，准确性都有问题。

nicememory

inline assembler in VC++
int gcd(int a,int b)
{
__asm{
             mov eax,a
             mov ebx,b
    nzloop:
             xor edx,edx
             div ebx  
             test edx,edx
             je zexit
             push edx
             pop eax
             xchg eax,ebx
             jmp nzloop
     zexit:        
              mov a,ebx
        }
     return a;  
}

tarkey

运行时间：0.000857092172
：） 这个速度快。。

kaiz

真是牛人哪………………佩服的五体投地

不知道楼主是如何测量时间的？

tarkey

static LARGE_INTEGER _tstart, _tend;
static LARGE_INTEGER freq;

void tstart(void)
{
    static int first = 1;

    if(first) {
        QueryPerformanceFrequency(&freq);
        first = 0;
    }
    QueryPerformanceCounter(&_tstart);
}
void tend(void)
{
    QueryPerformanceCounter(&_tend);
}

double tval()
{
    return ((double)_tend.QuadPart -
                (double)_tstart.QuadPart)/((double)freq.QuadPart);
}

然后在你的程序要测时间的地方：
tstart();
//这里是你的代码;
tend();
然后随便找个地方打印tval()就是了。

lobo

不好意思，我写错了。应该是
int gcd(int a,int b)
{
       while((a %= b) && (b %= a)) ;
        return a | b;
}
你再测试一下。

另外，你是用随机数测试还是同一个数测试10000次？如果是同一个数，那是不足以说明问题的，比如42，24用那个减法的肯定快，1000, 998就未必了。

tarkey

我用的是两个2^20以上的随机数测试的

Deen

Nicememory 你好。

PUSH edx
POP   eax

为什么不写成 MOV eax, edx 呢 ？