Why does a calculation with positive numbers give a negative result?

Question

Why does this one count (100 * 22118400) / 44954676 in Java gives a negative number?

-46

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        System.out.println(((100 * 22118400) / 44954676));
    }
}

Example in Ideone

Answer 1

Actually the problem occurs in the expression 100 * 22118400. It exceeds the positive value limit of an integer and Java has chosen, probably for performance, to assume a behavior instead of generating an exception of overflow. This behavior is just to count the bits that achieve and take the resulting value even if it is not what is expected.

In this case when it goes from 2147483647 (2 to 31 minus 1), it changes the bit more significant is the sign, after all the type int is Signed. The thirty-second bit is the sign. Then this expression turns negative and affects the rest of the expression. That is, it does the math ignoring that there is a bit and that it should not be changing when an account is attempted.

Since Java does not have a specific construction in the language to establish that the verification should be done (C# has), you should do it on your own, probably creating a method that should be used everywhere instead of the operator. Another partial solution is to use everything long that works until the limit of the long. Or use the BigInteger which accepts any size. In some cases a floating point type may be useful. None is very good. So the real solution is to remember this and be selective when there’s risk.

Answer 2

The operation 100 x 22118400 results in a value exceeding capacity (2³¹ -1 or 2147483647) that a whole of 32-bits can bear, which causes a Integer Overflow, an overflow. Normally the JVM does not issue any warning or exception about this, according to the documentation, 2.11.3. Arithmetic Instructions:

The JVM does not indicate overflow during operations in types of dice whole. The only operations with integer numbers that can exceptions are split instructions (iDiv and ldiv) and the instructions from the rest of the entire division (Go and irem), who launch one ArithmeticException if the divisor is zero.

The result negative of this operation is due to the return come in format Complement to two, which is used to represent negative integers, the documentation quotes the following, 15.17.1. Multiplication Operator:

If a overflow occur in integer multiplication, the result is the least significant bits, represented in the format complement of two. As a result, if it occurs overflow, the result signal may not be the same as the mathematical product of the two values of operands.

Considering the code below:

public static void main (String[] args) throws java.lang.Exception {
    // 100 * 22118400 = -2083127296, quando divido por 44954676, resulta em -46..
    System.out.println(((100 * 22118400) / 44954676)); 
}

Binary Representation

The number 100 in binary is represented by 1100100, and 22118400 is 1010100011000000000000000. In the binary multiplication we obtain as a result 1000001111010110000000000000, that when converted to decimal results 2211840000, the expected value. The illustration below shows how the multiplication was done:

Resolution

To get around this problem one should use a guy offering greater storage capacity, Long (2 ³ -1 or 9223372036854775807L) is an example:

public static void main (String[] args) throws java.lang.Exception {
    System.out.println(((100 * 22118400L) / 44954676)); // 49, correto!
}

DEMO

If you don’t feel safe using a guy like Long, or don’t know what value a variable can take, consider using the class BigInteger, theoretically there is no limit, will be allocated the amount of memory that is necessary to keep the information received, of course there are limits practical as the memory availability, but it is something quite difficult to happen.

An example of the use of BigInteger:

public static void main (String[] args) throws java.lang.Exception {
    BigInteger valor1 = new BigInteger("100");
    BigInteger valor2 = new BigInteger("22118400");
    BigInteger valor3 = new BigInteger("44954676");

    BigInteger mul = valor1.multiply(valor2);
    BigInteger divisao = soma.divide(valor3);
    System.out.printf("A multiplicação entre %d e %d resulta %d\n", valor1, valor2, mul);
    System.out.printf("A divisão entre %d e %d resulta %d", soma, valor3, divisao);
}

DEMO

Detection of Overflows

In versions prior to Java 8, there are no methods natives that help to detect Overflows, what it is up to you to do this. One of the ways of detection is to check whether the value of a variable of type Long is within the acceptable range of whole type, in other words:

public static int mult(int a, int b) throws ArithmeticException {
    long resultado = a * (long) b;    
    if (resultado > Integer.MAX_VALUE || resultado < Integer.MIN_VALUE){
        throw new ArithmeticException("Integer overflow");
    }
    return (int) resultado;
}

And use it as follows:

public static void main (String[] args) throws java.lang.Exception {
    int valor1 = 100;
    int valor2 = 22118400;
    int valor3 = 44954676;

    int mul = mult(valor1, valor2);
    int divisao = soma / valor3;
    System.out.printf("A soma entre %d e %d resulta %d\n", valor1, valor2, mul);
    System.out.printf("A divisão entre %d e %d resulta %d", soma, valor3, divisao);
} 

The above code will generate the following exception:

Exception in thread "main" java.lang.Arithmeticexception: Integer overflow

DEMO

In Java 8, methods have been added who carry out the arithmetic operations and if any Oveflows/Underflows, an exception ArithmeticException is launched. The following methods have been added in the class java.lang.Math:

Int                                            Long
-----------------------------------------------------------------------------------------------
public static int addExact(int x, int y)       public static long addExact(long x, long y)
public static int decrementExact(int a)        public static long decrementExact(long a)
public static int incrementExact(int a)        public static long incrementExact(long a)
public static int multiplyExact(int x, int y)  public static long multiplyExact(long x, long y)
public static int negateExact(int a)           public static long negateExact(long a)
public static int subtractExact(int x, int y)  public static long subtractExact(long x, long y)
public static int toIntExact(long value)

Follow an example:

public static void main (String[] args) throws java.lang.Exception {
    int valor1 = 100;
    int valor2 = 22118400;
    int valor3 = 44954676;

    int mul = Math.multiplyExact(valor1, valor2);
    int divisao = Math.floorDiv(soma, valor3);
    System.out.printf("A soma entre %d e %d resulta %d\n", valor1, valor2, mul);
    System.out.printf("A divisão entre %d e %d resulta %d", soma, valor3, divisao);
}

The above code will generate the following exception:

Exception in thread "main" java.lang.Arithmeticexception: integer overflow

DEMO

References

• Detect or Prevent integer overflow
• OWASP - Integer overflow
• Overflow And Underflow of Data Types in Java

---

By way of curiosity, the Youtube in December 2014 was forced to use an integer of 64-bits (9223372036854775808), after the video PSY - GANGNAM STYLE (강남스타일) M/V, reached the limit of views (2147483647, maximum value of an integer of 32-bits).

_{Image credits: RST}