1065 A+B and C (64bit) (20分)/数据溢出特性

题目

Given three integers A, B and C in [−263,2​63], 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


变量溢出特性

由于不是科班出身,没学过计算机组成原理等等基础课,不了解变量存储机制。只能想到常规的大数运算的方法,也就是《算法笔记》中介绍的方法。
但是觉得这样一个题用那种方法总觉得挺麻烦,就去看了柳神的博客,发现是利用变量溢出的特性。于是去学习了一些计算机存储的相关知识——“原码、补码”。

异同点

他们都是把第一位作为符号位,0表示正,1表示负。
原码的数值位就是十进制数的二进制表示。
在计算机系统中,正整数的补码是其二进制表示,与原码相同;求负整数的补码,将其原码除符号位外的所有位取反(0变1,1变0,符号位为1不变)后加1。

目的

计算机数值一律用补码来存储,这么做是为了便于计算,因为原码的符号位会导致直接计算出错。如:-1(1000…001)+1(0000…001)= -2(1000…010),显然是错误的。

再看数据溢出

下图是以补码定义式为基础,沿数轴列出典型的真值、原码与补码表示。负数补码表示的范围比原码稍宽,多一种数码组合,是由于在补码表示中,数 0只有一种表示。因此,若n为整数,表示范围为(-2n~2n-1)。1065 A+B and C (64bit) (20分)/数据溢出特性
这张图就解释了数据溢出的特性。比如int型,最大为231-1,其补码为0111…11,再加1就溢出,补码变成1000…00,表示-231

回到本题

如果A > 0, B < 0 或者 A < 0, B > 0,A+B是不可能溢出的
如果A > 0, B > 0,sum可能会溢出,sum范围理应为(0, 264 – 2],溢出得到的结果应该是[-264, -2]是个负数,所以A+B < 0时候说明溢出了。
同理A<0, B<0时A+B>=0说明溢出。注意当A=B=−263时,A+B=0。

问题

写了如下代码但是有两个测试点不能通过。

#include<cstdio>
using namespace std;
int main() {
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		long long a, b, c;
		scanf("%lld%lld%lld", &a, &b, &c);
		printf("Case #%d: ", i);
		if (a > 0 && b > 0 && a+b < 0) printf("true\n");
		else if (a < 0 && b < 0 && a+b >= 0) printf("false\n");
		else printf("%s\n", a+b > c ? "true" : "false");
	}
	return 0;
}

1065 A+B and C (64bit) (20分)/数据溢出特性
然后看到别人的代码是另写了一个long long变量存储a+b,于是就AC了,但是不明白这是为什么…

#include<cstdio>
using namespace std;
int main() {
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		long long a, b, c;
		scanf("%lld%lld%lld", &a, &b, &c);
		printf("Case #%d: ", i);
		long long sum = a + b;
		if (a > 0 && b > 0 && sum < 0) printf("true\n");
		else if (a < 0 && b < 0 && sum >= 0) printf("false\n");
		else printf("%s\n", sum > c ? "true" : "false");
	}
	return 0;
}

long double解法

但是也有博主认为上面的做法也不正确,因为题目给出的A,B,C的最大值已经超过了long long的范围,2^ 63是long long中无法正确解释的,被错误解释为-2^ 63。因此即使可以通过测试点,仍不是正确的做法。
例如输入:
0 9223372036854775808 1 会判断A + B < C;显然是不正确的。但可能由于测试数据并没有出现这样的数据,因此AC了。
可使用更大的long double类型存储,它有更高的精度和表示范围。
注: 输入输出时,使用格式字符%llf。

double和long double都是ANSI C标准的浮点数。但ANSI C并未规定long double的确切精度。所以对于不同平台可能有不同的实现。有的是8字节,有的是10字节,有的是12字节或更多。一般来说long double的精度要高于double, 至少相等,就像int和long int一样。但同一平台也可能不一样。

double类型的精度为15~16位,long double实际精度视编译环境或电脑系统而定。
所以这种解法可能不具有普适性。

#include <cstdio>
int main()
{
    int n;
    scanf("%d", &n);
    for( int i = 1; i <= n; ++i )
    {
        long double A, B, C;
        scanf("%llf %llf %llf", &A, &B, &C);
        printf("Case #%d: %s\n", i, A + B > C ? "true":"false");
    }
}
1065 A+B and C (64bit) (20分)/数据溢出特性1065 A+B and C (64bit) (20分)/数据溢出特性 正在拼命学习的大学狗 发布了33 篇原创文章 · 获赞 5 · 访问量 2273 私信 关注
上一篇:[NOIP2011 普及组] 表达式的值


下一篇:P1308 [NOIP2011 普及组] 统计单词数