PAT-A 1065. A+B and C (64bit)

用到了计算机组成原理的知识，两个大整数相加时发生溢出，判断溢出后的数字求解。

A 1065

Given three integers A, B and C in [-263, 263], you are supposed to tell whether A+B > C.

Input Specification:

The first line of the input gives the positive number of test cases, T (<=10). Then T test cases follow, each consists of a single line containing three integers A, B and C, separated by single spaces.

Output Specification:

For each test case, output in one line “Case #X: true” if A+B>C, or “Case #X: false” otherwise, where X is the case number (starting from 1).

Sample Input:

3
1 2 3
2 3 4
9223372036854775807 -9223372036854775808 0

Sample Output:

Case #1: false
Case #2: true
Case #3: false

题目大意

给出三个整数A、B、C，如果A+B>C，输出ture，否则输出false。其中A、B、C的取值范围是[-2⁶³, 2⁶³]。

思路

参考《算法笔记》

long long的取值范围是[-2⁶³, 2⁶³)，因此A和B相加可能会溢出，不能直接判断大小。在计算机组成原理中，如果两个正数相加发生溢出，则和为负数；如果两负数相加发生溢出，则和为正数。可以分析：

当A+B>=2⁶³时，显然有A+B>C，A+B会因超过long long的正向最大值而发生正溢出，由于题目给定的A和B最大均为2⁶³-1，故A+B最大为2⁶⁴-2，因此long long存储正溢出后的值的区间为[-2⁶³, -2]，由(2⁶⁴-2)%(2⁶⁴)=-2可得右边界，所以当A>0 && B>0 && A+B<0 时，输出true。
当A+B<-2⁶³时，显然有A+B<C成立，但是A+B会因超过long long 的负向最小值而发生负溢出。由于题目给定的A和B的最小值为-2⁶³，故A+B最小为-2⁶⁴，因此使用long long 存储负溢出后的值的区间为[0, 2⁶³)。所以当 A<0 && B<0 &&="" a+b="">=0时为负溢出，输出false。
当没有溢出的情况下，正常判断。

注意点：

算法笔记指出，测试数据中没有出现A、B取2⁶³的情况，题目给的数据范围应该是[-2⁶³, 2⁶³)。
A+B的计算结果必须存放到long long中才可以与C进行比较。

AC代码

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long ll;

int main() {
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        ll res = a + b;
        bool ans;
        // 判断A+B
        if (a > 0 && b > 0 && res < 0) {
            ans = 1;
        }
        else if (a < 0 && b < 0 && res >= 0) {
            ans = 0;
        }
        else if (res > c) {
            ans = 1;
        }
        else {
            ans = 0;
        }

        if (ans) {
            cout << "Case #" << i << ": true\n";
        }
        else {
            cout << "Case #" << i << ": false\n";
        }
    }

    return 0;
}