JAVA integer overflow intrigue

Question

The 1st for loop in the below code does not find the maximum correctly due to an overflow. However, the 2nd for loop does. I used godbolt.com to look at the byte codes for this program which showed that to determine which number is greater the 1st for loop uses an isub and the 2nd for loop uses an if_icmple. Makes sense. However, why is the if_icmple able to successfully do this comparison since it too at some point must do a subtraction (which I would expect to produce an overflow)?

public class Overflow {
   public static void main(String[] args) {
      int[] nums = {3,-2147483648, 5, 7, 27, 9};
       
      int curMax = nums[0];
      for (int num : nums) {
         int diff = curMax - num; 
         if (diff < 0) {
            curMax = num;
         }
      }
      System.out.println("1) max is " + curMax);
       
      curMax = nums[0];
      for (int num : nums) {
         if (num > curMax) {
            curMax = num;
         }
      }  
      System.out.println("2) max is " + curMax);        
   }   
}

The output is

max is -2147483648
max is 27

Why should the second produce an overflow, too? That large negative number is a perfectly normal int that can be compared, the problem is only when you do curMax - num, i.e. 3 - -2147483648, i.e. 3 + 2147483648, which overflows and becomes negative. — tobias_k
– tobias_k, Commented Apr 8, 2022 at 15:19
I don't know Java's virtual machine but surely the comparison is discarding the result and only looking for the sign of the difference. — shawnt00
– shawnt00, Commented Apr 8, 2022 at 15:22
Besides the sign bit, there indeed also exists an overflow flag flag. (like in neg - pos == pos).. — Joop Eggen
– Joop Eggen, Commented Apr 8, 2022 at 15:42
JAVA limits integers to 32 bits. I am assuming this is so the JVM can run a 32-bit processor. So I would think to compare the two numbers the processor at some point has to subtract them to see which is larger. — rainerpm
– rainerpm, Commented Apr 8, 2022 at 15:45

user555045 · Accepted Answer · 2022-04-08 15:36:38Z

3

Let's say that comparison is implemented using subtraction. Contrary to various other opinions here, I'd say that is highly likely. Eg cmp on x86 is just a subtraction that does not update its destination register, only the flags. Various other (but maybe not all) processors that have a flags register also work that way. In the rest of this answer I'll use x86 as a representative processor for examples.

However, there is an incorrect assumption made implicitly by your code: a comparison is not equivalent to a subtraction followed by checking the sign, it is equivalent to a subtraction followed by checking some combination of the Zero, Sign, and Overflow flags. For example, if you implement if (num > curMax) using some cmp followed by jle (to skip the body of the if when the condition is false), then jle does this:

Jump short if less or equal (ZF=1 or SF≠ OF).

Expressing the condition SF≠ OF directly in Java is not so easy. But the JVM itself has no such problem, it can use a comparison (or, equivalently, subtraction) followed by exactly the right kind of conditional jump.

There are some less-fortunate processors that do not have such as full set of conditional jumps as x86 has, but even in that case, the JVM has a lot more options than you do.

The option that the JVM does not have though, is implementing comparison incorrectly.

answered Apr 8, 2022 at 15:36

user555045

65.8k6 gold badges95 silver badges180 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Holger Over a year ago

Even in the unlikely case that the CPU has no suitable set of conditions, it must have an idiomatic way of performing such a comparison, which the JVM can use. But the question is obviously targeting a CPU which has it.

Louis Wasserman · Accepted Answer · 2022-04-08 16:28:43Z

0

However, why is the if_icmple able to successfully do this comparison since it too at some point must do a subtraction (which I would expect to produce an overflow)?

It doesn't need to do a subtraction. It just needs to do a comparison. Comparisons don't have to involve subtraction, certainly not in the CPU.

Of course, we can also take alternate steps to deal with overflow. Here is one simple approach:

int cmp(int a, int b) {
  boolean aNeg = (a >>> 31) != 0;
  boolean bNeg = (b >>> 31) != 0;
  if (aNeg != bNeg) {
    return aNeg ? -1 : 1;
  }
  int diff = a - b; // subtracting two numbers with the same sign can't overflow
  return (diff == 0) ? 0 : (diff < 0) ? -1 : 1; 
}

All Java has to do is compile if_icmple to something like this, or whatever other instruction is appropriate on the target CPU. Using bytecode means Java can leave that up to the runtime to get right for the target CPU, whatever's fastest in such an environment -- using the overflow bit, doing something like this, whatever.

edited Apr 8, 2022 at 16:28

answered Apr 8, 2022 at 15:25

Louis Wasserman

200k26 gold badges367 silver badges437 bronze badges

2 Comments

rainerpm Over a year ago

How would a CPU (specifically a 32-bit CPU) do this comparison without doing a subtract? Even a CPU compare instruction does a subtract (it just doesn't store the result).

Louis Wasserman Over a year ago

Any number of ways. If nothing else, you can flip the top bits to reduce it to an unsigned comparison, and then directly loop through the bits.

Collectives™ on Stack Overflow

JAVA integer overflow intrigue

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related