...

Failure to account for integer overflow has resulted in failures of real systems, for instance, when implementing the {{compareTo()}} method. The meaning of the return value of the {{compareTo()}} method is defined only in terms of its sign and whether it is zero; the magnitude of the return value is irrelevant. Consequently, an apparent --- but incorrect --- optimization would be to subtract the operands and return the result. For operands of opposite sign, this can result in integer overflow; consequently violating the {{compareTo()}} contract \[[Bloch 2008, item 12|AA. Bibliography#Bloch 08]\].

Addition

Addition (as with all arithmetic operations) in Java is performed on signed numbers only; unsigned numbers are unsupported. One exception is the unsigned char type. Performing arithmetic operations that use operands of type char is strongly discouraged.

Noncompliant Code Example

In this noncompliant code example, the result of the addition can overflow.

public int do_operation(int a, int b){
  // May result in overflow 
  int temp = a + b;
  return temp;
}

When the result of the addition is outside the range that can be represented as an int, the variable temp will contain an erroneous result. This problem does not occur when using short types, such as byte and short because the operands are promoted to type int before the operation is carried out. The language disallows storing the result of such operations in variables of types shorter than type int.

Compliant Solution (Bounds Checking)

Explicitly check the range of the operands of arithmetic operations; throw an ArithmeticException when overflow would occur.

Compliant Solution (Use a larger type and downcast)

For all integral types other than long, the next larger integral type can represent the result of any single integral operation. For example, operations on values of type int, can be safely performed using type long. Therefore, we can perform an operation using the larger type and range-check before down casting to the original type. Note, however, that this guarantee holds only for a one arithmetic operation; larger expressions without per-operation bounds checks may overflow the larger type.

Because type long is the largest primitive integral type, the only possible way to use a larger type and downcast is to perform arithmetic operations using the BigInteger class, range-check, and then convert the result back to type long.

This compliant solution converts two variables of type int to type long, performs the addition of the long values, and range checks the result before converting back to type int using a range-checking method. The range-checking method determines whether its input can be represented by type int. If so, it returns the downcast result; otherwise it throws an ArithmeticException.

Overview of Compliant Techniques

The three main techniques for detecting unintended integer overflow are:

• Pre-condition the inputs. Check the inputs to each arithmetic operator to ensure that overflow cannot occur. Throw an ArithmeticException when the operation would overflow if it were performed, otherwise perform the operation.
• Use a larger type and downcast. Cast the inputs to the next larger primitive integer type and perform the arithmetic in the larger size. Check each intermediate result for overflow of the original smaller type; throw an ArithmeticException if the range check fails. Note that the range check must be performed after each arithmetic operation. Downcast the final result to the original smaller type before assigning to the result variable. This approach cannot be use for type long, because long is already the largest primitive integer type.
• Use BigInteger. Convert the inputs into objects of type BigInteger and perform all arithmetic using BigInteger methods. Throw an ArithmeticException if the final result is outside the range of the original smaller type, otherwise convert back to the intended result type.

The "Pre-condition the inputs" technique requires different pre-condition for each arithmetic operation. This can be somewhat more difficult to understand than either of the other two approaches.

The "Use a larger type and downcast" technique is the preferred approach for the cases to which it applies. The checks it requires are simpler than those of the previous technique; it is substantially more efficient than using BigInteger.

The "Use BigInteger" technique is conceptually the simplest of the three techniques. However, it requires use of method calls for each operation in place of primitive arithmetic operators; this may obscure the intended meaning of the code. This technique will execute more slowly and will use more memory than either of the other techniques; performance degradation may be substantial.

Noncompliant Code Example

Either arithmetic operation in this noncompliant code example could produce a result that overflows the range representable by type int. When overflow occurs, the result will be incorrect.

public int multAccum(int oldAcc, int newVal, int scale) {
  // May result in overflow 
  return oldAcc + (newVal * scale);
}

Pre-condition the Inputs

The code example below shows the necessary pre-conditioning checks required for each arithmetic operation on arguments of type int. The checks for the other integral types are analogous.

static final preAdd(int left, int right

public int do_operation(int a, int b) throws ArithmeticException {
  return intRangeCheck((long) a + (long) b);
}

// Either perform a safe downcast to int, or throw ArithmeticException
public static int intRangeCheck(long val) throws ArithmeticException {
   if (valright > Integer0 ? left > Integer.MAX_VALUE || val - right : left < Integer.MIN_VALUE - right) {
     throw new ArithmeticException("OutInteger of rangeoverflow");
   }
}

static final preSubtract(int returnleft, (int right)val; // Value within range; downcast is safe
}

Compliant Solution (Bounds Checking)

This compliant solution range checks the operand values to ensure that the result does not overflow.

public int add(int a, int b) throws ArithmeticException {
  if( b > 0 ? a >  throws ArithmeticException {
  if (right > 0 ? left < Integer.MIN_VALUE + right : left > Integer.MAX_VALUE - b : a < Integer.MIN_VALUE - b + right) {
    throw new ArithmeticException("NotInteger in rangeoverflow");
  }
}

static final return a + b;  // Value within range so addition can be performed
}

public int add(int a, int b) throws ArithmeticException {
  if (((a > 0) && (b > 0) && (a > (Integer.MAX_VALUE - b))) 
   || ((a < 0) && (b < 0) && (a < (Integer.MIN_VALUE - b)))) {
 preMultiply(int left, int right) throws ArithmeticException {
  if (right>0 ? left > Integer.MAX_VALUE/right || left < Integer.MIN_VALUE/right :
       (right<-1 ? left > Integer.MIN_VALUE/right || left < Integer.MAX_VALUE/right :
         right == -1 && left == Integer.MIN_VALUE) ) {
    throw new ArithmeticException("NotInteger in rangeoverflow");
  }
}
else {
static final return a + b;  // Value within range so addition can be performed
}

Compliant Solution (Use BigInteger Class)

This compliant solution uses the BigInteger class as a wrapper to test for overflow.

public long do_operation(long a, long b) throws ArithmeticException {
  return longRangeCheck(BigInteger.valueOf(a).add(BigInteger.valueOf(b));
}

public long longRangeCheck(BigInteger valpreDivide(int left, int right) throws ArithmeticException {
  if ((left == Integer.MIN_VALUE) && (right == -1)) {
    throw new ArithmeticException("Integer overflow");
  }
}

static final preAbs(int a) throws ArithmeticException {
  if (a == Integer.MIN_VALUE) {
    throw new ArithmeticException("Integer overflow");
  }
}

static final preNegate(int a) throws ArithmeticException {
  if (val.compareTo(BigInteger.valueOf(Long.MAX_VALUE)) == 1 ||a == Integer.MIN_VALUE) {
    throw new     val.compareTo(BigInteger.valueOf(Long.MIN_VALUE)) == -1) {
    throw new ArithmeticException("Out of range for long"ArithmeticException("Integer overflow");
  }
  return val.longValue();
}

The BigInteger class eliminates integer overflows but at the cost of increased overhead.

Subtraction

Subtraction overflows when the first operand is a negative integer and the second operand is a large positive integer such that their difference is not representable as a value of type int. Subtraction also overflows when the first operand is positive and the second operand is negative and their difference is not representable as a value of type int.

Note that the "Use a larger type and downcast" approach suffices to avoid overflow for subtraction.

Multiplication

Multiplication overflows whenever the sum of the number of bits required to represent its operands is larger than the number of bits in the result type. Once again, the "Use a larger type and downcast" approach suffices to avoid overflow.

Division

Although Java throws a java.lang.ArithmeticException for division by zero, it fails to do so when dividing Integer.MIN_VALUE by -1. Rather, Java produces Integer.MIN_VALUE in this case, because the result is -(Integer.MIN_VALUE) = Integer.MAX_VALUE + 1)) which overflows to Integer.MIN_VALUE; this may surprise many programmers.

Once again, the "Use a larger type and downcast" approach suffices to avoid overflow. In some cases, checking for the specific case above may be more efficient.

Remainder Operator

The Java remainder operator does not present overflow issues. However, it has the following behavior for corner cases:

• When the modulo of Integer.MIN_VALUE with -1 is taken, the result is always 0.

• When the right-hand operand is zero, the integer remainder operator % will throw an ArithmeticException.

• The sign of the remainder is always the same as that of the dividend. For example, -3 % -2 results in the value -1. This behavior may be unexpected.

Refer to guideline INT02-J. Remember that the remainder operator may return a negative result value for more details.

Unary Negation

The result of negating Integer.MIN_VALUE is Integer.MIN_VALUE, because -Integer.MIN_VALUE is logically equivalent to Integer.MAX_VALUE+1 which overflows to Integer.MIN_VALUE.

Once again, the "Use a larger type and downcast" approach suffices to avoid overflow. In some cases, checking for the specific case above may be more efficient.

Absolute Value

A related pitfall is the use of the Math.abs() method that takes a parameter of type int and returns its absolute value. Because of the asymmetry between the two's complement representation of negative and positive integer values (Integer.MAX_VALUE is 2,147,483,647 and Integer.MIN_VALUE is -2,147,483,648, which means there is one more negative integer than positive integers), there is no equivalent positive value (+2,147,483,648) for Integer.MIN_VALUE. Consequently, the Math.abs() returns Integer.MIN_VALUE when the value of its argument is Integer.MIN_VALUE; this may surprise many programmers.

Once again, the "Use a larger type and downcast" approach suffices to avoid overflow. In some cases, checking for the specific case above may be more efficient.

Shifting

The shift operation in Java has the following properties:

• The right shift is an arithmetic shift.

• The types boolean, float and double cannot use the bit shifting operators.

• If the value to be shifted is of type int, only the five lowest-order bits of the right-hand operand are used as the shift distance. That is, the shift distance is the value of the right-hand operand masked by 31 (0x1F). This results in a value modulo 31, inclusive.

• Wiki Markup
  When the value to be shifted (left-operand) is of type {{long}}, only the last 6 bits of the right-hand operand are used to perform the shift. The shift distance is the value of the right-hand operand masked by 63 (0x3D) \[[JLS 2003|AA. Bibliography#JLS 03]\]. (That is to say, the shift value is always between 0 and 63. If the shift value is greater than 64, then the shift is {{value % 64}}.)

Refer to guideline INT05-J. Use shift operators correctly for further details about the behavior of the shift operators.

Noncompliant Code Example

This noncompliant code example attempts to shift the value {{i}} of type {{int}} until, after 32 iterations, the value becomes 0. Unfortunately, this loop never terminates because an attempt to shift a value of type {{int}} by 32 bits results in the original value rather than the value 0 \[[Bloch 2005|AA. Bibliography#Bloch 05]\]. 

int i = 0;
while ((-1 << i) != 0)
  i++;

Compliant Solution

This compliant solution initially sets the value val to -1 and repeatedly shifts the value by one place on each successive iteration.

for (int val = -1; val != 0; val <<= 1) { /* ... */ }

Noncompliant Code Example (Concurrent Code)

This noncompliant code example uses an AtomicInteger which is part of the concurrency utilities. The concurrency utilities do not enforce checks for integer overflow.

class InventoryManager {
  private final AtomicInteger itemsInInventory = new AtomicInteger(100);

  //...
  public final void returnItem() {
    itemsInInventory++;
  }
} 

Consequently, itemsInInventory may wrap around to Integer.MIN_VALUE after the increment operation.

Noncompliant Code Example (Concurrent Code—TOCTOU Condition in Check)

This noncompliant code example installs a check for integer overflow; however, there is a time-of-check-time-of-use vulnerability between the check and the increment operation.

class InventoryManager {
  private volatile int itemsInInventory = 100;

  // ...

  public final void returnItem() {
    if (itemsInInventory == Integer.MAX_VALUE) {
      throw new IllegalStateException("Out of bounds");
    }
    itemsInInventory++;
  }
}

Compliant Solution (java.util.concurrent.atomic classes)

The java.util.concurrent utilities can be used to atomically manipulate a shared variable. This compliant solution defines itemsInInventory as a java.util.concurrent.atomic.AtomicInteger variable, allowing composite operations to be performed atomically.

class InventoryManager {
  private final AtomicInteger itemsInInventory = new AtomicInteger(100);

  public final void returnItem() {
    while (true) {
      int old = itemsInInventory.get();
      if (old == Integer.MAX_VALUE) {
        throw new IllegalStateException("Out of bounds");
      }
      int next = old + 1; // Increment
      if (itemsInInventory.compareAndSet(old, next)) {
        break;
      }
    } // end while
  } // end removeItem()
} 

...

}

Note that these pre-conditioning checks can be simplified when the original type was char. Because the range of type char includes only positive values, all comparisons with negative values may be omitted.

Compliant Solution (Pre-condition the inputs)

public int multAccum(int oldAcc, int newVal, int scale) throws ArithmeticException {
  preMultiply(newVal, Scale);
  final int temp = newVal * scale;
  preAdd(oldAcc, temp);
  return oldAcc + temp;
}

Use a Larger Type and Downcast

For all integral types other than long, the next larger integral type can represent the result of any single integral operation. For example, operations on values of type int, can be safely performed using type long. Therefore, we can perform an operation using the larger type and range-check before down casting to the original type. Note, however, that this guarantee holds only for a one arithmetic operation; larger expressions without per-operation bounds checks may overflow the larger type.

This approach cannot be applied for type long because long is the largest primitive integral type. Use the "Use BigInteger" technique when the original variables are of type long.

Compliant Solution (Use a Larger Type and Downcast)

This compliant solution shows the implementation of a method for checking whether a long value falls within the representable range of they int. The implementations of range checks for the smaller primitive integer types are exactly analogous.

public long intRangeCheck(long value) throws ArithmeticOverflow {
  if ((value < Integer.MIN_VALUE) || (value > Integer.MAX_VALUE)) {
    throw new ArithmeticException("Integer overflow");
  }
  return value;
}

public int multAccum(int oldAcc, int newVal, int scale) throws ArithmeticException {
  final long res = 
    intRangeCheck(((long) oldAcc) + intRangeCheck((long) newVal * (long) scale));
  return (int) res; // safe down-cast
}

Use BigInteger

Type BigInteger is the standard arbitrary-precision integer type provided by the Java standard libraries. The arithmetic operations implemented as methods of this type cannot themselves overflow; instead, they produce the numerically correct result. As a consequence, compliant code performs only a single range check — just before converting the final result to the original smaller type. This property provides conceptual simplicity. An unfortunate consequence of this technique is that compliant code must be written using method calls in place of primitive arithmetic operators; this may obscure the intent of the code.

Note that operations on objects of type BigInteger may be significantly less efficient than operations on the original primitive integer type. Whether this loss of efficiency is important will depend on the context in which the code is used.

Compliant Solution (Use BigInteger)

private static final BigInteger bigMaxInt = BigInteger.valueOf(Integer.MAX_VALUE);
private static final BigInteger bigMinInt = BigInteger.valueOf(Integer.MIN_VALUE);

public BigInteger intRangeCheck(BigInteger val) throws ArithmeticException {
  if (val.compareTo(bigMaxInt) == 1 ||
          val.compareTo(bigMinInt) == -1) {
    throw new ArithmeticException("Integer overflow");
  }
  return val;
}

public int multAccum(int oldAcc, int newVal, int scale) throws ArithmeticException { 
  BigInteger product =
    BigInteger.valueOf(newVal).multiply(BigInteger.valueOf(scale));
  BigInteger res = intRangeCheck(BigInteger.valueOf(oldAcc).add(product));
  return res.intValue(); // safe conversion
}

Exceptions

INT00-EX1: Depending on circumstances, integer overflow may be benign. For instance, the Object.hashcode() method may return all representable values of type int; further, many algorithms for computing hashcodes intentionally allow overflow to occur.

...