How to check if number overflows 'int'

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 to an integer." But if the number exceeds the maximum value that can be stored in a 32-bit integer, it should throw an error. My question is, how can we check if a number overflows a 32-bit unsigned int?

Answer 1

(I looked at a possible duplicate of this question, and I'm not sure how useful this reading is, since in the context of the interview you expect to describe general ideas / approach)

---

Part of the answers to interview questions is to ask clarifying questions (one of the important elements of the checklist that interviewers expect from you).

Thus, your line of research should include such things as:

• Are you allowed to use unsigned long long / uint64_t (64-bit int)?
• Where did the line come from? stdin / read from file / hardcoded as string literal?
• Is it given to you as a decimal representation? Binary / octal / hexadecimal?
• What mistake should be thrown? Are we trying to restore and continue execution? What is the safe default?

Assuming your interviewer tells you that in decimal + you can use unsigned long long :

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

Answer 2

In the loop, you have the current integer value, determined by the first digits. You are going to do:

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

You can test 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 

Division and module operations are compile-time operations, not run-time operations.

One of the advantages of this approach in using more than 32-bit unsigned integer for calculation is that it can be extended to work with large integers - with 64-bit integers and uintmax_t integers - by changing the constant from UINT32_MAX to UINT64_MAX or UINTMAX_MAX. This is all that is needed (except for changing the types of variables, of course).

---

The same basic test also works for signed types, but there is an additional complication. It is easier to use 16-bit integers for demonstration purposes (fewer digits to print and think), so I will move on to the 16-bit 2'-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 copy is 32767. For all values ​​except SHRT_MIN, the test above will work fine. There are ways around this dilemma. One of them is to keep curval as a negative value during the calculation and cancel it before returning if it should be positive. Then your testing could be:

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

You still need to check that curval not SHRT_MIN before negating a negative value. (Theoretically, you should verify that -SHRT_MAX != SHRT_MIN allow systems other than two binary additions, the values ​​specified for the limits satisfy this condition.)

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

Answer 3

Make the conversion using uint64_t . You will add one digit at a time; for each digit you multiply by 10 and add the value of the next character. After processing each character, check if the result is greater than UINT32_MAX ; if so, exit with an error (or what you should do when overflowing). Once you're done, return the number as uint32_t . uint64_t , uint32_t and UINT32_MAX defined in stdint.h .