How does Java handle integer underflows and overflows and how would you check for it?
If it overflows, it goes back to the minimum value and continues from there. If it underflows, it goes back to the maximum value and continues from there.
You can check that beforehand as follows:
public static boolean willAdditionOverflow(int left, int right) {
if (right < 0 && right != Integer.MIN_VALUE) {
return willSubtractionOverflow(left, -right);
} else {
return (~(left ^ right) & (left ^ (left + right))) < 0;
}
}
public static boolean willSubtractionOverflow(int left, int right) {
if (right < 0) {
return willAdditionOverflow(left, -right);
} else {
return ((left ^ right) & (left ^ (left - right))) < 0;
}
}
(you can substitute int by long to perform the same checks for long)
If you think that this may occur more than often, then consider using a datatype or object which can store larger values, e.g. long or maybe java.math.BigInteger. The last one doesn't overflow, practically, the available JVM memory is the limit.
If you happen to be on Java8 already, then you can make use of the new Math#addExact() and Math#subtractExact() methods which will throw an ArithmeticException on overflow.
public static boolean willAdditionOverflow(int left, int right) {
try {
Math.addExact(left, right);
return false;
} catch (ArithmeticException e) {
return true;
}
}
public static boolean willSubtractionOverflow(int left, int right) {
try {
Math.subtractExact(left, right);
return false;
} catch (ArithmeticException e) {
return true;
}
}
The source code can be found here and here respectively.
Of course, you could also just use them right away instead of hiding them in a boolean utility method.
Well, as far as primitive integer types go, Java doesnt handle Over/Underflow at all (for float and double the behaviour is different, it will flush to +/- infinity just as IEEE-754 mandates).
When adding two int's, you will get no indication when an overflow occurs. A simple method to check for overflow is to use the next bigger type to actually perform the operation and check if the result is still in range for the source type:
public int addWithOverflowCheck(int a, int b) {
// the cast of a is required, to make the + work with long precision,
// if we just added (a + b) the addition would use int precision and
// the result would be cast to long afterwards!
long result = ((long) a) + b;
if (result > Integer.MAX_VALUE) {
throw new RuntimeException("Overflow occured");
} else if (result < Integer.MIN_VALUE) {
throw new RuntimeException("Underflow occured");
}
// at this point we can safely cast back to int, we checked before
// that the value will be withing int's limits
return (int) result;
}
What you would do in place of the throw clauses, depends on your applications requirements (throw, flush to min/max or just log whatever). If you want to detect overflow on long operations, you're out of luck with primitives, use BigInteger instead.
Edit (2014-05-21): Since this question seems to be referred to quite frequently and I had to solve the same problem myself, its quite easy to evaluate the overflow condition by the same method a CPU would calculate its V flag.
Its basically a boolean expression that involves the sign of both operands as well as the result:
/**
* Add two int's with overflow detection (r = s + d)
*/
public static int add(final int s, final int d) throws ArithmeticException {
int r = s + d;
if (((s & d & ~r) | (~s & ~d & r)) < 0)
throw new ArithmeticException("int overflow add(" + s + ", " + d + ")");
return r;
}
In java its simpler to apply the expression (in the if) to the entire 32 bits, and check the result using < 0 (this will effectively test the sign bit). The principle works exactly the same for all integer primitive types, changing all declarations in above method to long makes it work for long.
For smaller types, due to the implicit conversion to int (see the JLS for bitwise operations for details), instead of checking < 0, the check needs to mask the sign bit explicitly (0x8000 for short operands, 0x80 for byte operands, adjust casts and parameter declaration appropiately):
/**
* Subtract two short's with overflow detection (r = d - s)
*/
public static short sub(final short d, final short s) throws ArithmeticException {
int r = d - s;
if ((((~s & d & ~r) | (s & ~d & r)) & 0x8000) != 0)
throw new ArithmeticException("short overflow sub(" + s + ", " + d + ")");
return (short) r;
}
(Note that above example uses the expression need for subtract overflow detection)
So how/why do these boolean expressions work? First, some logical thinking reveals that an overflow can only occur if the signs of both arguments are the same. Because, if one argument is negative and one positive, the result (of add) must be closer to zero, or in the extreme case one argument is zero, the same as the other argument. Since the arguments by themselves can't create an overflow condition, their sum can't create an overflow either.
So what happens if both arguments have the same sign? Lets take a look at the case both are positive: adding two arguments that create a sum larger than the types MAX_VALUE, will always yield a negative value, so an overflow occurs if arg1 + arg2 > MAX_VALUE. Now the maximum value that could result would be MAX_VALUE + MAX_VALUE (the extreme case both arguments are MAX_VALUE). For a byte (example) that would mean 127 + 127 = 254. Looking at the bit representations of all values that can result from adding two positive values, one finds that those that overflow (128 to 254) all have bit 7 set, while all that do not overflow (0 to 127) have bit 7 (topmost, sign) cleared. Thats exactly what the first (right) part of the expression checks:
if (((s & d & ~r) | (~s & ~d & r)) < 0)
(~s & ~d & r) becomes true, only if, both operands (s, d) are positive and the result (r) is negative (the expression works on all 32 bits, but the only bit we're interested in is the topmost (sign) bit, which is checked against by the < 0).
Now if both arguments are negative, their sum can never be closer to zero than any of the arguments, the sum must be closer to minus infinity. The most extreme value we can produce is MIN_VALUE + MIN_VALUE, which (again for byte example) shows that for any in range value (-1 to -128) the sign bit is set, while any possible overflowing value (-129 to -256) has the sign bit cleared. So the sign of the result again reveals the overflow condition. Thats what the left half (s & d & ~r) checks for the case where both arguments (s, d) are negative and a result that is positive. The logic is largely equivalent to the positive case; all bit patterns that can result from adding two negative values will have the sign bit cleared if and only if an underflow occured.
By default, Java's int and long math silently wrap around on overflow and underflow. (Integer operations on other integer types are performed by first promoting the operands to int or long, per JLS 4.2.2.)
As of Java 8, java.lang.Math provides addExact, subtractExact, multiplyExact, incrementExact, decrementExact and negateExact static methods for both int and long arguments that perform the named operation, throwing ArithmeticException on overflow. (There's no divideExact method -- you'll have to check the one special case (MIN_VALUE / -1) yourself.)
As of Java 8, java.lang.Math also provides toIntExact to cast a long to an int, throwing ArithmeticException if the long's value does not fit in an int. This can be useful for e.g. computing the sum of ints using unchecked long math, then using toIntExact to cast to int at the end (but be careful not to let your sum overflow).
If you're still using an older version of Java, Google Guava provides IntMath and LongMath static methods for checked addition, subtraction, multiplication and exponentiation (throwing on overflow). These classes also provide methods to compute factorials and binomial coefficients that return MAX_VALUE on overflow (which is less convenient to check). Guava's primitive utility classes, SignedBytes, UnsignedBytes, Shorts and Ints, provide checkedCast methods for narrowing larger types (throwing IllegalArgumentException on under/overflow, not ArithmeticException), as well as saturatingCast methods that return MIN_VALUE or MAX_VALUE on overflow.