H 题为什么错误的代码也能够 AC

题目

输入 一个整数,x

输出 一个非负整数,|x|

数据范围 x 在 int 范围内,即 x∈[−2^31,2^31−1]

在做这道题的时候,有的同学发现,使用如下代码会导致 WA:

// 第一段代码
#include <stdio.h>
#include <stdlib.h>
int main(void) 
{ 
    long long x, y;
    scanf("%lld", &x); 
    y = abs(x);
    printf("%lld", y);
    return 0;
}

但是使用一段看似与上面相同的代码就能够 AC(虽然它也是错误的代码):

// 第二段代码
#include <stdio.h>
#include <stdlib.h>
int main(void) 
{ 
    long long x;
    scanf("%lld", &x); 
    printf("%lld", abs(x));
    return 0;
}

为什么第一段代码会 WA?

执行第一段代码并输入 -2147483648(-2^31),程序会返回-2147483648,显然这并不是正确的输出。

其原因在于,在 C99 中,abs 函数的实现如下(以下代码来自 glibc):

/* Return the absolute value of I. */
int
abs (int i)
{
    return i < 0 ? -i : i;
}

可以看到,该函数仅有对于 int 的实现,并没有对于 long long 的实现。而 int 的范围为 -2^312^31 - 1,无法表达 2^31。实际操作中,-i 会返回 -2^31,从而导致了以上输出的产生。

正确的做法是使用 llabs() 函数,该函数是针对 long long 的绝对值:

/* Return the absolute value of I.  */
long long int
llabs (long long int i)
{
    return i < 0 ? -i : i;
}

使用 llabs() 函数,第一段代码就可以 AC 了。

为什么第二段代码可以 AC?

尝试发现,第二段代码并不能输出 -2147483649 的绝对值,而会输出 2147483647。这是因为,abs() 函数并不能处理超出 int 范围的值,导致它输出了其他值。

但是,第二段代码却能够正确地输出 -2147483648 的绝对值 2147483648

这是为什么呢?

int 中,0 到 2^31 – 1 是使用 0x00x7FFFFFFF 来表示的,而 -1 到 -2^31 是使用 0xFFFFFFFF0x80000000 来表示的。(注意:越大的数,其对应的十六进制值越大,但负数的十六进制值总是大于正数)(参见 补码 – 维基百科

我们输入的极限数据,-2147483648int 中,使用十六进制可以表示为 0x80000000

而在 long long 中,-2147483648 可以表示为 0xFFFFFFFF80000000,而表示 2147483648 的,是 0x80000000

我们可以做一个小实验:

int value = -2147483648;
printf("A: %d\n", value);
printf("B: %lld\n", value);

这段代码会输出什么呢?

A: -2147483648
B: 2147483648

(以上输出在 Manjaro Linux 18.1.11 下测得,使用 gcc (GCC) 8.2.1 编译,编译命令为 gcc 1.c -std=c99,在其他平台上可能有不同的结果,但在 OJ 上的结果应该和上面结果相同)

第一句 printf 使用了格式化控制符 %d。传给 printf 的数据是 0x80000000,它将其以 int 类型来解析,得到的结果正是 -2147483648

第二句 printf 使用了格式化控制符 %lld,它将其以 long long 类型来解析,得到的结果却是 2147483648

第二段代码也正是这个问题。我们接收了 abs() 函数返回的 int 数据 -2147483648 ,但将其以 long long 类型解析,得到 2147483648。这 恰好 是我们期望的结果,尽管这段代码并不正确。错上加错,反而导致了巧合的正确。

在第一段代码中,y = abs(x); 这行代码,实际上将一个 int 赋值给了 long long。在执行这个赋值操作的时候,实际上进行了一个类型转换操作。原本 int 值为 0x80000000,在运行类型转换的时候,程序会自动将这个值转换为了 long long 类型中 -2147483648 对应的正确值 0xFFFFFFFF80000000,从而导致程序输出错误的结果 -2147483648

结论

如果你能够看懂上面的文字,那很好;

如果你看不懂,我希望你能记住:

  1. abs() 函数仅能使用于 int 类型。如果你要计算 long long 类型的绝对值,请使用 llabs()
  2. printf 语句中,格式化控制符(%d%lld)必须与实际类型(intlong long)匹配,否则会导致数据类型解析错误。
  3. 如果一个 int 类型的变量 i 的值为 -2147483648,那么 -i 的值与 i 相同。

附注

在 C++11 中,std::abs() 对  long long 提供了重载,因此上述“错误”的代码在 C++11 中是正确的。请参见 cppreference

t123yh

CC BY-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-ShareAlike 4.0 International License.

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据