安全地取整数的绝对值（C语言相关）

Question

考虑以下程序（C99）：

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

int main(void)
{
    printf("Enter int in range %jd .. %jd:\n > ", INTMAX_MIN, INTMAX_MAX);
    intmax_t i;
    if (scanf("%jd", &i) == 1)
        printf("Result: |%jd| = %jd\n", i, imaxabs(i));
}

据我理解，这段代码包含易于触发的未定义行为，例如：

Enter int in range -9223372036854775808 .. 9223372036854775807:
 > -9223372036854775808
Result: |-9223372036854775808| = -9223372036854775808

问题：

1. 如果用户输入了错误的数字，这是否真的是未定义行为，就像“代码被允许触发任何代码路径，而任何能够引起编译器注意的代码”一样？或者它是其他类型的不完全定义行为？

2. 一个吹毛求疵的程序员如何在不做任何标准没有保证的假设的情况下防范这种情况？

（有几个相关的问题，但我没有找到一个回答上述第2个问题的问题，因此如果您建议重复，请确保它回答了那个问题。）

- hyde

---

请注意，输入超出范围的整数会导致未定义的行为。如果要避免未定义的行为，则不能使用任何类型的%d或其他整数或浮点scanf格式说明符。请使用strto系列函数。而且，未定义的行为只有一种，那就是坏的行为。 - M.M

@M.M 还有一些实现定义行为、未指定但有效的值，以及可能是未定义行为的其他温和替代品。但是，我是否误解了，你是说 scanf 对于带符号或浮点数隐含地包含用户可触发的 UB 吗？参考资料呢？ - hyde

是的，用户可以通过输入超出正在扫描的整数范围的值来触发UB。请参阅C标准中的fscanf规范。在C11中，它是7.21.6.2/10，“如果转换的结果不能被对象表示，则行为未定义”。因此，scanf系列大多不适合用于生产。 - M.M

我记得很多年前我上编程入门课时的第一个作业是写一个程序来计算两个数字的和，这些数字可以是正数或负数。我认真地写了代码，然后意识到可能会出现溢出和下溢的情况，所以我又写了代码来检测并告知用户是否发生了这种情况。我想类似的方法也可以用来满足你的第二个问题。 - Michael

Answer 1

如果imaxabs的结果无法表示，可能会发生在使用二进制补码时，那么 行为是未定义的。

7.8.2.1函数imaxabs

2. 函数imaxabs计算整数j的绝对值。如果结果无法表示，则行为是未定义的。221）

221）在二进制补码中，最负数的绝对值无法表示。

进行检查而不做任何假设并且总是有定义的方法是：

intmax_t i = ... ;
if( i < -INTMAX_MAX )
{
    //handle error
}

如果使用补码或原码表示法，这个if语句将无法执行。编译器可能会发出“不可到达的代码”警告。但是该代码本身仍然被定义且有效。

- 2501

---

感谢您提供的好解决方案，这是一个艰难的选择，但经过一些考虑，我仍然选择接受其他答案，因为它展示了如何打印正确的结果。 - hyde

@hyde 除了另一个答案不符合标准，而这个答案符合标准。 - Voo

-INTMAX_MAX 不会溢出，这个有保证吗？ - nwellnhof

@nwellnhof 这是有保障的。请看我的其他评论：https://dev59.com/j1sW5IYBdhLWcg3wOk_O#35251846?noredirect=1#comment58217467_35251501 - 2501

Answer 2

一个过于追求细节的程序员会如何防止这种情况发生，而不做任何标准未保证的假设呢？

一种方法是使用无符号整数。无符号整数的溢出行为是明确定义的，转换有符号整数到无符号整数的行为也是明确定义的。

因此，我认为以下代码应该是安全的（结果在某些非常晦涩的系统上是糟糕的，见后面的帖子中改进版）。

uintmax_t j = i;
if (j > (uintmax_t)INTMAX_MAX) {
  j = -j;
}
printf("Result: |%jd| = %ju\n", i, j);

---

那么这是如何工作的？

uintmax_t j = i;

这将有符号整数转换为无符号整数。如果它是正数，值保持不变；如果它是负数，则值增加2ⁿ（其中n是位数）。这将把它转换为一个大数字（比INTMAX_MAX更大）。

if (j > (uintmax_t)INTMAX_MAX) {

如果原始数字为正（因此小于或等于INTMAX_MAX），则不执行任何操作。如果原始数字为负，则运行if块中的内容。

  j = -j;

数字被否定了。否定的结果显然是负数，因此不能表示为无符号整数。因此，它增加了2ⁿ。

因此，代数上看，负数i的结果如下：

j = - (i + 2ⁿ) + 2ⁿ = -i

---

“聪明，但这个解决方案做了一些假设。如果INTMAX_MAX == UINTMAX_MAX，这将失败，而这是C标准允许的。”

“嗯，让我们看看这个（我正在阅读https://busybox.net/~landley/c99-draft.html，这显然是标准化之前的最后一个C99草案，如果在最终标准中有任何更改，请告诉我。”

“当定义仅在初始u的存在或不存在上不同的typedef名称时，它们应表示6.2.5中描述的相应的有符号和无符号类型；实现不应提供没有提供其相应类型的类型。”

“在6.2.5中，我看到：”

“对于每个有符号整数类型，都有一个相应的（但不同的）无符号整数类型（用关键字unsigned指定），它使用相同数量的存储空间（包括符号信息）并具有相同的对齐要求。”

“在6.2.6.2中，我看到：”

对于除了unsigned char之外的其他无符号整数类型，对象表示的位将被分成两组：值位和填充位（可以没有填充位）。如果有N个值位，则每个位将表示介于1和2N-1之间的不同的2的幂次方，使得该类型的对象能够使用纯二进制表示表示从0到2N-1的值；这将被称为值表示。任何填充位的值都是未指定的。 对于有符号整数类型，对象表示的位将被分成三组：值位、填充位和符号位。可能没有填充位；必须恰好有一个符号位。作为值位的每个位都应与相应的无符号类型的对象表示中的相同位具有相同的值（如果有M个值位在有符号类型中，N个值位在无符号类型中，则M≤N）。如果符号位为零，则不会影响结果值。所以是的，看起来你是对的，虽然有符号和无符号类型必须具有相同的大小，但似乎无符号类型可以比有符号类型多一个填充位。

---

好的，基于以上分析揭示了我第一次尝试中的缺陷，我写了一个更加谨慎的变体。这与我的第一个版本有两个改变。

我使用 i < 0 而不是 j > (uintmax_t)INTMAX_MAX 来检查负数。这意味着即使 INTMAX_MAX == UINTMAX_MAX，该算法也可以为大于或等于 -INTMAX_MAX 的数字生成正确的结果。

我添加了对错误情况的处理，其中 INTMAX_MAX == UINTMAX_MAX，INTMAX_MIN == -INTMAX_MAX -1 和 i == INTMAX_MIN。这将导致 if 条件内的 j=0，我们可以轻松地进行测试。

从 C 标准的要求可以看出，INTMAX_MIN 不能小于 -INTMAX_MAX -1，因为只有一个符号位，值位数必须与相应的无符号类型中的位数相同或更低。根本没有剩余的位模式来表示更小的数字。

uintmax_t j = i;
if (i < 0) {
  j = -j;
  if (j == 0) {
    printf("your platform sucks\n");
    exit(1);
  }
}
printf("Result: |%jd| = %ju\n", i, j);

---

@plugwash 我认为2501是正确的。例如，-UINTMAX_MAX值变为1：(-UINTMAX_MAX + (UINTMAX_MAX + 1))，并且不会被您的if捕获。– hyde 58分钟前

嗯，

假设INTMAX_MAX == UINTMAX_MAX且i = -INTMAX_MAX

uintmax_t j = i;

执行此命令后，j = -INTMAX_MAX + (UINTMAX_MAX + 1) = 1

if (i < 0) {

i小于零，因此我们运行if内的命令

j = -j;

执行此命令后，j = -1 + (UINTMAX_MAX + 1) = UINTMAX_MAX

这是正确的答案，因此无需在错误情况下陷入陷阱。

- plugwash

---

聪明，但这个解决方案有一些假设。如果 INTMAX_MAX == UINTMAX_MAX，这会失败，而C标准允许这种情况。 - 2501

@hyde 第C11 6.2.6.2段落的第二句话提到，无符号整数可能与相应的有符号整数具有相同数量的值位（注意：M≤N）。在这种情况下，有符号整数的范围实际上更大，因为它有一个额外的符号位，该位赋予它负范围。 - 2501

@hyde 1. 是的，只是错误的结果。2. 我不知道有任何其他的方法。:) 我认为这更多是一个理论上的问题。你可以为那种不太可能的情况添加 #ifdef，并使用这段代码，如果你喜欢的话。 - 2501

@plugwash 是的，我的前三条评论对于那些值来说都不正确，所以我把它们删掉了。 - 2501

@2501，我认为你是不正确的。我的代码原始版本依赖于j=i对正数和负数产生不同的结果，但是“更谨慎”的版本将测试更改为（i<0），因此正数和负数不再需要产生不同的j值。 - plugwash

Answer 3

在二补码系统中，获取最小值的绝对数确实是未定义行为，因为绝对值会超出范围。编译器无法帮助您解决这个问题，因为 UB 发生在运行时。

唯一的保护方法是将输入与类型的最小值（在您展示的代码中为 INTMAX_MIN）进行比较。

- Some programmer dude

---

这涵盖了二进制补码（并且仅在一的补码中丢失一个有效数字），但我认为一个好的问题是，是否可以以可靠的方式检测到它，而不管整数表示方式如何（我假设标准不仅限于一和二的补码，尽管我必须承认我从未检查过）。 - Joachim Isaksson

标准限制为三种选项之一：二进制补码、反码和原码。(C99，6.2.6.2，第2段。) - Mark Dickinson

if( i < -INTMAX_MAX ) 这个语句对于任何的表示方式都有效。尽管在使用补码或者符号-数表示法的编译器上可能会得到警告，因为这个语句无法执行。但我不知道如何避免这种情况。 - 2501

“这并不是编译器能帮到你的，因为未定义行为发生在运行时。”编译器可以生成执行时检查的代码；-) - coredump

@skyking 标准并未定义该类型。您能否引用标准，以便更清楚地表达您的观点？或者更好的方法是发布一篇回应我的答案。 （我很感兴趣，也许我错了，但我没有看到它。） - 2501

根据C语言规范，对于任何有符号类型，都必须能够表示-MAX（最小负数）：C11 6.2.6.2, p2，因为有符号整数必须是这三种表示中的一种，以确保它们的取值范围。有符号整数的最大值不可能比其绝对值的最小值还要大。 - 2501

Answer 4

因此，在某些情况下，计算整数的绝对值会导致未定义的行为。实际上，虽然可以避免出现未定义的行为，但在某些情况下无法给出正确的结果。

现在考虑整数乘以3的情况：这里我们有一个更严重的问题。这个操作在三分之二的情况下会导致未定义的行为！而对于三分之二的int值x，找到一个值为3x的int是不可能的。这是比绝对值问题更严重的问题。

- gnasher729

Answer 5

您可能想使用一些位操作技巧：

int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here 
int const mask = v >> sizeof(int) * CHAR_BIT - 1;

r = (v + mask) ^ mask;

这在INT_MIN < v <= INT_MAX时效果良好。如果v == INT_MIN，它仍然保持为INT_MIN，而不会导致未定义的行为。您还可以使用位运算来处理反码和补码系统中的这个问题。参考：https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs。

- nalzok

---

我认为对有符号整数进行右移本身就是未定义行为。 - abligh

如果有符号整数为负，则其实现是未定义的。此答案还假定没有填充位。 - 2501

根据位操作技巧文件，这个无分支解决方案依赖于二进制补码，但也已经在美国获得了专利，这也可能会是一个问题。 - Rob11311

Answer 6

根据此http://linux.die.net/man/3/imaxabs。

备注：

尝试对最小负整数取绝对值是未定义的。

为了处理全部范围，您可以将以下内容添加到您的代码中。

    if (i != INTMAX_MIN) {
        printf("Result: |%jd| = %jd\n", i, imaxabs(i));
    } else {  /* Code around undefined abs( INTMAX_MIN) /*
        printf("Result: |%jd| = %jd%jd\n", i, -(i/10), -(i%10));
    }

编辑：由于在2的补码机器上无法表示abs(INTMAX_MIN)，因此将范围内可表示的2个值连接在输出中作为字符串。 经过gcc测试，但printf需要%lld，因为不支持%jd格式。

- Ilan Kutsman

---

imax(i+1)+1 是什么，它的作用是什么？ - Pascal Cuoq

我本来想写的是imaxabs，我会进行修正。它应该给出INTMAX_MIN绝对值的正确结果。只是在尝试打破常规思维。 - Ilan Kutsman

imaxbas(i+1)+1 不是一种解决方法，它只是将未定义的行为推入第二个加法中。在补码机器上，imaxabs(INTMAX_MIN) 未定义的根本原因是正确的结果无法表示。无论添加两次一还是多少次一，都无法改变这个基本事实。 - Pascal Cuoq

好的，稍作修改，imaxabs(INTMAX_MIN+1)可以被2进制补码机器表示。现在你需要将其转换为字符串，并在'\0'之前递增最后一个字符。 - Ilan Kutsman

使用 div 和 mod 更容易将 INTMAX_MIN 放入可否定的范围。 - Rob11311

Answer 7

• 当用户输入错误的数字时，代码允许触发任何代码路径，这些路径可能会引起编译器的注意，这是否真的是未定义行为？还是其他类型的不完全定义行为？

只有在成功输入错误数字并传递给imaxabs()函数后，程序的行为才是未定义的。在典型的二进制补码系统中，该函数返回一个负数结果，正如您所观察到的。

在这种情况下，这就是未定义行为，如果ALU设置状态标志，实现也可以终止程序并显示溢出错误。

C语言中“未定义行为”的原因是为了让编译器编写者不必防范溢出，以便程序能够更有效地运行。虽然每个使用abs()函数的C程序都可能试图杀死你的第一个孩子，但只要你用一个太小的值调用它，将这样的代码写入目标文件就是荒谬的。

这些未定义行为的真正问题在于，优化编译器可以推理出天真的检查，因此像以下代码一样的代码：

r = (i < 0) ? -i : i;
if (r < 0) {   // This code may be pointless
    // Do overflow recovery
    doRecoveryProcessing();
} else {
    printf("%jd", r);
}

作为编译器优化器可以推断负值被否定，它原则上可以确定 (r <0) 总是错误的，因此尝试捕获问题失败。

2. 一个过于严谨的程序员如何在不做任何标准未保证的假设的情况下防范这种情况？

到目前为止，最好的方法就是确保程序在有效范围内工作，所以在这种情况下，验证输入就足够了（禁止 INTMAX_MIN）。打印 abs() 表格的程序应避免使用 INT*_MIN 等。

    if (i != INTMAX_MIN) {
        printf("Result: |%jd| = %jd\n", i, imaxabs(i));
    } else {  /* Code around undefined abs( INTMAX_MIN) /*
        printf("Result: |%jd| = %jd%jd\n", i, -(i/10), -(i%10));
    }

似乎通过欺骗的方式写出 abs(INTMAX_MIN)，使程序能够履行对用户的承诺。

- Rob11311