Java에서 오버플로를 방지 할 수 있습니까?

Question

TopCoder에서 문제가 발생했습니다. 하나의 계산 단계에서 오버플로가 발생할 수 있다고 분석은 솔루션이 너무 오래 버티다 고 말합니다. 나는 이것이 왜 효과가 있을지 이해하지 못한다.

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

변수를 pos 및 MODULO은 모두 내가 오래 캐스트의 도움은 무엇입니까 궁금하네요 범위 -2147483648과 2147483647
에서 될 수 있을까? 감사!

Answer 1

Java의 경우 long은 항상 64 비트입니다. 서로 다른 폭의 두 가지 양으로 산술 연산을 수행하면 Java의 사양에 따르면 산술 연산이 더 큰 데이터 유형으로 수행됩니다.

따라서 pos을 long으로 캐스팅하면 모든 후속 연산이 64 비트 long을 사용하여 수행됩니다. 마지막 단계는 32 비트 값에 대한 mod이므로 결과는 32 비트 내에 맞을 수 있으므로 최종 캐스트는 정밀도를 잃지 않습니다.

Answer 2

코드를 약간 리팩토링하고 모든 표현식을 자체 줄에 유지하면 더 명확 해집니다.

var에 pos 및 MODULO 모두 범위 -2147483648과 2147483647

공지 사항에서 할 수있는, 즉 정확하게 : Integer.MAX_VALUE == 2147483647.

이

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; 단계에서 정확하게 발생 가장자리 케이스 (pos 가능한 한 큰 MODULO)를 가지고가는 것은 좋은 예이다. MODULO가 될 수

단지 약 Integer.MAX_VALUE, 즉 행 1 정수 (정수 오버플로)보다 큰 값을 반환 만큼 약간 첨가 의미한다.

마찬가지로 이전 단계 (mod = pos2 % MODULO)에서 mod이 1 일 수 있으므로 오버플로가 발생할 수 있습니다.

캐스팅을 long으로하면 오버플로가 염려없이 합계가 발생합니다. 물론 결과가 int이 되려면 캐스트가 문제가 될 수 있습니다.

다행히도 마지막 표현식의 값 (sum % MODULO)이 0과 MODULO 사이이므로 문제가되지 않습니다. 그리고 MODULO은 최대로 Integer.MAX_VALUE (2147483647) 일 수 있으므로 유효한 정수이므로 int으로 다시 캐스팅 할 수 있습니다.