Could this prevent overflow in Java?

Question

I was coding a problem in TopCoder. In one calculating step there could be overflow for, the analysis says the solution is cast too long. I don't understand why this would work.

int normalize(int pos) {
    return (int) (((long) pos % MODULO + MODULO) % MODULO);
}

The variables pos and MODULO could both be from the range -2147483648 and 2147483647
I'm wondering what's the help of casting to long? thanks!

Answer 1

In Java, longs are always 64-bit quantities. When arithmetic is performed with two quantities of differing widths, Java's specification says that the arithmetic is done with the larger datatype.

Thus, by casting pos to a long, all subsequent arithmetic is done using 64-bit longs. Since the last step is to mod against a 32-bit value, the result can fit within 32 bits for sure, so the final cast loses no precision.

Answer 2

I think it becomes clearer if you refactor the code a little and keep every expression in its own line.

The var pos and MODULO could both be from the range -2147483648 and 2147483647

Notice that, precisely: Integer.MAX_VALUE == 2147483647. Taking the edge case (pos and MODULO as big as possible) is a good example:

public static void main(String[] args) {
    System.out.println("result: "
            + normalize(Integer.MAX_VALUE-1, Integer.MAX_VALUE));
    System.out.println();
    System.out.println("result: "
            + normalizeWithoutLongCast(Integer.MAX_VALUE-1, Integer.MAX_VALUE));
}

static int normalize(int pos, int MODULO) {
    System.out.println("normalize()");
    long mod = pos % MODULO;
    System.out.println("mod: "+mod);
    long sum = mod + MODULO; // this is where the overflow can occur
    System.out.println("sum: "+sum);
    return (int) (sum % MODULO);
}

static int normalizeWithoutLongCast(int pos, int MODULO) {
    System.out.println("normalizeWithoutLongCast()");
    int mod = pos % MODULO;
    System.out.println("mod: "+mod);
    int sum = mod + MODULO; // this is where the overflow can occur
    System.out.println("sum: "+sum);
    return (int) (sum % MODULO);
}

Output:

normalize()
mod: 2147483646
sum: 4294967293
result: 2147483646

normalizeWithoutLongCast()
mod: 2147483646
sum: -3
result: -3

So, as you can see, the problem occurs exactly in the sum = mod + MODULO; step.

As MODULO can be just about Integer.MAX_VALUE, that would mean adding as little as 1 to it would return a value larger than an integer (an integer overflow).

As, in the step before (mod = pos2 % MODULO), you have that mod can be 1, the overflow can occur.

Casting to long will allow the sum to happen without fearing the overflow. Of course, the cast would be a problem if we wanted the result to be an int.

Luckily, that is not an issue here because the last expression's value (sum % MODULO) is between 0 and MODULO. And as MODULO can be at most Integer.MAX_VALUE (2147483647) it is then a valid integer and thus safe to be casted back to int.