CODEWITHSUNDEEP
c++c++11integer-overflow
rushikesh chaskar
rushikesh chaskar

Reputation: 792

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

        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

BUT getting

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

I also tried

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

Same error

//Compiled with clang 11 using the latest C++ 17 standard.

May I know why this is happening? I thought maybe long long is getting truncated to int hence the 0LL, But still that didn't solve the issue.

When tried on other compiler, getting output

for 1st code:

-243309312

for second peice of code:

1904174336

Upvotes: 0

Views: 701

Answers (2)

Marek R
Marek R

Reputation: 37512

Basically problem is you have integer overflow just after multiplication.

To overcome this problem you have to approach topic using one of two solutions.

  • use integer type which can hold a result of such magnitude, for example: unsigned long long int
  • use algorithm which is able to do that calculation without integer overflow (for that I can't find good and simple document in English)

Using second approach:

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

Upvotes: 1

User
User

Reputation: 610

integer range considering size to be 4 bytes

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


Unsigned int max  4,294,967,295

Now the statement

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

will try to put orders*(orders+1) into type int which is signed and has max value of "2,147,483,647" as orders is type of int.

so the multiplication results

1000000001000000000

and it's not in range of int .hence you have overflow issue here .

For better visibility run this

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;

Upvotes: 1

Related Questions