尽管使用了 unsigned int 和模运算，但 c++ 整数溢出

Question

        int orders=1000000000;
        int mod=pow(10,9)+7;
        unsigned int total=4294967295; 
        total=(orders*(orders+1))%mod;
        total/=2;
        return total;

expected Answer= 21

但是得到

runtime error: signed integer overflow: 1000000000 * 1000000001 cannot be represented in type 'int'

我也试过了

        int orders=1000000000;
        int mod=pow(10,9)+7;
        long long total=0LL; 
        total=(long long)(orders*(orders+1))%mod;
        total/=2;
        return total;

同样的错误

//使用最新的 C++ 17 标准用 clang 11 编译。

请问这是为什么？我想也许 long long 被截断为 int 因此 0LL，但是还是没有解决问题。

在其他编译器上尝试时，获取输出

for 1st code:

-243309312

for second peice of code:

1904174336

Answer 1

考虑大小为 4 个字节的整数范围

-2,147,483,648 to 2,147,483,647

Unsigned int max  4,294,967,295

现在声明

total=(orders*(orders+1))%mod;

将尝试将 orders*(orders+1) 放入带符号且最大值为“2,147,483,647”的 int 类型中，因为 orders 是 int 类型。

所以乘法结果

1000000001000000000

它不在 int 的范围内。因此你这里有溢出问题。

为了更好的可见度运行这个

int orders=1000000000;
        int mod=pow(10,9)+7;
        unsigned int total=4294967295; 
        total=(orders*(orders+1))%mod;
        total/=2;
        cout<< "result= "<<total<<"\n"; 
        int val = (orders*(orders+1));
        std::cout<<"val = "<<val;
        unsigned int t=(-486618624)%mod;
        std::cout<<"\nresult 2 = "<<t/2;

Answer 2

基本上问题是乘法后整数溢出。

要克服这个问题，您必须使用两种解决方案之一来处理主题。

使用可以容纳如此大的结果的整数类型，例如：unsigned long long int
使用能够在没有整数溢出的情况下进行计算的算法（为此我找不到好的和简单的英文文档）

使用第二种方法：

constexpr unsigned mutiplyModulo(unsigned a, unsigned b, unsigned n)
{
    unsigned m = 1, w = 1;

    while (m) {
        if (b & m)
            w = (w + a) % n;
        a = (a << 1) % n;
        m <<= 1;
    }
    return w;
}

constexpr unsigned int intpow(unsigned int x, unsigned int n)
{
    unsigned int r = 1;
    while (n) {
        if (n & 1)
            r *= x;
        x *= x;
        n /= 2;
    }
    return r;
}

unsigned int foo(unsigned int orders)
{
    constexpr auto mod = intpow(10u, 9u) + 7u;
    unsigned int total = mutiplyModulo(orders, orders + 1, mod);
    total /= 2;
    return total;
}

https://godbolt.org/z/ePW7WxcTe

尽管使用了 unsigned int 和模运算，但 c++ 整数溢出

c++ Integer overflow in spite of using unsigned int and modulo operations

c++

integer-overflow

c++11