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:

```
public class Parser {
```
```
 
```

  public static int parseInt(final String value) throws NumberFormatException {

```
    if(null == value) {
```
```
      throw new NullPointerException();
```
```
    } else {
```
```
      final int n = value.length();
```
```
      if(0 == n) {
```

        throw new NumberFormatException();

```
      } else {
```
```
        switch(value.charAt(0)) {
```
```
          case '-':
```

            return negative(value, 1, n);

```
          case '+':
```

            return positive(value, 1, n);

```
          default:
```

            return positive(value, 0, n);

```
        }
```
```
      }
```
```
    }
```
```
  }
```
```
 
```

  private static int positive(final String value, final int start

        , final int end) throws NumberFormatException {

```
    if(start < end) {
```
```
      int result = 0;
```

      for(int i = start; i < end; ++i) {

        if(result > (Integer.MAX_VALUE / 10)) {

          throw new NumberFormatException(); // positive overflow.

```
        } else {
```
```
          result *= 10;
```
```
        }
```

        final char digitChar = value.charAt(i);

        if((digitChar >= '0') && (digitChar <= '9')) {

          final int digit = digitChar - '0';

          if(result > (Integer.MAX_VALUE - digit)) {

            throw new NumberFormatException(); // positive overflow.

```
          } else {
```
```
            result += digit;
```
```
          }
```
```
        } else {
```

          throw new NumberFormatException();

```
        }
```
```
      }
```
```
      return result;
```
```
    } else {
```

      throw new NumberFormatException();

```
    }
```
```
  }
```
```
 
```

  private static int negative(final String value, final int start

        , final int end) throws NumberFormatException {

```
    if(start < end) {
```
```
      int result = 0;
```

      for(int i = start; i < end; ++i) {

        if(result < (Integer.MIN_VALUE / 10)) {

          throw new NumberFormatException(); // negative overflow.

```
        } else {
```
```
          result *= 10;
```
```
        }
```

        final char digitChar = value.charAt(i);

        if((digitChar >= '0') && (digitChar <= '9')) {

          final int digit = digitChar - '0';

          if(result < (Integer.MIN_VALUE + digit)) {

            throw new NumberFormatException(); // negative overflow.

```
          } else {
```
```
            result -= digit;
```
```
          }
```
```
        } else {
```

          throw new NumberFormatException();

```
        }
```
```
      }
```
```
      return result;
```
```
    } else {
```

      throw new NumberFormatException();

```
    }
```
```
  }
```
```
 
```
```
  @Test
```
```
  public void test() {
```

    Assert.assertEquals(0, parseInt("0"));

    Assert.assertEquals(0, parseInt("+0"));

    Assert.assertEquals(0, parseInt("-0"));

    Assert.assertEquals(123, parseInt("123"));

    Assert.assertEquals(123, parseInt("+123"));

    Assert.assertEquals(-123, parseInt("-123"));

```
    Assert.assertEquals(
```

        Integer.MAX_VALUE, parseInt(Integer.toString(Integer.MAX_VALUE)));

```
    Assert.assertEquals(
```

        Integer.MIN_VALUE, parseInt(Integer.toString(Integer.MIN_VALUE)));

    for(final String value : new String[] {

```
        "2147483648",
```
```
        "2147483648123",
```
```
        "-2147483649",
```
```
        "-2147483649123",
```
```
        "+",
```
```
        "-",
```
```
        "",
```
```
        "abc"
```
```
    }) {
```
```
      try {
```
```
        parseInt(value);
```
```
        Assert.fail();
```

      } catch(final NumberFormatException e) {}

```
    }
```
```
    try {
```
```
      parseInt(null);
```

    } catch(final NullPointerException e) {}

```
  }
```
```
}
```

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).

shanhe.me

Handling arithmetic overflow: an exercise of parsing strings to integers

Handling arithmetic overflow: an exercise of parsing strings to integers

Post new comment