欧几里德最大公约数算法的实现

C 代码实现

#include 

int gcd(int a, int b)
{   if ( b == 0 ) return(a);
    else return ( gcd(b, a % b) );
}

int main()
{   printf("gcd(%d,%d)=%d\n",2979, 1265, gcd(2970,1265));
    return 0;
}

产生的汇编代码

        .file   "gcd.c"
        .text
        .globl  gcd
        .type   gcd, @function
gcd:
.LFB0:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        subq    $16, %rsp
        movl    %edi, -4(%rbp)
        movl    %esi, -8(%rbp)
        cmpl    $0, -8(%rbp)
        jne     .L2
        movl    -4(%rbp), %eax
        jmp     .L3
.L2:
        movl    -4(%rbp), %eax
        movl    %eax, %edx
        sarl    $31, %edx
        idivl   -8(%rbp)
        movl    -8(%rbp), %eax
        movl    %edx, %esi
        movl    %eax, %edi
        call    gcd
.L3:
        leave
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:
        .size   gcd, .-gcd
        .section        .rodata
.LC0:
        .string "gcd(%d,%d)=%d\n"
        .text
        .globl  main
        .type   main, @function
main:
.LFB1:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        movl    $1265, %esi
        movl    $2970, %edi
        call    gcd
        movl    %eax, %ecx
        movl    $1265, %edx
        movl    $2979, %esi
        movl    $.LC0, %edi
        movl    $0, %eax
        call    printf
        movl    $0, %eax
        popq    %rbp
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE1:
        .size   main, .-main
        .ident  "GCC: (GNU) 4.7.2 20121109 (Red Hat 4.7.2-8)"
        .section        .note.GNU-stack,"",@progbits

自我挑战

• 在你自己的机器上下载GCD C源程序，并编译运行。
• 修改代码来计算用户任意输入的两个整数的最大公约数。

| 返回互动演示 |