c - 二进制供电给了我错误的结果

Question

我的二进制供电功能有问题。包含结果的变量在执行乘法时溢出并给出错误的结果。当源值大于 4,312,952,827 时会发生这种情况。那么我该如何解决这个问题呢？这是我的函数的代码。

unsigned long long binpow(unsigned long long a, unsigned long long n, unsigned long long m)
{
    unsigned long long res;
    res=1;
    while (n)
    {
        if (n & 1)
        {
            res=(res*a)%m;
            n--;
        }
        a=(a*a)%m;
        n >>= 1;
    }
    return res;
}

Answer 1

表达式a*a 需要的空间是源大小的两倍。在您的场景 4,312,952,827 > 2^32-1 中，因此您超出了 unsigned long long 的范围。

实现模幂二进制梯形的经验法则是能够在至少是参数数据类型两倍的范围上执行算术，因此在您的情况下它是 128 位。