Handling arithmetic overflow: an exercise of parsing strings to integers

Handling arithmetic overflow: an exercise of parsing strings to integers

Let us say we want to parse a string to an integer, where we must throw an exception if the parsed value is too positive or too negative. This boils down to how arithmetic overflow can be detected.

Here is an example code snippet:

  1. public class Parser {
  2.  
  3.   public static int parseInt(final String value) throws NumberFormatException {
  4.     if(null == value) {
  5.       throw new NullPointerException();
  6.     } else {
  7.       final int n = value.length();
  8.       if(0 == n) {
  9.         throw new NumberFormatException();
  10.       } else {
  11.         switch(value.charAt(0)) {
  12.           case '-':
  13.             return negative(value, 1, n);
  14.           case '+':
  15.             return positive(value, 1, n);
  16.           default:
  17.             return positive(value, 0, n);
  18.         }
  19.       }
  20.     }
  21.   }
  22.  
  23.   private static int positive(final String value, final int start
  24.         , final int end) throws NumberFormatException {
  25.     if(start < end) {
  26.       int result = 0;
  27.       for(int i = start; i < end; ++i) {
  28.         if(result > (Integer.MAX_VALUE / 10)) {
  29.           throw new NumberFormatException(); // positive overflow.
  30.         } else {
  31.           result *= 10;
  32.         }
  33.         final char digitChar = value.charAt(i);
  34.         if((digitChar >= '0') && (digitChar <= '9')) {
  35.           final int digit = digitChar - '0';
  36.           if(result > (Integer.MAX_VALUE - digit)) {
  37.             throw new NumberFormatException(); // positive overflow.
  38.           } else {
  39.             result += digit;
  40.           }
  41.         } else {
  42.           throw new NumberFormatException();
  43.         }
  44.       }
  45.       return result;
  46.     } else {
  47.       throw new NumberFormatException();
  48.     }
  49.   }
  50.  
  51.   private static int negative(final String value, final int start
  52.         , final int end) throws NumberFormatException {
  53.     if(start < end) {
  54.       int result = 0;
  55.       for(int i = start; i < end; ++i) {
  56.         if(result < (Integer.MIN_VALUE / 10)) {
  57.           throw new NumberFormatException(); // negative overflow.
  58.         } else {
  59.           result *= 10;
  60.         }
  61.         final char digitChar = value.charAt(i);
  62.         if((digitChar >= '0') && (digitChar <= '9')) {
  63.           final int digit = digitChar - '0';
  64.           if(result < (Integer.MIN_VALUE + digit)) {
  65.             throw new NumberFormatException(); // negative overflow.
  66.           } else {
  67.             result -= digit;
  68.           }
  69.         } else {
  70.           throw new NumberFormatException();
  71.         }
  72.       }
  73.       return result;
  74.     } else {
  75.       throw new NumberFormatException();
  76.     }
  77.   }
  78.  
  79.   @Test
  80.   public void test() {
  81.     Assert.assertEquals(0, parseInt("0"));
  82.     Assert.assertEquals(0, parseInt("+0"));
  83.     Assert.assertEquals(0, parseInt("-0"));
  84.     Assert.assertEquals(123, parseInt("123"));
  85.     Assert.assertEquals(123, parseInt("+123"));
  86.     Assert.assertEquals(-123, parseInt("-123"));
  87.     Assert.assertEquals(
  88.         Integer.MAX_VALUE, parseInt(Integer.toString(Integer.MAX_VALUE)));
  89.     Assert.assertEquals(
  90.         Integer.MIN_VALUE, parseInt(Integer.toString(Integer.MIN_VALUE)));
  91.     for(final String value : new String[] {
  92.         "2147483648",
  93.         "2147483648123",
  94.         "-2147483649",
  95.         "-2147483649123",
  96.         "+",
  97.         "-",
  98.         "",
  99.         "abc"
  100.     }) {
  101.       try {
  102.         parseInt(value);
  103.         Assert.fail();
  104.       } catch(final NumberFormatException e) {}
  105.     }
  106.     try {
  107.       parseInt(null);
  108.     } catch(final NullPointerException e) {}
  109.   }
  110. }

For positive numbers, we need to make sure that (m is Integer.MAX_VALUE here)

(1)

We can first make sure

(2)

Then make sure

(3)

For negative numbers, similarly (n is Integer.MIN_VALUE here)

(4)

First

(5)

Then

(6)

Note that in Java, for a positive integer n, n/10 is equivalent to Math.floor(n/10); for a negative integer n, n/10 is equivalent to Math.ceil(n/10).

Post new comment

The content of this field is kept private and will not be shown publicly.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.

More information about formatting options

To prevent automated spam submissions leave this field empty.