How to check if a number overflows an 'int' [duplicate]

Question

Possible Duplicate:
Best way to detect integer overflow in C/C++

I was asked this question in an interview : "Convert a string representation of a number into an integer". But if the number exceeds the max value that can be stored in a 32 bit integer, it must throw an error. My question is how can we check if a number overflows a 32-bit unsigned int ?

Answer 1

(I looked at the possible duplicate to this question and I'm uncertain how useful that reading will be, since in an interview context, you'd be expected describe the general ideas / approach)

---

Part of answering interview questions is to ask clarifying questions (one of the important checklist items that interviewers expects from you).

So your line of inquiry should at least include things like:

• Are you allowed to use unsigned long long / uint64_t (64 bit int)?
• Where is the string coming from? stdin / read from file / hard-coded as a string literal?
• Is it given to you as a Decimal representation? Binary / Octal / Hex?
• What kind of error should be thrown? Do we try to recover and continue execution? What's the fail-safe default value?

Assuming that your interviewer tells you that it's in Decimal representation + you can use unsigned long long:

• First check the number of digits: 32-bit unsigned int ranges between 0 to 4,294,967,295. If the number's string representation in decimal has more than 10 characters (has more than 10 digits), it already overflows; raise error.
• Next, save the number into an unsigned long long and divide by UINT32_MAX+1=4294967296. If the result is greater than 0, it overflows; raise error.

Answer 2

In the loop, you've got the current value of the integer determined by the first digits. You're about to do:

curval = curval * 10 + digit;  // digit converted from '0'..'9' to 0..9 already

You can test for overflow with:

if (curval > UINT32_MAX / 10 || (curval == UINT32_MAX / 10 && digit > UINT32_MAX % 10))
    ...overflow would occur...
else
    curval = curval * 10 + digit; // overflow did not occur

The division and modulus operations are compile time operations, not run time operations.

One advantage of this approach over using a 'larger than 32-bit unsigned integer for the calculation' is that it can be extended to work with bigger integers — with 64-bit integers and uintmax_t integers — by changing the constant from UINT32_MAX to UINT64_MAX or UINTMAX_MAX. That's all that's necessary (other than changing the variable types, of course).

---

The same basic test also works for signed types, but there's an added complication. It's easier to use 16-bit integers for demo purposes (fewer digits to type and think about), so I'm switching to 16-bit two's-complement short with:

• USHRT_MAX = 65535
• SHRT_MAX = 32767
• SHRT_MIN = -32768

The problem is that the short type can store -32768 but the largest positive value you can accumulate is 32767. For all values except SHRT_MIN, the test above would work fine. There are ways around this dilemma. One is to store the curval as a negative value during the calculation, and to negate it before returning if it should be positive. Then your testing might be:

if (curval < SHRT_MIN / 10 || (curval == SHRT_MIN / 10 && digit > -(SHRT_MIN / 10))
    ...overflow would occur...
else
    curval = curval * 10 - digit; // Note subtraction!

You still have to check that curval is not SHRT_MIN before negating the negative value. (In theory, you should check that -SHRT_MAX != SHRT_MIN to allow for other systems than two's complement binary; the values I quoted for the limits satisfy that condition.)

The same thinking and techniques apply to INT_MAX, INT32_MAX, INT64_MAX and INTMAX_MAX, of course.