Может ли это предотвратить переполнение в Java?

Question

Я искал проблему в TopCoder. На одном этапе расчета может быть переполнение, анализ говорит, что решение слишком долгое. Я не понимаю, почему это сработает.

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

Переменные pos и MODULO оба могли быть из диапазона -2147483648 и 2147483647
Я интересно, что это поможет литья долго? благодаря!

Answer 1

В Java, long s всегда 64-битные величины. Когда арифметика выполняется с двумя величинами различной ширины, спецификация Java говорит, что арифметика выполняется с более крупным типом данных.

Таким образом, путем литья pos в long, все последующие арифметические операции выполняются с использованием 64-разрядных long. Поскольку последний шаг заключается в модификации по сравнению с 32-битным значением, результат может поместиться в пределах 32 бит точно, так что конечный результат не теряет точности.

Answer 2

Я думаю, что это станет понятнее, если вы немного реорганизуете код и сохраните каждое выражение в своей собственной строке.

Значение переменной pos и MODULO может быть оба из диапазона -2147483648 и 2147483647

Обратите внимание, что именно: Integer.MAX_VALUE == 2147483647. Принимая краевой случай (pos и MODULO как можно больше), является хорошим примером:

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); 
} 

Выход:

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

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

Итак, как вы можете видеть, эта проблема возникает именно в sum = mod + MODULO; шаге.

MODULO Как может быть примерно Integer.MAX_VALUE, это будет означать, добавив, как мало, как 1 к нему будет возвращать значение больше, чем целое число (целое число от переполнения).

Как, на предыдущем этапе (mod = pos2 % MODULO), у вас есть mod может быть 1, может произойти переполнение.

Кастинг до long позволит получить сумму, не опасаясь переполнения. Конечно, бросок будет проблемой, если мы хотим, чтобы результат был int.

К счастью, это не проблема здесь, потому что значение последнего выражения (sum % MODULO) находится в пределах 0 и MODULO. И так как MODULO может быть не более Integer.MAX_VALUE (2147483647), тогда оно является действительным целым числом и, таким образом, может быть отменено до int.