3

有谁知道在编译时计算C中至少两个数字的 LCM（最小公倍数）和/或 GCD（最大公分母）的机制（不是 C++，我知道那里有模板魔术）？

我通常使用GCC，并记得它可以在所有输入已知的编译时计算某些值（例如：sin、cos 等）。

我正在寻找如何在GCC中执行此操作（最好以其他编译器可以处理的方式），并希望相同的机制可以在 Visual Studio 中工作。

4

4 回答 4

6

毕竟我想通了...

#define GCD(a,b) ((a>=b)*GCD_1(a,b)+(a<b)*GCD_1(b,a))
#define GCD_1(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_2((b), (a)%((b)+!(b))))
#define GCD_2(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_3((b), (a)%((b)+!(b))))
#define GCD_3(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_4((b), (a)%((b)+!(b))))
#define GCD_4(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_5((b), (a)%((b)+!(b))))
#define GCD_5(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_6((b), (a)%((b)+!(b))))
#define GCD_6(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_7((b), (a)%((b)+!(b))))
#define GCD_7(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_8((b), (a)%((b)+!(b))))
#define GCD_8(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_last((b), (a)%((b)+!(b))))
#define GCD_last(a,b) (a)

#define LCM(a,b) (((a)*(b))/GCD(a,b))


int main()
{
    printf("%d, %d\n", GCD(21,6), LCM(21,6));
    return 0;
}

请注意，根据您的整数有多大，您可能需要包括更多的中间步骤（即 GCD_9、GCD_10 等...）。

我希望这有帮助！

于 2008-09-16T20:37:03.450 回答
2

部分基于凯文的回答，这里有一个宏序列，它对常量值有编译时错误，否则有运行时错误。

如果不能选择失败，它也可以配置为引入非编译时函数。

#define GCD(a,b) ( ((a) > (b)) ? ( GCD_1((a), (b)) ) : ( GCD_1((b), (a)) ) )

#define GCD_1(a,b) ( ((b) == 0) ? (a) : GCD_2((b), (a) % (b) ) )
#define GCD_2(a,b) ( ((b) == 0) ? (a) : GCD_3((b), (a) % (b) ) )
#define GCD_3(a,b) ( ((b) == 0) ? (a) : GCD_4((b), (a) % (b) ) )
#define GCD_4(a,b) ( ((b) == 0) ? (a) : GCD_5((b), (a) % (b) ) )
#define GCD_5(a,b) ( ((b) == 0) ? (a) : GCD_6((b), (a) % (b) ) )
#define GCD_6(a,b) ( ((b) == 0) ? (a) : GCD_7((b), (a) % (b) ) )
#define GCD_7(a,b) ( ((b) == 0) ? (a) : GCD_8((b), (a) % (b) ) )
#define GCD_8(a,b) ( ((b) == 0) ? (a) : GCD_9((b), (a) % (b) ) )
#define GCD_9(a,b) (assert(0),-1)

请注意将其扩展得太大，即使它会提前终止，因为编译器必须在评估之前完全插入所有内容。

于 2008-09-17T01:01:38.413 回答
1

我意识到您只对 C 实现感兴趣，但我想我还是会对 C++ 和模板元编程发表评论。我不完全相信在 C++ 中这是可能的，因为您需要明确定义的初始条件才能终止递归扩展。

template<int A, int B>
struct GCD {
    enum { value = GCD<B, A % B>::value };
};

/*
Because GCD terminates when only one of the values is zero it is impossible to define a base condition to satisfy all GCD<N, 0>::value conditions
*/
template<>
struct GCD<A, 0> { // This is obviously not legal
    enum { value = A };
};

int main(void)
{
    ::printf("gcd(%d, %d) = %d", 7, 35, GCD<7, 35>::value);
}

这可能在 C++0x 中是可能的，但不是 %100 确定的。

于 2008-09-16T22:04:14.050 回答
0 
 int gcd(int n1,int n2){
       while(n1!=n2){
        if(n1 > n2) n1 -= n2;
        else n2 -= n1;
    }
    return n1;
}
int lcm(int n1, int n2){
    int total =n1*n2;
    return total/gcd(n1,n2);
}
于 2021-11-20T15:22:53.477 回答