我的二进制供电功能有问题。包含结果的变量在执行乘法时溢出并给出错误的结果。当源值大于 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;
}
最佳答案
表达式a*a
需要的空间是源大小的两倍。在您的场景 4,312,952,827 > 2^32-1
中,因此您超出了 unsigned long long
的范围。
实现模幂二进制梯形的经验法则是能够在至少是参数数据类型两倍的范围上执行算术,因此在您的情况下它是 128 位。
关于c - 二进制供电给了我错误的结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37556482/