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

问题：

当用户输入错误数字时，这真的是未定义的行为，如 "code is allowed to trigger any code path, which any code that stroke compiler's fancy" 中那样吗？或者是其他一些未完全定义的味道？
迂腐的程序员将如何防范这种情况，不做出标准不保证的任何假设？

（有几个相关问题，但我没有找到可以回答上面问题 2 的问题，所以如果您建议重复，请确保它回答了那个问题。）

Answer 1

在二元补码系统上，获得最大负值的绝对数确实是未定义的行为，因为绝对值会超出范围。编译器无法帮助您，因为 UB 发生在运行时间。

防止这种情况发生的唯一方法是将输入与该类型的最负值进行比较（INTMAX_MIN 在您显示的代码中）。

Answer 2

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

7.8.2.1 The imaxabs function

The imaxabs function computes the absolute value of an integer j. If the result cannot be represented, the behavior is undefined. 221)

221) The absolute value of the most negative number cannot be represented in two’s complement.

不做假设且始终定义的检查是：

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

（如果使用补码或符号大小表示，则无法执行此 if 语句，因此编译器可能会给出无法访问的代码警告。代码本身仍然是已定义且有效的。）

Answer 3

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

Notes

Trying to take the absolute value of the most negative integer is not defined.

要处理整个范围，您可以在代码中添加类似这样的内容

    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) 无法在 2 的补码机上表示，因此可表示范围内的 2 个值在输出时连接为字符串。已使用 gcc 进行测试，但 printf 需要 %lld，因为 %jd 不是受支持的格式。

Answer 4

您可能想使用一些技巧：

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

Answer 5

How would a pedantic programmer go about guarding against this, without making any assumptions not guaranteed by standard?

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

所以我认为以下内容应该是安全的（事实证明它在一些非常晦涩的系统上被严重破坏，稍后在 post 中查看改进版本）

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

Clever, but this solution makes assumptions. This fails if INTMAX_MAX == UINTMAX_MAX, which is allowed by C Standard.

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

When typedef names differing only in the absence or presence of the initial u are defined, they shall denote corresponding signed and unsigned types as described in 6.2.5; an implementation shall not provide a type without also providing its corresponding type.

在6.2.5我看到了

For each of the signed integer types, there is a corresponding (but different) unsigned integer type (designated with the keyword unsigned) that uses the same amount of storage (including sign information) and has the same alignment requirements.

在6.2.6.2我看到了

#1

For unsigned integer types other than unsigned char, the bits of the object representation shall be divided into two groups: value bits and padding bits (there need not be any of the latter). If there are N value bits, each bit shall represent a different power of 2 between 1 and 2N-1, so that >objects of that type shall be capable of representing values from 0 to 2N-1 >using a pure binary representation; this shall be known as the value representation. The values of any padding bits are unspecified.39)

#2

For signed integer types, the bits of the object representation shall be divided into three groups: value bits, padding bits, and the sign bit. There need not be any padding bits; there shall be exactly one sign bit. Each bit that is a value bit shall have the same value as the same bit in the object representation of the corresponding unsigned type (if there are M value bits in the signed type and N in the unsigned type, then M<=N). If the sign bit is zero, it shall not affect the resulting value.

所以是的，看来你是对的，虽然有符号和无符号类型的大小必须相同，但无符号类型比有符号类型多一个填充位似乎是有效的。

好的，根据上面的分析揭示了我第一次尝试中的一个缺陷，我写了一个更偏执的变体。这与我的第一个版本相比有两个变化。

我使用 i < 0 而不是 j > (uintmax_t)INTMAX_MAX 来检查负数。这意味着即使 INTMAX_MAX == UINTMAX_MAX.

，算法也会为大于或等于 -INTMAX_MAX 的数字计算出正确的结果

我添加了对 INTMAX_MAX == UINTMAX_MAX、INTMAX_MIN == -INTMAX_MAX -1 和 i == [=93= 的错误情况的处理].这将导致我们可以轻松测试的 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 I think 2501 is correct. For example, -UINTMAX_MAX value becomes 1: (-UINTMAX_MAX + (UINTMAX_MAX + 1)), and is not caught by your if. – hyde 58 mins ago

嗯，

假设 INTMAX_MAX == UINTMAX_MAX 并且 i = -INTMAX_MAX

uintmax_tj=i;

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

如果（我 < 0）{

i 小于零所以我们运行 if

中的命令

j = -j;

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

这是正确答案，因此无需将其陷入错误情况。

Answer 6

当用户输入错误号码时，这真的是未定义的行为，如 "code is allowed to trigger any code path, which any code that stroke compiler's fancy" 中那样吗？还是 not-completely-defined 的其他风味？

程序的行为只是未定义，当错误数字成功 input-ed 并传递给 imaxabs() 时，在典型的 2 的补码系统中 returns 结果与您一样观察到。

在这种情况下，这是未定义的行为，如果 ALU 设置状态标志，也允许实现以 over-flow 错误终止程序。

C 中 "undefined behaviour" 的原因是编译器编写者不必防止溢出，因此程序可以运行更有效。虽然每个使用 abs() 的 C 程序都在 C 标准中试图杀死你的长子，只是因为你用太 -ve 值调用它，将这样的代码写入 object 文件只是有悖常理。

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

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

由于编译器优化器可以推断负值被取反，它原则上可以确定 (r <0) always false，因此尝试捕获问题失败.

迂腐的程序员如何在不做出任何不受标准保证的假设的情况下防范这种情况？

到目前为止，最好的方法就是确保程序在有效范围内运行，因此在这种情况下验证输入就足够了（不允许 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)，使程序能够实现对用户的承诺。

Answer 7

因此，在一种情况下，计算整数的绝对值会调用未定义的行为。实际上，虽然可以避免未定义的行为，但不可能在一种情况下给出正确的结果。

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

C安全地取整数的绝对值

C safely taking absolute value of integer

c

undefined-behavior

absolute-value