求两个数的最大公约数C语言，Stein算法，并将代码写好解释

以下是求两个数的最大公约数C语言，Stein算法的代码及解释：

#include <stdio.h>

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

    int k = 0;
    while ((a & 1) == 0 && (b & 1) == 0) {
        a >>= 1;
        b >>= 1;
        k++;
    }

    while ((a & 1) == 0) {
        a >>= 1;
    }

    while (b != 0) {
        while ((b & 1) == 0) {
            b >>= 1;
        }

        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }

        b -= a;
    }

    return a << k;
}

int main() {
    int a, b;
    printf("请输入两个整数：");
    scanf("%d %d", &a, &b);
    printf("它们的最大公约数是：%d\n", gcd(a, b));
    return 0;
}

解释：

这是使用 Stein 算法求两个数的最大公约数的 C 语言代码。Stein 算法是一种比较高效的算法，它可以在不使用除法和模运算的情况下求出两个数的最大公约数。

首先，我们需要判断两个数是否为 0，如果其中一个数为 0，那么另一个数就是它们的最大公约数。

然后，我们需要将两个数都除以 2 直到它们都变成奇数。这样做的原因是，如果两个数都是偶数，那么它们的最大公约数也一定是偶数，因此我们可以将它们都除以 2，直到它们都变成奇数。

接下来，我们使用辗转相减法来求两个数的最大公约数。具体来说，我们先将其中较小的数减去较大的数，然后不断重复这个过程，直到其中一个数变成 0。这样做的原因是，如果两个数的最大公约数是 d，那么它们一定可以表示成 d * x 和 d * y 的形式，其中 x 和 y 都是整数。因此，我们可以将其中较大的数减去较小的数，直到它们相等，然后再将它们中的一个数减去另一个数，直到其中一个数变成 0。这样做的结果是，我们得到了两个数的最大公约数的两倍，因此最后需要将它乘以 2 的 k 次方，其中 k 是我们在一开始将两个数都除以 2 的次数。

最后，我们可以将这个算法封装成一个函数，然后在主函数中调用它来求两个数的最大公约数。