C 乘方求幂的实现

Question

我试图在 C 中实现“平方取幂”算法，但我的程序有一个奇怪的行为。首先，这是一个小代码片段:

long long fast_power_1(long long base, long long power){
    long long result = 1;
    while (power > 0)
    {
        if (power % 2 == 0)
        {
            power = power / 2;
            base = base * base;
        }
        else
        {
            power = power - 1;
            result = (result*base);
            power = power / 2;
            base = (base * base);
        }
    }
return result;}

如果我调用函数:

printf("%d\n",fast_power_1(2,100));

我希望输出类似于 976371285，但结果是 0，我不太明白为什么。

Answer 1

long long 应该使用 %lld 格式说明符打印，否则它是未定义的行为。此外，对于较大的 power 值，此方法已经发生溢出 - 因为 long long 不能容纳 2^100(截至目前 32 或 64 位系统-当它是128 位系统当然可以)。

到目前为止，在您的代码中，如果您提供的指数值不是太大并使用 printf("%lld",..) 那么它会给您一个有效的结果。

也许您想对其进行模块化运算。 (一般要求就此止步 - 比如对一些大质数进行模运算，即 10^9+7 )。