How do I detect unsigned integer multiply overflow

Question

I was writing a program in C   to find all solutions of ab   c  where a  b and c together use all the digits 0-9 exactly once  The program looped over values of a and b  and it ran a digit-counting routine each time on a  b and ab to check if the digits condition was satisfied   However  spurious solutions can be generated when ab overflows the integer limit  I ended up checking for this using code like   unsigned long b  c  c test      c test c b             Possible overflow if  c test b    c      There has been an overflow    else c c test          No overflow   Is there a better way of testing for overflow  I know that some chips have an internal flag that is set when overflow occurs  but I ve never seen it accessed through C or C       Beware that signed int overflow is undefined behaviour in C and C    and thus you have to detect it without actually causing it  For signed int overflow before addition  see Detecting signed overflow in C C

User · Answer

The simplest way is to convert your unsigned longs into unsigned long longs  do your multiplication  and compare the result to 0x100000000LL   You ll probably find that this is more efficient than doing the division as you ve done in your example   Oh  and it ll work in both C and C    as you ve tagged the question with both      Just been taking a look at the glibc manual  There s a mention of an integer overflow trap  FPE INTOVF TRAP  as part of SIGFPE  That would be ideal  apart from the nasty bits in the manual      FPE INTOVF TRAP       Integer overflow  impossible in a C program unless you enable overflow trapping in a hardware-specific fashion      A bit of a shame really

User · Answer

Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn t standard   You could also test for the possibility of overflow before you perform the multiplication   if   b  gt  ULONG MAX   a      a   b would overflow

User · Answer

I see that a lot of people answered the question about overflow  but I wanted to address his original problem  He said the problem was to find ab c such that all digits are used without repeating  Ok  that s not what he asked in this post  but I m still think that it was necessary to study the upper bound of the problem and conclude that he would never need to calculate or detect an overflow  note  I m not proficient in math so I did this step by step  but the end result was so simple that this might have a simple formula    The main point is that the upper bound that the problem requires for either a  b or c is 98 765 432  Anyway  starting by splitting the problem in the trivial and non trivial parts    x0    1  all permutations of 9  8  7  6  5  4  3  2 are solutions  x1    x  no solution possible  0b    0  no solution possible  1b    1  no solution possible  ab  a   1  b   1  non trivial    Now we just need to show that no other solution is possible and only the permutations are valid  and then the code to print them is trivial   We go back to the upper bound  Actually the upper bound is c   98 765 432  It s the upper bound because it s the largest number with 8 digits  10 digits total minus 1 for each a and b   This upper bound is only for c because the bounds for a and b must be much lower because of the exponential growth  as we can calculate  varying b from 2 to the upper bound       9938 08 2    98765432     462 241 3    98765432     99 6899 4    98765432     39 7119 5    98765432     21 4998 6    98765432     13 8703 7    98765432     9 98448 8    98765432     7 73196 9    98765432     6 30174 10    98765432     5 33068 11    98765432     4 63679 12    98765432     4 12069 13    98765432     3 72429 14    98765432     3 41172 15    98765432     3 15982 16    98765432     2 95305 17    98765432     2 78064 18    98765432     2 63493 19    98765432     2 51033 20    98765432     2 40268 21    98765432     2 30883 22    98765432     2 22634 23    98765432     2 15332 24    98765432     2 08826 25    98765432     2 02995 26    98765432     1 97741 27    98765432   Notice  for example the last line  it says that 1 97 27  98M  So  for example  1 27    1 and 2 27    134 217 728 and that s not a solution because it has 9 digits  2   1 97 so it s actually bigger than what should be tested   As it can be seen  the combinations available for testing a and b are really small  For b    14  we need to try 2 and 3  For b    3  we start at 2 and stop at 462  All the results are granted to be less than   98M   Now just test all the combinations above and look for the ones that do not repeat any digits         0    2    4    5    6    7    8   84 2   7056       1    2    3    4    5    8    9   59 2   3481       0    1    2    3    4    5    8    9   59 2   3481   leading zero        1    2    3    5    8   8 3   512       0    1    2    3    5    8   8 3   512   leading zero        1    2    4    6   4 2   16       0    1    2    4    6   4 2   16   leading zero        1    2    4    6   2 4   16       0    1    2    4    6   2 4   16   leading zero        1    2    8    9   9 2   81       0    1    2    8    9   9 2   81   leading zero        1    3    4    8   3 4   81       0    1    3    4    8   3 4   81   leading zero        2    3    6    7    9   3 6   729       0    2    3    6    7    9   3 6   729   leading zero        2    3    8   2 3   8       0    2    3    8   2 3   8   leading zero        2    3    9   3 2   9       0    2    3    9   3 2   9   leading zero        2    4    6    8   8 2   64       0    2    4    6    8   8 2   64   leading zero        2    4    7    9   7 2   49       0    2    4    7    9   7 2   49   leading zero    None of them matches the problem  which can also be seen by the absence of  0    1         9     The example code that solves it follows  Also note that s written in Python  not because it needs arbitrary precision integers  the code doesn t calculate anything bigger than 98 million   but because we found out that the amount of tests is so small that we should use a high level language to make use of its built-in containers and libraries  also note  the code has 28 lines        import math      m   98765432     l          for i in xrange 2  98765432           inv   1 0 i         r   m  inv         if  r  lt  2 0   break         top   int math floor r           assert top  lt   m           for j in xrange 2  top 1               s   str i    str j    str j  i              l append  sorted s   i  j  j  i               assert j  i  lt   m       l sort       for s  i  j  ji in l          assert ji  lt   m          ss   sorted set s           if s    ss              print   s  d  d    d     s  i  j  ji             Try with non significant zero somewhere         s     0     s         ss   sorted set s           if s    ss              print   s  d  d    d   leading zero      s  i  j  ji

User · Answer

The x86 instruction set includes an unsigned multiply instruction that stores the result to two registers  To use that instruction from C  one can write the following code in a 64-bit program  GCC    unsigned long checked imul unsigned long a  unsigned long b      unsigned   int128 res    unsigned   int128 a   b    if   unsigned long  res  gt  gt  64       printf  overflow in integer multiply      return  unsigned long res      For a 32-bit program  one needs to make the result 64 bit and parameters 32 bit   An alternative is to use compiler-dependent intrinsic to check the flag register  GCC documentation for overflow intrinsic can be found from 6 56 Built-in Functions to Perform Arithmetic with Overflow Checking

User · Answer

I needed to answer this same question for floating point numbers  where bit masking and shifting does not look promising  The approach I settled on works for signed and unsigned  integer and floating point numbers  It works even if there is no larger data type to promote to for intermediate calculations  It is not the most efficient for all of these types  but because it does work for all of them  it is worth using   Signed Overflow test  Addition and Subtraction    Obtain the constants that represent the largest and smallest possible values for the type  MAXVALUE and MINVALUE  Compute and compare the signs of the operands    a  If either value is zero  then neither addition nor subtraction can overflow  Skip remaining tests   b  If the signs are opposite  then addition cannot overflow  Skip remaining tests   c  If the signs are the same  then subtraction cannot overflow  Skip remaining tests  Test for positive overflow of MAXVALUE   a  If both signs are positive and MAXVALUE - A  lt  B  then addition will overflow   b  If the sign of B is negative and MAXVALUE - A  lt  -B  then subtraction will overflow  Test for negative overflow of MINVALUE   a  If both signs are negative and MINVALUE - A   B  then addition will overflow   b  If the sign of A is negative and MINVALUE - A   B  then subtraction will overflow  Otherwise  no overflow    Signed Overflow test  Multiplication and Division    Obtain the constants that represent the largest and smallest possible values for the type  MAXVALUE and MINVALUE  Compute and compare the magnitudes  absolute values  of the operands to one   Below  assume A and B are these magnitudes  not the signed originals    a  If either value is zero  multiplication cannot overflow  and division will yield zero or an infinity   b  If either value is one  multiplication and division cannot overflow   c  If the magnitude of one operand is below one and of the other is greater than one  multiplication cannot overflow   d  If the magnitudes are both less than one  division cannot overflow  Test for positive overflow of MAXVALUE   a  If both operands are greater than one and MAXVALUE   A  lt  B  then multiplication will overflow   b  If B is less than one and MAXVALUE   B  lt  A  then division will overflow  Otherwise  no overflow    Note  Minimum overflow of MINVALUE is handled by 3  because we took absolute values  However  if ABS MINVALUE    MAXVALUE  then we will have some rare false positives   The tests for underflow are similar  but involve EPSILON  the smallest positive number greater than zero

User · Answer

Try this macro to test the overflow bit of 32-bit machines  adapted the solution of Angel Sinigersky    define overflowflag isOverflow       size t eflags                         asm   pushfl                                pop   eax                               a   eflags                    isOverflow    eflags  gt  gt  11   amp  1     I defined it as a macro because otherwise the overflow bit would have been overwritten   Subsequent is a little application with the code segement above    include  lt cstddef gt   include  lt stdio h gt   include  lt iostream gt   include  lt conio h gt   if defined   MSC VER    include  lt intrin h gt   include  lt oskit x86 gt   endif  using namespace std    define detectOverflow isOverflow         size t eflags                         asm   pushfl                               pop   eax                                a   eflags                    isOverflow    eflags  gt  gt  11   amp  1    int main int argc  char   argv         bool endTest   false      bool isOverflow       do           cout  lt  lt   Enter two intergers   lt  lt  endl          int x   0          int y   0          cin clear            cin  gt  gt  x  gt  gt  y          int z   x   y          detectOverflow isOverflow          printf   nThe result is   d   z           if   isOverflow                std  cout  lt  lt     no overflow occured n   lt  lt  std  endl            else               std  cout  lt  lt     overflow occured n   lt  lt  std  endl                     z   x   x   y          detectOverflow isOverflow          printf   nThe result is   d   z           if   isOverflow                std  cout  lt  lt     no overflow ocurred n   lt  lt  std  endl            else               std  cout  lt  lt     overflow occured n   lt  lt  std  endl                     cout  lt  lt   Do you want to stop   Enter   y   or   Y    lt  lt  endl           char c   0           do               c   getchar              while   c      n    amp  amp   c    EOF             if  c     y     c     Y                 endTest   true                     do               c   getchar              while   c      n    amp  amp   c    EOF           while   endTest

User · Answer

There is a way to determine whether an operation is likely to overflow  using the positions of the most-significant one-bits in the operands and a little basic binary-math knowledge   For addition  any two operands will result in  at most  one bit more than the largest operand s highest one-bit  For example   bool addition is safe uint32 t a  uint32 t b        size t a bits highestOneBitPosition a   b bits highestOneBitPosition b       return  a bits lt 32  amp  amp  b bits lt 32       For multiplication  any two operands will result in  at most  the sum of the bits of the operands  For example   bool multiplication is safe uint32 t a  uint32 t b        size t a bits highestOneBitPosition a   b bits highestOneBitPosition b       return  a bits b bits lt  32       Similarly  you can estimate the maximum size of the result of a to the power of b like this   bool exponentiation is safe uint32 t a  uint32 t b        size t a bits highestOneBitPosition a       return  a bits b lt  32        Substitute the number of bits for your target integer  of course    I m not sure of the fastest way to determine the position of the highest one-bit in a number  here s a brute-force method   size t highestOneBitPosition uint32 t a        size t bits 0      while  a  0              bits          a gt  gt  1             return bits      It s not perfect  but that ll give you a good idea whether any two numbers could overflow before you do the operation  I don t know whether it would be faster than simply checking the result the way you suggested  because of the loop in the highestOneBitPosition function  but it might  especially if you knew how many bits were in the operands beforehand

User · Answer

It depends what you use it for  Performing unsigned long  DWORD  addition or multiplication  the best solution is to use ULARGE INTEGER   ULARGE INTEGER is a structure of two DWORDs  The full value can be accessed as  QuadPart  while the high DWORD is accessed as  HighPart  and the low DWORD is accessed as  LowPart    For example   DWORD My Addition DWORD Value A  DWORD Value B        ULARGE INTEGER a  b       b LowPart   Value A      A 32 bit value up to 32 bit      b HighPart   0      a LowPart   Value B      A 32 bit value up to 32 bit      a HighPart   0       a QuadPart    b QuadPart          If  a HighPart        Then a HighPart contains the overflow  carry       return  a LowPart   a HighPart          Any overflow is stored in a HighPart  up to 32 bits

User · Answer

The simple way to test for overflow is to do validation by checking whether the current value is less than the previous value   For example  suppose you had a loop to print the powers of 2   long lng  int n  for  n   0  n  lt  34    n       lng   pow  2  n      printf    li n   lng       Adding overflow checking the way that I described results in this   long signed lng  lng prev   0  int n  for  n   0  n  lt  34    n        lng   pow  2  n       if  lng  lt   lng prev                printf   Overflow   i n   n              Do whatever you do in the event of overflow                printf    li n   lng       lng prev   lng      It works for unsigned values as well as both positive and negative signed values   Of course  if you wanted to do something similar for decreasing values instead of increasing values  you would flip the  lt   sign to make it  gt    assuming the behaviour of underflow is the same as the behaviour of overflow   In all honesty  that s about as portable as you ll get without access to a CPU s overflow flag  and that would require inline assembly code  making your code non-portable across implementations anyway

User · Answer

Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn t standard   You could also test for the possibility of overflow before you perform the multiplication   if   b  gt  ULONG MAX   a      a   b would overflow

User · Answer

Another variant of a solution  using assembly language  is an external procedure  This example for unsigned integer multiplication using g   and fasm under Linux x64   This procedure multiplies two unsigned integer arguments  32 bits   according to specification for amd64  section 3 2 3 Parameter Passing       If the class is INTEGER  the next available register of the sequence  rdi   rsi   rdx   rcx   r8  and  r9 is used    edi and esi registers in my code   and returns the result or 0 if an overflow has occured   format ELF64  section   text  executable  public u mul  u mul    MOV eax  edi   mul esi   jnc u mul ret   xor eax  eax u mul ret  ret   Test   extern  C  unsigned int u mul const unsigned int a  const unsigned int b    int main         printf   u n   u mul 4000000000 2       0     printf   u n   u mul UINT MAX 2 2       OK     return 0      Link the program with the asm object file  In my case  in Qt Creator  add it to LIBS in a  pro file

User · Answer

A clean way to do it would be to override all operators    and   in particular  and check for an overflow before performing the operations

User · Answer

Calculate the results with doubles  They have 15 significant digits  Your requirement has a hard upper bound on c of 108 thinsp  mdash  thinsp it can have at most 8 digits  Hence  the result will be precise if it s in range  and it will not overflow otherwise

User · Answer

The simplest way is to convert your unsigned longs into unsigned long longs  do your multiplication  and compare the result to 0x100000000LL   You ll probably find that this is more efficient than doing the division as you ve done in your example   Oh  and it ll work in both C and C    as you ve tagged the question with both      Just been taking a look at the glibc manual  There s a mention of an integer overflow trap  FPE INTOVF TRAP  as part of SIGFPE  That would be ideal  apart from the nasty bits in the manual      FPE INTOVF TRAP       Integer overflow  impossible in a C program unless you enable overflow trapping in a hardware-specific fashion      A bit of a shame really

User · Answer

Try this macro to test the overflow bit of 32-bit machines  adapted the solution of Angel Sinigersky    define overflowflag isOverflow       size t eflags                         asm   pushfl                                pop   eax                               a   eflags                    isOverflow    eflags  gt  gt  11   amp  1     I defined it as a macro because otherwise the overflow bit would have been overwritten   Subsequent is a little application with the code segement above    include  lt cstddef gt   include  lt stdio h gt   include  lt iostream gt   include  lt conio h gt   if defined   MSC VER    include  lt intrin h gt   include  lt oskit x86 gt   endif  using namespace std    define detectOverflow isOverflow         size t eflags                         asm   pushfl                               pop   eax                                a   eflags                    isOverflow    eflags  gt  gt  11   amp  1    int main int argc  char   argv         bool endTest   false      bool isOverflow       do           cout  lt  lt   Enter two intergers   lt  lt  endl          int x   0          int y   0          cin clear            cin  gt  gt  x  gt  gt  y          int z   x   y          detectOverflow isOverflow          printf   nThe result is   d   z           if   isOverflow                std  cout  lt  lt     no overflow occured n   lt  lt  std  endl            else               std  cout  lt  lt     overflow occured n   lt  lt  std  endl                     z   x   x   y          detectOverflow isOverflow          printf   nThe result is   d   z           if   isOverflow                std  cout  lt  lt     no overflow ocurred n   lt  lt  std  endl            else               std  cout  lt  lt     overflow occured n   lt  lt  std  endl                     cout  lt  lt   Do you want to stop   Enter   y   or   Y    lt  lt  endl           char c   0           do               c   getchar              while   c      n    amp  amp   c    EOF             if  c     y     c     Y                 endTest   true                     do               c   getchar              while   c      n    amp  amp   c    EOF           while   endTest

User · Answer

Here is a really fast way to detect overflow for at least additions  which might give a lead for multiplication  division and power-of  The idea is that exactly because the processor will just let the value wrap back to zero and that C C   is to abstracted from any specific processor  you can  uint32 t x  y  uint32 t value   x   y  bool overflow   value  lt   x   y    This both ensures that if one operand is zero and one isn t  then overflow won t be falsely detected and is significantly faster than a lot of NOT XOR AND test operations as previously suggested  As pointed out  this approach  although better than other more elaborate ways  is still optimisable  The following is a revision of the original code containing the optimisation  uint32 t x  y  uint32 t value   x   y  const bool overflow   value  lt  x     Alternatively  quot value  lt  y quot  should also work  A more efficient and cheap way to detect multiplication overflow is  uint32 t x  y  const uint32 t a    x  gt  gt  16U     y  amp  0xFFFFU   const uint32 t b    x  amp  0xFFFFU     y  gt  gt  16U   const bool overflow     x  gt  gt  16U     y  gt  gt  16U          a  gt  gt  16U     b  gt  gt  16U   uint32 t value   overflow   UINT32 MAX   x   y   This results in either UINT32 MAX on overflow  or the result of the multiplication  It is strictly undefined behaviour to allow the multiplication to proceed for signed integers in this case  Of note  this uses the partial Karatsuba method multiplicative decomposition to compute the high 32 bits of the 64-bit multiplication to check if any of them should become set to know if the 32-bit multiplication overflows  If using C    you can turn this into a neat little lambda to compute overflow so the inner workings of the detector get hidden  uint32 t x  y  const bool overflow          const uint32 t x  const uint32 t y  noexcept - gt  bool               const uint32 t a  x  gt  gt  16U    uint16 t y            const uint32 t b uint16 t x     y  gt  gt  16U            return   x  gt  gt  16U     y  gt  gt  16U      a  gt  gt  16U     b  gt  gt  16U         x  y     uint32 t value overflow   UINT32 MAX   x   y

User · Answer

To perform an unsigned multiplication without overflowing in a portable way the following can be used          begin multiplication    unsigned multiplicand  multiplier  product  productHalf  int zeroesMultiplicand  zeroesMultiplier  zeroesMultiplicand   number of leading zeroes  multiplicand    zeroesMultiplier     number of leading zeroes  multiplier    if  zeroesMultiplicand   zeroesMultiplier  lt   30   goto overflow  productHalf   multiplicand     c  gt  gt  1    if   int productHalf  lt  0   goto overflow  product   productHalf   2  if  multiplier  amp  1       product    multiplicand     if  product  lt  multiplicand   goto overflow           continue code here where  product  is the correct product         overflow     put overflow handling code here     int number of leading zeroes  unsigned value       int ctZeroes     if  value    0   return 32     ctZeroes   1     if    value  gt  gt  16      0    ctZeroes    16  value   value  lt  lt  16       if    value  gt  gt  24      0    ctZeroes     8  value   value  lt  lt   8       if    value  gt  gt  28      0    ctZeroes     4  value   value  lt  lt   4       if    value  gt  gt  30      0    ctZeroes     2  value   value  lt  lt   2       ctZeroes -  x  gt  gt  31     return ctZeroes

User · Answer

include  lt stdio h gt   include  lt stdlib h gt    define MAX 100   int mltovf int a  int b        if  a  amp  amp  b  return abs a   gt  MAX abs b       else return 0     main         int a  b       for  a   0  a  lt   MAX  a            for  b   0  b  lt  MAX  b               if  mltovf a  b      a b  gt  MAX                printf  Bad calculation  a   d b   d n   a  b

User · Answer

I needed to answer this same question for floating point numbers  where bit masking and shifting does not look promising  The approach I settled on works for signed and unsigned  integer and floating point numbers  It works even if there is no larger data type to promote to for intermediate calculations  It is not the most efficient for all of these types  but because it does work for all of them  it is worth using   Signed Overflow test  Addition and Subtraction    Obtain the constants that represent the largest and smallest possible values for the type  MAXVALUE and MINVALUE  Compute and compare the signs of the operands    a  If either value is zero  then neither addition nor subtraction can overflow  Skip remaining tests   b  If the signs are opposite  then addition cannot overflow  Skip remaining tests   c  If the signs are the same  then subtraction cannot overflow  Skip remaining tests  Test for positive overflow of MAXVALUE   a  If both signs are positive and MAXVALUE - A  lt  B  then addition will overflow   b  If the sign of B is negative and MAXVALUE - A  lt  -B  then subtraction will overflow  Test for negative overflow of MINVALUE   a  If both signs are negative and MINVALUE - A   B  then addition will overflow   b  If the sign of A is negative and MINVALUE - A   B  then subtraction will overflow  Otherwise  no overflow    Signed Overflow test  Multiplication and Division    Obtain the constants that represent the largest and smallest possible values for the type  MAXVALUE and MINVALUE  Compute and compare the magnitudes  absolute values  of the operands to one   Below  assume A and B are these magnitudes  not the signed originals    a  If either value is zero  multiplication cannot overflow  and division will yield zero or an infinity   b  If either value is one  multiplication and division cannot overflow   c  If the magnitude of one operand is below one and of the other is greater than one  multiplication cannot overflow   d  If the magnitudes are both less than one  division cannot overflow  Test for positive overflow of MAXVALUE   a  If both operands are greater than one and MAXVALUE   A  lt  B  then multiplication will overflow   b  If B is less than one and MAXVALUE   B  lt  A  then division will overflow  Otherwise  no overflow    Note  Minimum overflow of MINVALUE is handled by 3  because we took absolute values  However  if ABS MINVALUE    MAXVALUE  then we will have some rare false positives   The tests for underflow are similar  but involve EPSILON  the smallest positive number greater than zero

User · Answer

To perform an unsigned multiplication without overflowing in a portable way the following can be used          begin multiplication    unsigned multiplicand  multiplier  product  productHalf  int zeroesMultiplicand  zeroesMultiplier  zeroesMultiplicand   number of leading zeroes  multiplicand    zeroesMultiplier     number of leading zeroes  multiplier    if  zeroesMultiplicand   zeroesMultiplier  lt   30   goto overflow  productHalf   multiplicand     c  gt  gt  1    if   int productHalf  lt  0   goto overflow  product   productHalf   2  if  multiplier  amp  1       product    multiplicand     if  product  lt  multiplicand   goto overflow           continue code here where  product  is the correct product         overflow     put overflow handling code here     int number of leading zeroes  unsigned value       int ctZeroes     if  value    0   return 32     ctZeroes   1     if    value  gt  gt  16      0    ctZeroes    16  value   value  lt  lt  16       if    value  gt  gt  24      0    ctZeroes     8  value   value  lt  lt   8       if    value  gt  gt  28      0    ctZeroes     4  value   value  lt  lt   4       if    value  gt  gt  30      0    ctZeroes     2  value   value  lt  lt   2       ctZeroes -  x  gt  gt  31     return ctZeroes

User · Answer

MSalter s answer is a good idea   If the integer calculation is required  for precision   but floating point is available  you could do something like   uint64 t foo uint64 t a  uint64 t b        double dc       dc   pow a  b        if  dc  lt  UINT MAX           return  powu64 a  b              else            Overflow

User · Answer

You can t access the overflow flag from C C     Some compilers allow you to insert trap instructions into the code  On GCC the option is -ftrapv   The only portable and compiler independent thing you can do is to check for overflows on your own  Just like you did in your example   However  -ftrapv seems to do nothing on x86 using the latest GCC  I guess it s a leftover from an old version or specific to some other architecture  I had expected the compiler to insert an INTO opcode after each addition  Unfortunately it does not do this

User · Answer

You can t access the overflow flag from C C     Some compilers allow you to insert trap instructions into the code  On GCC the option is -ftrapv   The only portable and compiler independent thing you can do is to check for overflows on your own  Just like you did in your example   However  -ftrapv seems to do nothing on x86 using the latest GCC  I guess it s a leftover from an old version or specific to some other architecture  I had expected the compiler to insert an INTO opcode after each addition  Unfortunately it does not do this

User · Answer

Inline assembly lets you check the overflow bit directly  If you are going to be using C    you really should learn assembly

User · Answer

MSalter s answer is a good idea   If the integer calculation is required  for precision   but floating point is available  you could do something like   uint64 t foo uint64 t a  uint64 t b        double dc       dc   pow a  b        if  dc  lt  UINT MAX           return  powu64 a  b              else            Overflow

User · Answer

Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn t standard   You could also test for the possibility of overflow before you perform the multiplication   if   b  gt  ULONG MAX   a      a   b would overflow

User · Answer

If you have a datatype which is bigger than the one you want to test  say you do a 32-bit add and you have a 64-bit type   then this will detect if an overflow occurred  My example is for an 8-bit add  But it can be scaled up   uint8 t x  y        Give these values    const uint16 t data16      x   y  const bool carry           data16  gt  0xFF   const bool overflow           x   y    amp   x   data16   amp  0x80     It is based on the concepts explained on this page  http   www cs umd edu class spring2003 cmsc311 Notes Comb overflow html  For a 32-bit example  0xFF becomes 0xFFFFFFFF and 0x80 becomes 0x80000000 and finally uint16 t becomes a uint64 t   NOTE  this catches integer addition subtraction overflows  and I realized that your question involves multiplication  In which case  division is likely the best approach  This is commonly a way that calloc implementations make sure that the parameters don t overflow as they are multiplied to get the final size

User · Answer

The simplest way is to convert your unsigned longs into unsigned long longs  do your multiplication  and compare the result to 0x100000000LL   You ll probably find that this is more efficient than doing the division as you ve done in your example   Oh  and it ll work in both C and C    as you ve tagged the question with both      Just been taking a look at the glibc manual  There s a mention of an integer overflow trap  FPE INTOVF TRAP  as part of SIGFPE  That would be ideal  apart from the nasty bits in the manual      FPE INTOVF TRAP       Integer overflow  impossible in a C program unless you enable overflow trapping in a hardware-specific fashion      A bit of a shame really

User · Answer

A clean way to do it would be to override all operators    and   in particular  and check for an overflow before performing the operations

User · Answer

The x86 instruction set includes an unsigned multiply instruction that stores the result to two registers  To use that instruction from C  one can write the following code in a 64-bit program  GCC    unsigned long checked imul unsigned long a  unsigned long b      unsigned   int128 res    unsigned   int128 a   b    if   unsigned long  res  gt  gt  64       printf  overflow in integer multiply      return  unsigned long res      For a 32-bit program  one needs to make the result 64 bit and parameters 32 bit   An alternative is to use compiler-dependent intrinsic to check the flag register  GCC documentation for overflow intrinsic can be found from 6 56 Built-in Functions to Perform Arithmetic with Overflow Checking

User · Answer

To expand on Head Geek s answer  there is a faster way to do the addition is safe   bool addition is safe unsigned int a  unsigned int b        unsigned int L Mask   std  numeric limits lt unsigned int gt   max        L Mask  gt  gt   1      L Mask    L Mask       a  amp   L Mask      b  amp   L Mask       return   a    0    b    0        This uses machine-architecture safe  in that 64-bit and 32-bit unsigned integers will still work fine  Basically  I create a mask that will mask out all but the most significant bit  Then  I mask both integers  and if either of them do not have that bit set  then addition is safe   This would be even faster if you pre-initialize the mask in some constructor  since it never changes

User · Answer

You can t access the overflow flag from C C     Some compilers allow you to insert trap instructions into the code  On GCC the option is -ftrapv   The only portable and compiler independent thing you can do is to check for overflows on your own  Just like you did in your example   However  -ftrapv seems to do nothing on x86 using the latest GCC  I guess it s a leftover from an old version or specific to some other architecture  I had expected the compiler to insert an INTO opcode after each addition  Unfortunately it does not do this

User · Answer

There is a way to determine whether an operation is likely to overflow  using the positions of the most-significant one-bits in the operands and a little basic binary-math knowledge   For addition  any two operands will result in  at most  one bit more than the largest operand s highest one-bit  For example   bool addition is safe uint32 t a  uint32 t b        size t a bits highestOneBitPosition a   b bits highestOneBitPosition b       return  a bits lt 32  amp  amp  b bits lt 32       For multiplication  any two operands will result in  at most  the sum of the bits of the operands  For example   bool multiplication is safe uint32 t a  uint32 t b        size t a bits highestOneBitPosition a   b bits highestOneBitPosition b       return  a bits b bits lt  32       Similarly  you can estimate the maximum size of the result of a to the power of b like this   bool exponentiation is safe uint32 t a  uint32 t b        size t a bits highestOneBitPosition a       return  a bits b lt  32        Substitute the number of bits for your target integer  of course    I m not sure of the fastest way to determine the position of the highest one-bit in a number  here s a brute-force method   size t highestOneBitPosition uint32 t a        size t bits 0      while  a  0              bits          a gt  gt  1             return bits      It s not perfect  but that ll give you a good idea whether any two numbers could overflow before you do the operation  I don t know whether it would be faster than simply checking the result the way you suggested  because of the loop in the highestOneBitPosition function  but it might  especially if you knew how many bits were in the operands beforehand

User · Answer

It depends what you use it for  Performing unsigned long  DWORD  addition or multiplication  the best solution is to use ULARGE INTEGER   ULARGE INTEGER is a structure of two DWORDs  The full value can be accessed as  QuadPart  while the high DWORD is accessed as  HighPart  and the low DWORD is accessed as  LowPart    For example   DWORD My Addition DWORD Value A  DWORD Value B        ULARGE INTEGER a  b       b LowPart   Value A      A 32 bit value up to 32 bit      b HighPart   0      a LowPart   Value B      A 32 bit value up to 32 bit      a HighPart   0       a QuadPart    b QuadPart          If  a HighPart        Then a HighPart contains the overflow  carry       return  a LowPart   a HighPart          Any overflow is stored in a HighPart  up to 32 bits

User · Answer

include  lt stdio h gt   include  lt stdlib h gt    define MAX 100   int mltovf int a  int b        if  a  amp  amp  b  return abs a   gt  MAX abs b       else return 0     main         int a  b       for  a   0  a  lt   MAX  a            for  b   0  b  lt  MAX  b               if  mltovf a  b      a b  gt  MAX                printf  Bad calculation  a   d b   d n   a  b

User · Answer

Clang 3 4  and GCC 5  offer checked arithmetic builtins  They offer a very fast solution to this problem  especially when compared to bit-testing safety checks   For the example in OP s question  it would work like this   unsigned long b  c  c test  if    builtin umull overflow b  c   amp c test            Returned non-zero  there has been an overflow   else          Return zero  there hasn t been an overflow     The Clang documentation doesn t specify whether c test contains the overflowed result if an overflow occurred  but the GCC documentation says that it does  Given that these two like to be   builtin-compatible  it s probably safe to assume that this is how Clang works too   There is a   builtin for each arithmetic operation that can overflow  addition  subtraction  multiplication   with signed and unsigned variants  for int sizes  long sizes  and long long sizes  The syntax for the name is   builtin  us  operation  l l   overflow    u for unsigned or s for signed  operation is one of add  sub or mul  no l suffix means that the operands are ints  one l means long  two ls mean long long    So for a checked signed long integer addition  it would be   builtin saddl overflow  The full list can be found on the Clang documentation page   GCC 5  and Clang 3 8  additionally offer generic builtins that work without specifying the type of the values    builtin add overflow    builtin sub overflow and   builtin mul overflow  These also work on types smaller than int   The builtins lower to what s best for the platform  On x86  they check the carry  overflow and sign flags   Visual Studio s cl exe doesn t have direct equivalents  For unsigned additions and subtractions  including  lt intrin h gt  will allow you to use addcarry uNN and subborrow uNN  where NN is the number of bits  like addcarry u8 or subborrow u64   Their signature is a bit obtuse   unsigned char  addcarry u32 unsigned char c in  unsigned int src1  unsigned int src2  unsigned int  sum   unsigned char  subborrow u32 unsigned char b in  unsigned int src1  unsigned int src2  unsigned int  diff     c in b in is the carry borrow flag on input  and the return value is the carry borrow on output  It does not appear to have equivalents for signed operations or multiplications   Otherwise  Clang for Windows is now production-ready  good enough for Chrome   so that could be an option  too

User · Answer

There is a way to determine whether an operation is likely to overflow  using the positions of the most-significant one-bits in the operands and a little basic binary-math knowledge   For addition  any two operands will result in  at most  one bit more than the largest operand s highest one-bit  For example   bool addition is safe uint32 t a  uint32 t b        size t a bits highestOneBitPosition a   b bits highestOneBitPosition b       return  a bits lt 32  amp  amp  b bits lt 32       For multiplication  any two operands will result in  at most  the sum of the bits of the operands  For example   bool multiplication is safe uint32 t a  uint32 t b        size t a bits highestOneBitPosition a   b bits highestOneBitPosition b       return  a bits b bits lt  32       Similarly  you can estimate the maximum size of the result of a to the power of b like this   bool exponentiation is safe uint32 t a  uint32 t b        size t a bits highestOneBitPosition a       return  a bits b lt  32        Substitute the number of bits for your target integer  of course    I m not sure of the fastest way to determine the position of the highest one-bit in a number  here s a brute-force method   size t highestOneBitPosition uint32 t a        size t bits 0      while  a  0              bits          a gt  gt  1             return bits      It s not perfect  but that ll give you a good idea whether any two numbers could overflow before you do the operation  I don t know whether it would be faster than simply checking the result the way you suggested  because of the loop in the highestOneBitPosition function  but it might  especially if you knew how many bits were in the operands beforehand

User · Answer

The simplest way is to convert your unsigned longs into unsigned long longs  do your multiplication  and compare the result to 0x100000000LL   You ll probably find that this is more efficient than doing the division as you ve done in your example   Oh  and it ll work in both C and C    as you ve tagged the question with both      Just been taking a look at the glibc manual  There s a mention of an integer overflow trap  FPE INTOVF TRAP  as part of SIGFPE  That would be ideal  apart from the nasty bits in the manual      FPE INTOVF TRAP       Integer overflow  impossible in a C program unless you enable overflow trapping in a hardware-specific fashion      A bit of a shame really

User · Answer

Clang now supports dynamic overflow checks for both signed and unsigned integers  See the -fsanitize integer switch  For now  it is the only C   compiler with fully supported dynamic overflow checking for debug purposes

User · Answer

CERT has developed a new approach to detecting and reporting signed integer overflow  unsigned integer wrapping  and integer truncation using the  as-if  infinitely ranged  AIR  integer model   CERT has published a technical report describing the model and produced a working prototype based on GCC 4 4 0 and GCC 4 5 0     The AIR integer model either produces a value equivalent to one that would have been obtained using infinitely ranged integers or results in a runtime constraint violation  Unlike previous integer models  AIR integers do not require precise traps  and consequently do not break or inhibit most existing optimizations

User · Answer

Another variant of a solution  using assembly language  is an external procedure  This example for unsigned integer multiplication using g   and fasm under Linux x64   This procedure multiplies two unsigned integer arguments  32 bits   according to specification for amd64  section 3 2 3 Parameter Passing       If the class is INTEGER  the next available register of the sequence  rdi   rsi   rdx   rcx   r8  and  r9 is used    edi and esi registers in my code   and returns the result or 0 if an overflow has occured   format ELF64  section   text  executable  public u mul  u mul    MOV eax  edi   mul esi   jnc u mul ret   xor eax  eax u mul ret  ret   Test   extern  C  unsigned int u mul const unsigned int a  const unsigned int b    int main         printf   u n   u mul 4000000000 2       0     printf   u n   u mul UINT MAX 2 2       OK     return 0      Link the program with the asm object file  In my case  in Qt Creator  add it to LIBS in a  pro file

User · Answer

To expand on Head Geek s answer  there is a faster way to do the addition is safe   bool addition is safe unsigned int a  unsigned int b        unsigned int L Mask   std  numeric limits lt unsigned int gt   max        L Mask  gt  gt   1      L Mask    L Mask       a  amp   L Mask      b  amp   L Mask       return   a    0    b    0        This uses machine-architecture safe  in that 64-bit and 32-bit unsigned integers will still work fine  Basically  I create a mask that will mask out all but the most significant bit  Then  I mask both integers  and if either of them do not have that bit set  then addition is safe   This would be even faster if you pre-initialize the mask in some constructor  since it never changes

User · Answer

I see you re using unsigned integers  By definition  in C  I don t know about C     unsigned arithmetic does not overflow     so  at least for C  your point is moot     With signed integers  once there has been overflow  undefined behaviour  UB  has occurred and your program can do anything  for example  render tests inconclusive   nbsp    include  lt limits h gt   int a    lt something gt   int x    lt something gt   a    x                  UB    if  a  lt  0               Unreliable test                    To create a conforming program  you need to test for overflow before generating said overflow  The method can be used with unsigned integers too      For addition  include  lt limits h gt   int a    lt something gt   int x    lt something gt   if   x  gt  0   amp  amp   a  gt  INT MAX - x       a   x  would overflow     if   x  lt  0   amp  amp   a  lt  INT MIN - x       a   x  would underflow            For subtraction  include  lt limits h gt  int a    lt something gt   int x    lt something gt   if   x  lt  0   amp  amp   a  gt  INT MAX   x       a - x  would overflow     if   x  gt  0   amp  amp   a  lt  INT MIN   x       a - x  would underflow            For multiplication  include  lt limits h gt   int a    lt something gt   int x    lt something gt      There may be a need to check for -1 for two s complement machines     If one number is -1 and another is INT MIN  multiplying them we get abs INT MIN  which is 1 higher than INT MAX if   a    -1   amp  amp   x    INT MIN       a   x  can overflow    if   x    -1   amp  amp   a    INT MIN       a   x   or  a   x   can overflow       general case if  a  gt  INT MAX   x      a   x  would overflow     if   a  lt  INT MIN   x       a   x  would underflow         For division  except for the INT MIN and -1 special case   there isn t any possibility of going over INT MIN or INT MAX

User · Answer

You can t access the overflow flag from C C      I don t agree with this  You could write some inline assembly language and use a jo  jump overflow  instruction assuming you are on x86 to trap the overflow  Of course  your code would no longer be portable to other architectures   Look at info as and info gcc

User · Answer

Calculate the results with doubles  They have 15 significant digits  Your requirement has a hard upper bound on c of 108 thinsp  mdash  thinsp it can have at most 8 digits  Hence  the result will be precise if it s in range  and it will not overflow otherwise

User · Answer

mozilla  CheckedInt lt T gt  provides overflow-checked integer math for integer type T  using compiler intrinsics on clang and gcc as available   The code is under MPL 2 0 and depends on three  IntegerTypeTraits h  Attributes h and Compiler h  other header-only non-standard library headers plus Mozilla-specific assertion machinery  You probably want to replace the assertion machinery if you import the code

User · Answer

Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn t standard   You could also test for the possibility of overflow before you perform the multiplication   if   b  gt  ULONG MAX   a      a   b would overflow

User · Answer

Another interesting tool is IOC  An Integer Overflow Checker for C C     This is a patched Clang compiler  which adds checks to the code at compile time   You get output looking like this   CLANG ARITHMETIC UNDEFINED at  lt add c   9 11  gt    Op     Reason   Signed Addition Overflow  BINARY OPERATION  left  int32   2147483647 right  int32   1

User · Answer

Here is a  non-portable  solution to the question  The Intel x86 and x64 CPUs have the so-called EFLAGS-register  which is filled in by the processor after each integer arithmetic operation  I will skip a detailed description here  The relevant flags are the  Overflow  Flag  mask 0x800  and the  Carry  Flag  mask 0x1   To interpret them correctly  one should consider if the operands are of signed or unsigned type   Here is a practical way to check the flags from C C    The following code will work on Visual Studio 2005 or newer  both 32 and 64 bit   as well as on GNU C C   64 bit    include  lt cstddef gt   if defined   MSC VER    include  lt intrin h gt   endif  inline size t query intel x86 eflags const size t query bit mask         if defined   MSC VER            return   readeflags    amp  query bit mask        elif defined    GNUC                This code will work only on 64-bit GNU-C machines             Tested and does NOT work with Intel C   10 1          size t eflags            asm     volatile                 pushfq  n t               pop   rax n t               movq   rax   0 n t                 r  eflags                               rax                         return eflags  amp  query bit mask        else           pragma message  No inline assembly will work with this compiler                return 0       endif    int main int argc  char   argv        int x   1000000000      int y   20000      int z   x   y      int f   query intel x86 eflags 0x801       printf   X n   f       If the operands were multiplied without overflow  you would get a return value of 0 from query intel eflags 0x801   i e  neither the carry nor the overflow flags are set  In the provided example code of main    an overflow occurs and the both flags are set to 1  This check does not imply any further calculations  so it should be quite fast

User · Answer

Warning  GCC can optimize away an overflow check when compiling with -O2  The option -Wall will give you a warning in some cases like  if  a   b  lt  a       Deal with overflow        but not in this example   b   abs a   if  b  lt  0       Deal with overflow        The only safe way is to check for overflow before it occurs  as described in the CERT paper  and this would be incredibly tedious to use systematically   Compiling with -fwrapv solves the problem  but disables some optimizations   We desperately need a better solution  I think the compiler should issue a warning by default when making an optimization that relies on overflow not occurring  The present situation allows the compiler to optimize away an overflow check  which is unacceptable in my opinion

User · Answer

You can t access the overflow flag from C C      I don t agree with this  You could write some inline assembly language and use a jo  jump overflow  instruction assuming you are on x86 to trap the overflow  Of course  your code would no longer be portable to other architectures   Look at info as and info gcc

User · Answer

You can t access the overflow flag from C C     Some compilers allow you to insert trap instructions into the code  On GCC the option is -ftrapv   The only portable and compiler independent thing you can do is to check for overflows on your own  Just like you did in your example   However  -ftrapv seems to do nothing on x86 using the latest GCC  I guess it s a leftover from an old version or specific to some other architecture  I had expected the compiler to insert an INTO opcode after each addition  Unfortunately it does not do this

User · Answer

Clang now supports dynamic overflow checks for both signed and unsigned integers  See the -fsanitize integer switch  For now  it is the only C   compiler with fully supported dynamic overflow checking for debug purposes

User · Answer

For unsigned integers  just check that the result is smaller than one of the arguments   unsigned int r  a  b  r   a   b  if  r  lt  a           Overflow     For signed integers you can check the signs of the arguments and of the result   Integers of different signs can t overflow  and integers of the same sign overflow only if the result is of a different sign   signed int r  a  b  s  r   a   b  s   a gt  0  if  s     b gt  0   amp  amp  s     r gt  0            Overflow

User · Answer

If you have a datatype which is bigger than the one you want to test  say you do a 32-bit add and you have a 64-bit type   then this will detect if an overflow occurred  My example is for an 8-bit add  But it can be scaled up   uint8 t x  y        Give these values    const uint16 t data16      x   y  const bool carry           data16  gt  0xFF   const bool overflow           x   y    amp   x   data16   amp  0x80     It is based on the concepts explained on this page  http   www cs umd edu class spring2003 cmsc311 Notes Comb overflow html  For a 32-bit example  0xFF becomes 0xFFFFFFFF and 0x80 becomes 0x80000000 and finally uint16 t becomes a uint64 t   NOTE  this catches integer addition subtraction overflows  and I realized that your question involves multiplication  In which case  division is likely the best approach  This is commonly a way that calloc implementations make sure that the parameters don t overflow as they are multiplied to get the final size

User · Answer

Another interesting tool is IOC  An Integer Overflow Checker for C C     This is a patched Clang compiler  which adds checks to the code at compile time   You get output looking like this   CLANG ARITHMETIC UNDEFINED at  lt add c   9 11  gt    Op     Reason   Signed Addition Overflow  BINARY OPERATION  left  int32   2147483647 right  int32   1

User · Answer

You can t access the overflow flag from C C      I don t agree with this  You could write some inline assembly language and use a jo  jump overflow  instruction assuming you are on x86 to trap the overflow  Of course  your code would no longer be portable to other architectures   Look at info as and info gcc

User · Answer

MSalter s answer is a good idea   If the integer calculation is required  for precision   but floating point is available  you could do something like   uint64 t foo uint64 t a  uint64 t b        double dc       dc   pow a  b        if  dc  lt  UINT MAX           return  powu64 a  b              else            Overflow

User · Answer

Here is a  non-portable  solution to the question  The Intel x86 and x64 CPUs have the so-called EFLAGS-register  which is filled in by the processor after each integer arithmetic operation  I will skip a detailed description here  The relevant flags are the  Overflow  Flag  mask 0x800  and the  Carry  Flag  mask 0x1   To interpret them correctly  one should consider if the operands are of signed or unsigned type   Here is a practical way to check the flags from C C    The following code will work on Visual Studio 2005 or newer  both 32 and 64 bit   as well as on GNU C C   64 bit    include  lt cstddef gt   if defined   MSC VER    include  lt intrin h gt   endif  inline size t query intel x86 eflags const size t query bit mask         if defined   MSC VER            return   readeflags    amp  query bit mask        elif defined    GNUC                This code will work only on 64-bit GNU-C machines             Tested and does NOT work with Intel C   10 1          size t eflags            asm     volatile                 pushfq  n t               pop   rax n t               movq   rax   0 n t                 r  eflags                               rax                         return eflags  amp  query bit mask        else           pragma message  No inline assembly will work with this compiler                return 0       endif    int main int argc  char   argv        int x   1000000000      int y   20000      int z   x   y      int f   query intel x86 eflags 0x801       printf   X n   f       If the operands were multiplied without overflow  you would get a return value of 0 from query intel eflags 0x801   i e  neither the carry nor the overflow flags are set  In the provided example code of main    an overflow occurs and the both flags are set to 1  This check does not imply any further calculations  so it should be quite fast

User · Answer

Warning  GCC can optimize away an overflow check when compiling with -O2  The option -Wall will give you a warning in some cases like  if  a   b  lt  a       Deal with overflow        but not in this example   b   abs a   if  b  lt  0       Deal with overflow        The only safe way is to check for overflow before it occurs  as described in the CERT paper  and this would be incredibly tedious to use systematically   Compiling with -fwrapv solves the problem  but disables some optimizations   We desperately need a better solution  I think the compiler should issue a warning by default when making an optimization that relies on overflow not occurring  The present situation allows the compiler to optimize away an overflow check  which is unacceptable in my opinion

User · Answer

A clean way to do it would be to override all operators    and   in particular  and check for an overflow before performing the operations

User · Answer

Inline assembly lets you check the overflow bit directly  If you are going to be using C    you really should learn assembly

User · Answer

If you have a datatype which is bigger than the one you want to test  say you do a 32-bit add and you have a 64-bit type   then this will detect if an overflow occurred  My example is for an 8-bit add  But it can be scaled up   uint8 t x  y        Give these values    const uint16 t data16      x   y  const bool carry           data16  gt  0xFF   const bool overflow           x   y    amp   x   data16   amp  0x80     It is based on the concepts explained on this page  http   www cs umd edu class spring2003 cmsc311 Notes Comb overflow html  For a 32-bit example  0xFF becomes 0xFFFFFFFF and 0x80 becomes 0x80000000 and finally uint16 t becomes a uint64 t   NOTE  this catches integer addition subtraction overflows  and I realized that your question involves multiplication  In which case  division is likely the best approach  This is commonly a way that calloc implementations make sure that the parameters don t overflow as they are multiplied to get the final size

User · Answer

A clean way to do it would be to override all operators    and   in particular  and check for an overflow before performing the operations

User · Answer

Calculate the results with doubles  They have 15 significant digits  Your requirement has a hard upper bound on c of 108 thinsp  mdash  thinsp it can have at most 8 digits  Hence  the result will be precise if it s in range  and it will not overflow otherwise

User · Answer

I see that a lot of people answered the question about overflow  but I wanted to address his original problem  He said the problem was to find ab c such that all digits are used without repeating  Ok  that s not what he asked in this post  but I m still think that it was necessary to study the upper bound of the problem and conclude that he would never need to calculate or detect an overflow  note  I m not proficient in math so I did this step by step  but the end result was so simple that this might have a simple formula    The main point is that the upper bound that the problem requires for either a  b or c is 98 765 432  Anyway  starting by splitting the problem in the trivial and non trivial parts    x0    1  all permutations of 9  8  7  6  5  4  3  2 are solutions  x1    x  no solution possible  0b    0  no solution possible  1b    1  no solution possible  ab  a   1  b   1  non trivial    Now we just need to show that no other solution is possible and only the permutations are valid  and then the code to print them is trivial   We go back to the upper bound  Actually the upper bound is c   98 765 432  It s the upper bound because it s the largest number with 8 digits  10 digits total minus 1 for each a and b   This upper bound is only for c because the bounds for a and b must be much lower because of the exponential growth  as we can calculate  varying b from 2 to the upper bound       9938 08 2    98765432     462 241 3    98765432     99 6899 4    98765432     39 7119 5    98765432     21 4998 6    98765432     13 8703 7    98765432     9 98448 8    98765432     7 73196 9    98765432     6 30174 10    98765432     5 33068 11    98765432     4 63679 12    98765432     4 12069 13    98765432     3 72429 14    98765432     3 41172 15    98765432     3 15982 16    98765432     2 95305 17    98765432     2 78064 18    98765432     2 63493 19    98765432     2 51033 20    98765432     2 40268 21    98765432     2 30883 22    98765432     2 22634 23    98765432     2 15332 24    98765432     2 08826 25    98765432     2 02995 26    98765432     1 97741 27    98765432   Notice  for example the last line  it says that 1 97 27  98M  So  for example  1 27    1 and 2 27    134 217 728 and that s not a solution because it has 9 digits  2   1 97 so it s actually bigger than what should be tested   As it can be seen  the combinations available for testing a and b are really small  For b    14  we need to try 2 and 3  For b    3  we start at 2 and stop at 462  All the results are granted to be less than   98M   Now just test all the combinations above and look for the ones that do not repeat any digits         0    2    4    5    6    7    8   84 2   7056       1    2    3    4    5    8    9   59 2   3481       0    1    2    3    4    5    8    9   59 2   3481   leading zero        1    2    3    5    8   8 3   512       0    1    2    3    5    8   8 3   512   leading zero        1    2    4    6   4 2   16       0    1    2    4    6   4 2   16   leading zero        1    2    4    6   2 4   16       0    1    2    4    6   2 4   16   leading zero        1    2    8    9   9 2   81       0    1    2    8    9   9 2   81   leading zero        1    3    4    8   3 4   81       0    1    3    4    8   3 4   81   leading zero        2    3    6    7    9   3 6   729       0    2    3    6    7    9   3 6   729   leading zero        2    3    8   2 3   8       0    2    3    8   2 3   8   leading zero        2    3    9   3 2   9       0    2    3    9   3 2   9   leading zero        2    4    6    8   8 2   64       0    2    4    6    8   8 2   64   leading zero        2    4    7    9   7 2   49       0    2    4    7    9   7 2   49   leading zero    None of them matches the problem  which can also be seen by the absence of  0    1         9     The example code that solves it follows  Also note that s written in Python  not because it needs arbitrary precision integers  the code doesn t calculate anything bigger than 98 million   but because we found out that the amount of tests is so small that we should use a high level language to make use of its built-in containers and libraries  also note  the code has 28 lines        import math      m   98765432     l          for i in xrange 2  98765432           inv   1 0 i         r   m  inv         if  r  lt  2 0   break         top   int math floor r           assert top  lt   m           for j in xrange 2  top 1               s   str i    str j    str j  i              l append  sorted s   i  j  j  i               assert j  i  lt   m       l sort       for s  i  j  ji in l          assert ji  lt   m          ss   sorted set s           if s    ss              print   s  d  d    d     s  i  j  ji             Try with non significant zero somewhere         s     0     s         ss   sorted set s           if s    ss              print   s  d  d    d   leading zero      s  i  j  ji

User · Answer

If you have a datatype which is bigger than the one you want to test  say you do a 32-bit add and you have a 64-bit type   then this will detect if an overflow occurred  My example is for an 8-bit add  But it can be scaled up   uint8 t x  y        Give these values    const uint16 t data16      x   y  const bool carry           data16  gt  0xFF   const bool overflow           x   y    amp   x   data16   amp  0x80     It is based on the concepts explained on this page  http   www cs umd edu class spring2003 cmsc311 Notes Comb overflow html  For a 32-bit example  0xFF becomes 0xFFFFFFFF and 0x80 becomes 0x80000000 and finally uint16 t becomes a uint64 t   NOTE  this catches integer addition subtraction overflows  and I realized that your question involves multiplication  In which case  division is likely the best approach  This is commonly a way that calloc implementations make sure that the parameters don t overflow as they are multiplied to get the final size

User · Answer

Here is a really fast way to detect overflow for at least additions  which might give a lead for multiplication  division and power-of  The idea is that exactly because the processor will just let the value wrap back to zero and that C C   is to abstracted from any specific processor  you can  uint32 t x  y  uint32 t value   x   y  bool overflow   value  lt   x   y    This both ensures that if one operand is zero and one isn t  then overflow won t be falsely detected and is significantly faster than a lot of NOT XOR AND test operations as previously suggested  As pointed out  this approach  although better than other more elaborate ways  is still optimisable  The following is a revision of the original code containing the optimisation  uint32 t x  y  uint32 t value   x   y  const bool overflow   value  lt  x     Alternatively  quot value  lt  y quot  should also work  A more efficient and cheap way to detect multiplication overflow is  uint32 t x  y  const uint32 t a    x  gt  gt  16U     y  amp  0xFFFFU   const uint32 t b    x  amp  0xFFFFU     y  gt  gt  16U   const bool overflow     x  gt  gt  16U     y  gt  gt  16U          a  gt  gt  16U     b  gt  gt  16U   uint32 t value   overflow   UINT32 MAX   x   y   This results in either UINT32 MAX on overflow  or the result of the multiplication  It is strictly undefined behaviour to allow the multiplication to proceed for signed integers in this case  Of note  this uses the partial Karatsuba method multiplicative decomposition to compute the high 32 bits of the 64-bit multiplication to check if any of them should become set to know if the 32-bit multiplication overflows  If using C    you can turn this into a neat little lambda to compute overflow so the inner workings of the detector get hidden  uint32 t x  y  const bool overflow          const uint32 t x  const uint32 t y  noexcept - gt  bool               const uint32 t a  x  gt  gt  16U    uint16 t y            const uint32 t b uint16 t x     y  gt  gt  16U            return   x  gt  gt  16U     y  gt  gt  16U      a  gt  gt  16U     b  gt  gt  16U         x  y     uint32 t value overflow   UINT32 MAX   x   y

User · Answer

Inline assembly lets you check the overflow bit directly  If you are going to be using C    you really should learn assembly

User · Answer

CERT has developed a new approach to detecting and reporting signed integer overflow  unsigned integer wrapping  and integer truncation using the  as-if  infinitely ranged  AIR  integer model   CERT has published a technical report describing the model and produced a working prototype based on GCC 4 4 0 and GCC 4 5 0     The AIR integer model either produces a value equivalent to one that would have been obtained using infinitely ranged integers or results in a runtime constraint violation  Unlike previous integer models  AIR integers do not require precise traps  and consequently do not break or inhibit most existing optimizations

User · Answer

The simple way to test for overflow is to do validation by checking whether the current value is less than the previous value   For example  suppose you had a loop to print the powers of 2   long lng  int n  for  n   0  n  lt  34    n       lng   pow  2  n      printf    li n   lng       Adding overflow checking the way that I described results in this   long signed lng  lng prev   0  int n  for  n   0  n  lt  34    n        lng   pow  2  n       if  lng  lt   lng prev                printf   Overflow   i n   n              Do whatever you do in the event of overflow                printf    li n   lng       lng prev   lng      It works for unsigned values as well as both positive and negative signed values   Of course  if you wanted to do something similar for decreasing values instead of increasing values  you would flip the  lt   sign to make it  gt    assuming the behaviour of underflow is the same as the behaviour of overflow   In all honesty  that s about as portable as you ll get without access to a CPU s overflow flag  and that would require inline assembly code  making your code non-portable across implementations anyway

User · Answer

mozilla  CheckedInt lt T gt  provides overflow-checked integer math for integer type T  using compiler intrinsics on clang and gcc as available   The code is under MPL 2 0 and depends on three  IntegerTypeTraits h  Attributes h and Compiler h  other header-only non-standard library headers plus Mozilla-specific assertion machinery  You probably want to replace the assertion machinery if you import the code

User · Answer

Inline assembly lets you check the overflow bit directly  If you are going to be using C    you really should learn assembly

User · Answer

Calculate the results with doubles  They have 15 significant digits  Your requirement has a hard upper bound on c of 108 thinsp  mdash  thinsp it can have at most 8 digits  Hence  the result will be precise if it s in range  and it will not overflow otherwise

User · Answer

For unsigned integers  just check that the result is smaller than one of the arguments   unsigned int r  a  b  r   a   b  if  r  lt  a           Overflow     For signed integers you can check the signs of the arguments and of the result   Integers of different signs can t overflow  and integers of the same sign overflow only if the result is of a different sign   signed int r  a  b  s  r   a   b  s   a gt  0  if  s     b gt  0   amp  amp  s     r gt  0            Overflow

User · Answer

You can t access the overflow flag from C C      I don t agree with this  You could write some inline assembly language and use a jo  jump overflow  instruction assuming you are on x86 to trap the overflow  Of course  your code would no longer be portable to other architectures   Look at info as and info gcc

User · Answer

Clang 3 4  and GCC 5  offer checked arithmetic builtins  They offer a very fast solution to this problem  especially when compared to bit-testing safety checks   For the example in OP s question  it would work like this   unsigned long b  c  c test  if    builtin umull overflow b  c   amp c test            Returned non-zero  there has been an overflow   else          Return zero  there hasn t been an overflow     The Clang documentation doesn t specify whether c test contains the overflowed result if an overflow occurred  but the GCC documentation says that it does  Given that these two like to be   builtin-compatible  it s probably safe to assume that this is how Clang works too   There is a   builtin for each arithmetic operation that can overflow  addition  subtraction  multiplication   with signed and unsigned variants  for int sizes  long sizes  and long long sizes  The syntax for the name is   builtin  us  operation  l l   overflow    u for unsigned or s for signed  operation is one of add  sub or mul  no l suffix means that the operands are ints  one l means long  two ls mean long long    So for a checked signed long integer addition  it would be   builtin saddl overflow  The full list can be found on the Clang documentation page   GCC 5  and Clang 3 8  additionally offer generic builtins that work without specifying the type of the values    builtin add overflow    builtin sub overflow and   builtin mul overflow  These also work on types smaller than int   The builtins lower to what s best for the platform  On x86  they check the carry  overflow and sign flags   Visual Studio s cl exe doesn t have direct equivalents  For unsigned additions and subtractions  including  lt intrin h gt  will allow you to use addcarry uNN and subborrow uNN  where NN is the number of bits  like addcarry u8 or subborrow u64   Their signature is a bit obtuse   unsigned char  addcarry u32 unsigned char c in  unsigned int src1  unsigned int src2  unsigned int  sum   unsigned char  subborrow u32 unsigned char b in  unsigned int src1  unsigned int src2  unsigned int  diff     c in b in is the carry borrow flag on input  and the return value is the carry borrow on output  It does not appear to have equivalents for signed operations or multiplications   Otherwise  Clang for Windows is now production-ready  good enough for Chrome   so that could be an option  too

User · Answer

There is a way to determine whether an operation is likely to overflow  using the positions of the most-significant one-bits in the operands and a little basic binary-math knowledge   For addition  any two operands will result in  at most  one bit more than the largest operand s highest one-bit  For example   bool addition is safe uint32 t a  uint32 t b        size t a bits highestOneBitPosition a   b bits highestOneBitPosition b       return  a bits lt 32  amp  amp  b bits lt 32       For multiplication  any two operands will result in  at most  the sum of the bits of the operands  For example   bool multiplication is safe uint32 t a  uint32 t b        size t a bits highestOneBitPosition a   b bits highestOneBitPosition b       return  a bits b bits lt  32       Similarly  you can estimate the maximum size of the result of a to the power of b like this   bool exponentiation is safe uint32 t a  uint32 t b        size t a bits highestOneBitPosition a       return  a bits b lt  32        Substitute the number of bits for your target integer  of course    I m not sure of the fastest way to determine the position of the highest one-bit in a number  here s a brute-force method   size t highestOneBitPosition uint32 t a        size t bits 0      while  a  0              bits          a gt  gt  1             return bits      It s not perfect  but that ll give you a good idea whether any two numbers could overflow before you do the operation  I don t know whether it would be faster than simply checking the result the way you suggested  because of the loop in the highestOneBitPosition function  but it might  especially if you knew how many bits were in the operands beforehand

User · Answer

Catching Integer Overflows in C points out a solution more general than the one discussed by CERT  it is more general in term of handled types   even if it requires some GCC extensions  I don t know how widely supported they are

User · Answer

MSalter s answer is a good idea   If the integer calculation is required  for precision   but floating point is available  you could do something like   uint64 t foo uint64 t a  uint64 t b        double dc       dc   pow a  b        if  dc  lt  UINT MAX           return  powu64 a  b              else            Overflow

User · Answer

Catching Integer Overflows in C points out a solution more general than the one discussed by CERT  it is more general in term of handled types   even if it requires some GCC extensions  I don t know how widely supported they are

User · Answer

I see you re using unsigned integers  By definition  in C  I don t know about C     unsigned arithmetic does not overflow     so  at least for C  your point is moot     With signed integers  once there has been overflow  undefined behaviour  UB  has occurred and your program can do anything  for example  render tests inconclusive   nbsp    include  lt limits h gt   int a    lt something gt   int x    lt something gt   a    x                  UB    if  a  lt  0               Unreliable test                    To create a conforming program  you need to test for overflow before generating said overflow  The method can be used with unsigned integers too      For addition  include  lt limits h gt   int a    lt something gt   int x    lt something gt   if   x  gt  0   amp  amp   a  gt  INT MAX - x       a   x  would overflow     if   x  lt  0   amp  amp   a  lt  INT MIN - x       a   x  would underflow            For subtraction  include  lt limits h gt  int a    lt something gt   int x    lt something gt   if   x  lt  0   amp  amp   a  gt  INT MAX   x       a - x  would overflow     if   x  gt  0   amp  amp   a  lt  INT MIN   x       a - x  would underflow            For multiplication  include  lt limits h gt   int a    lt something gt   int x    lt something gt      There may be a need to check for -1 for two s complement machines     If one number is -1 and another is INT MIN  multiplying them we get abs INT MIN  which is 1 higher than INT MAX if   a    -1   amp  amp   x    INT MIN       a   x  can overflow    if   x    -1   amp  amp   a    INT MIN       a   x   or  a   x   can overflow       general case if  a  gt  INT MAX   x      a   x  would overflow     if   a  lt  INT MIN   x       a   x  would underflow         For division  except for the INT MIN and -1 special case   there isn t any possibility of going over INT MIN or INT MAX

[c++] How do I detect unsigned integer multiply overflow?

Examples related to c++

Examples related to c

Examples related to integer-overflow