Geek Answers Handbook

Overflow of whole divisions

Problem

I was thinking about overflow integer (type int), and it occurs to me that division can overflow.

An example . On my current platform, I have

INT_MIN == -INT_MAX - 1

and therefore

 INT_MIN < -INT_MAX

and therefore

 INT_MIN / -1 > -INT_MAX / -1

and therefore

 INT_MIN / -1 > INT_MAX.

Therefore, division (INT_MIN / -1) is overflowed.

Questions

So, I have two questions:

  • What could (cross-platform) C code write to prevent div overflow (for type (signed) int)?

  • What guarantees (in the C or C ++ standard) can help with code development?

For example, if the standard guarantees that we have

 INT_MIN == -INT_MAX - 1

or

 INT_MIN == -INT_MAX,

The following code appears to prevent overflow.

 #include <limits.h> /* Try to divide integer op1 by op2. Return 0 (success) or 1 (possibly overflow prevented). In case of success, write the quotient to res. */ int safe_int_div(int * res, int op1, int op2) { /* assert(res != NULL); */ /* assert(op2 != 0); */ if ( op1 == INT_MIN && op2 == -1 ) { return 1; } *res = op1 / op2; return 0; }
+5
source share
2 answers

What guarantees (in the C or C ++ standard) can help with code development?

C indicates a signed integer representation using 1 of 3 forms: sign and magnitude, two additions or additions. Given these forms, only division by 0 and two-component division of INT_MIN/-1 can occur.

What can be written (cross-platform) C code to prevent div overflow (for type (signed) int)?

 int safe_int_div(int * res, int op1, int op2) { if (op2 == 0) { return 1; } // 2 complement detection #if (INT_MIN != -INT_MAX) if (op1 == INT_MIN && op2 == -1) { return 1; } #endif *res = op1 / op2; return 0; }
+4
source

1) As with any other operation in C, the application must ensure that:

  • the type used for the calculation itself is large enough, and
  • the type of variable in which the result is stored is large enough.

A way to ensure this is to set size limits for each operand before the operation. What suitable constraints depend on the algorithm and variable assignment.

2) If you use stdint.h of the C standard, you get guarantees of how large the variables are, portable. You should never use int when writing portable code.

As in the case of writing a safe division subroutine, 32-bit integers are required as parameters, then a calculation is performed on 64-bit integers and the result is returned as a 32-bit integer.

 #include <stdint.h> #include <stdbool.h> /* Try to divide integer op1 by op2. Return true (success) or false (possibly overflow prevented). In case of success, write the quotient to res. In case of failure, res remains untouched. */ bool safe_int_div (int32_t* res, int32_t op1, int32_t op2) { if(op2 == 0) return false; int64_t res64 = (int64_t)op1 / (int64_t)op2; if(res64 > INT32_MAX || res64 < INT32_MIN) return false; *res = (int32_t)res64_t; return true; }

If you need more information about why the split failed, replace bool with an enumeration.

0
source

More articles:


All Articles