정수 연산 기능을 이해하는 데 도움이 필요합니다.

Question

누군가 나를 부탁해이 기능을 설명 할만큼 친절하십니까?

int overflow(int x, int y) 
{ 
    int result, non_overflow, overflow, result_sign, mask; 

    result = x + y; 
    result_sign = result >> 31; //Need help starting from here... I know 
           //it is shifting 31 bits... but why?? 
    non_overflow = ((x^y) | ~(y^result)) >> 31; 
    overflow = ~non_overflow; 

    mask = overflow << 31; 

    return (non_overflow & result) | (overflow & (result_sign^mask)); 
} 

Answer 1

은 결과의 크기보다 작 INT_MAXINT_MIN 이상인지를 나타내는 가산 연산을위한 정수 오버플로 "플래그"를 계산하는 것. int은 32 비트이고 2의 보수이며 부호있는 숫자의 오른쪽 시프트는 고위 비트를 복제하는 "산술"시프트라고 가정합니다. 안전한 가정은 없습니다.

x과 y의 부호가 같지만 결과의 부호가 반대이면 결과가 오버플로됩니다. 그것이 컴퓨팅의 전부입니다. 너무 복잡 할 필요가 없습니다. 우리가 원하는 경우

(x^y) < 0 && (x^result) < 0 /* (A^B)<0 iff A and B have opposite sign */ 

: 또한이 중요한 예외를 생성하지 않고 더 남았습니다 패리티 비트는이 표현은 원래의 코드와 같은 정신 부호 비트를 조작하여 작동합니다,가 없다고 가정

잘 정의 된 동작에 의존하는 것에 대해 까다로울 경우 x + y은 불법 일 경우 결과가 오버플로 될 수 있습니다. C 표준을 따르는 시스템은 오버플로 (또는 자체 파괴 등)시 프로그램을 종료 할 수 있으므로 처음부터 그렇게하지 않아야합니다.

우리가 수행 할 테스트는

x + y > INT_MAX 
x + y < INT_MIN 

직접 x와 y 사이에 안전 운전 없습니다 있습니다. 우리는 방정식의 반대편으로 움직여야합니다. 이것은 방정식의 반대와 빼기를 의미합니다. 그것은 INT_MAX에서 양수를 빼거나 INT_MIN에서 음수를 빼기 만 안전, 그래서 우리는 다음을 수정할 수 있습니다

y > INT_MAX - x 
y < INT_MIN - x 

그것을 할 수있는 가장 안전한 방법은 다음

x < 0? (y < INT_MIN - x) : (y > INT_MAX - x); 

---

입니다 편집 : Woops, 나는 함수가 오버 플로우 플래그로 무엇을했는지 짐작하지 않았다. 오버플로가 없으면 결과를 반환하고 양수 오버플로가있는 경우 INT_MAX을 반환하고 음수 오버플로가 발생하는 경우 INT_MIN을 반환합니다. 다시 말해서, 그것은 덧셈을 포화시키는 것입니다. 그것이하는 방식은 약간 복잡한 데, 저자가 가지를 제거하는 데 어려움을 겪은 것처럼 보입니다. 그러나 오버 플로우는 일반적으로 발생하지 않으며 예측 가능한 분기는 많은 산술보다 저렴하므로 if … else을 사용하여보다 직접적인 구현을 시도해 볼 가치가 있습니다.