CODEWITHSUNDEEP
c++numbersbit-manipulation
Harini Sj
Harini Sj

Reputation: 183

Runtime Error : Integer Overflow for Complement Number Problem

I have 3 ways of complementing a given binary number. The 1st & 3rd methods do not get any Integer Overflow Error. Can you please explain why the 2nd method gets this run time error? Here's the code :

 int findComplement1(int num) {
        if(num==0)
            return 1;

        int n=num;
        int bit=1;
        while(n>0)
        {
         num=num^bit;
         n/=2;
         bit=bit<<1;
        }
        return num;
    }

//Got Integer Overflow
int findComplement2(int num)
{
    int n = floor(log2(num)+1);;
    int num_with_all_ones =(int) (1<<n)-1;
    return (num_with_all_ones^num);
}

int findComplement3(int num)
{
    if(num==0)
        return 1;
    int result=0;
    int power=1;
    while(num>0)
    {
        int pop=num%2;
        int c=(num%2)^1;
        result+=c*power;
        power=power<<1;
        num=num>>1;
    }
    return result;
}

This was the error message : Runtime Error Message: Line 7: Char 44: runtime error: signed integer overflow: -2147483648 - 1 cannot be represented in type 'int' (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:16:44

Last executed input: 2147483647

Upvotes: 2

Views: 868

Answers (1)

T Law
T Law

Reputation: 111

TLDR: This is a two's complement arithmetical issue of underflow.

Your error rightly shows that "-2147483648 - 1 cannot be represented in type 'int'". A little background on the integer type might be helpful.

The integer type is a four-byte (32 bit) representation of mathematical integers. Thus it should be able to represent 2^32 -1 positive integers. However, it quickly became apparent that negative integers also need to be represented. The solution was to use the most significant bit (MSB: the bit furthest to the left in big endian ordering) as a flag to determine whether an integer will be interpreted as positive or negative. Having the MSB set to 1 alerts the computer that the 31 bits after represent a negative integer, and to 0, a positive integer. Very basically, this is called two's complement, although a quick online search will explain it more clearly and in detail. As a result the range of the integer type is [-2,147,483,648 to 2,147,483,647] where -2,147,483,648 is represented in binary as 0b10000000000000000000000000000000 and 2,147,483,647 as 0b01111111111111111111111111111111. Just as adding one to 2,147,483,647 would overflow into the binary representation of the max negative integer, so also subtracting one from -2,147,483,648 would underflow to the max positive integer.

As regards your runtime error in your second function.

int findComplement2(int num){

    int n = floor(log2(num)+1);;            
    int num_with_all_ones =(int) (1<<n)-1;
    return (num_with_all_ones^num);
}
findComplement2(2147483647);

With the parameter num as 2,147,483,647, the variable n is assigned 31 (floor(30.9999999993 + 1), and it would be good to delete the superfluous semicolon. Therefore num_with_all_ones is assigned the difference between the binary number represented by 1 followed by 31 0s (or as we have seen above, the max negative integer -2147483648) and one. This results in an underflow error, which causes your computer to raise the runtime error.

N.B. This is my first Stack answer ever, so if anyone has advice on how to answer better next time, that would be much appreciated.

Upvotes: 2

Related Questions