8

如“ C++ 中带负数的整数除法舍入”、C99 之前的 C（即 C89 中）和 C++11 之前的 C++（即 C++98 和 C++03）中所引用的，对于整数除法计算，其中任一操作数为负，余数的符号（或等价地，商的舍入方向）是实现定义的。

然后是标准函数std::div，它被指定将商截断为零（即余数与被除数（分子）具有相同的符号）（例如，参见“什么是 div() 库函数的目的？”的答案）。

这是 glibc 的div()( source ) 代码（也在“ Is div function有用 (stdlib.h)? ”中引用）：

（注：div_t定义为：

typedef struct
  {
    int quot;
    int rem;
  } div_t;

——结束注。）

/* Return the `div_t' representation of NUMER over DENOM.  */
div_t
div (numer, denom)
     int numer, denom;
{
  div_t result;

  result.quot = numer / denom;
  result.rem = numer % denom;

  /* The ANSI standard says that |QUOT| <= |NUMER / DENOM|, where
     NUMER / DENOM is to be computed in infinite precision.  In
     other words, we should always truncate the quotient towards
     zero, never -infinity.  Machine division and remainer may
     work either way when one or both of NUMER or DENOM is
     negative.  If only one is negative and QUOT has been
     truncated towards -infinity, REM will have the same sign as
     DENOM and the opposite sign of NUMER; if both are negative
     and QUOT has been truncated towards -infinity, REM will be
     positive (will have the opposite sign of NUMER).  These are
     considered `wrong'.  If both are NUM and DENOM are positive,
     RESULT will always be positive.  This all boils down to: if
     NUMER >= 0, but REM < 0, we got the wrong answer.  In that
     case, to get the right answer, add 1 to QUOT and subtract
     DENOM from REM.  */

  if (numer >= 0 && result.rem < 0)
    {
      ++result.quot;
      result.rem -= denom;
    }

  return result;
}

如您所见，在大注释块之后有一个测试，其目的是“纠正”内置除法截断为 -infinity 而不是为零的结果。

现在的问题：

该代码中没有错误吗？

让我们首先考虑示例 call div(42, -5)。“在数学中” 42/-5正好是-8.4，因此理论上在 C89 和 C++03 中42 / -5可能会产生-8（截断）或-9（下限），具体取决于实现。阅读代码：

  • 如果42 / -5yield-8则42 % -5yield 2(as 42 == -8 * -5 + 2)，所以测试是(42 >= 0 && 2 < 0)which is not true 并且上面的函数返回-8and 2，如所希望的；
  • 如果42 / -5yield-9那么42 % -5yield -3(as 42 == -9 * -5 + -3)，那么测试是(42 >= 0 && -3 < 0)正确的，所以上面的函数返回“更正的” -9 + 1and -3 - -5，即-8and 2，如所希望的。

但现在让我们考虑调用div(-42, 5)（符号倒置）：

  • 如果-42 / 5yield-8则-42 % 5yield -2(as -42 == -8 * 5 + -2)，所以测试是(-42 >= 0 && -2 < 0)which is not true 并且上面的函数返回-8and -2，如所希望的；
  • 如果-42 / 5产生-9然后-42 % 5产生3（as -42 == -9 * 5 + 3），所以测试是(-42 >= 0 && 3 < 0)哪个......不是真的！上面的函数返回-9and3而不是-8and-2！

上面代码中的注释首先似乎是正确的，当它说需要更正的情况是“REM 具有 NUMER 的相反符号”时，但随后它进行了巨大的简化“这一切都归结为：如果 NUMER >= 0 ，但是 REM < 0，我们得到了错误的答案”，这对我来说似乎是错误的（不完整），因为它省略了“如果 NUMER < 0，但 REM > 0”的情况（-42以及3在前面的示例中）。

我几乎不敢相信这样的错误自 1992 年或 1990 年以来一直未被注意到（显然有人试图“修复”它，但它似乎仍然不正确，因为div(-42, 5)可能会返回-10和8）......可以说，大多数实现默认情况下都被截断为零（并且从 C99 和 C++11 开始都需要这样做，所以问题在最新的标准1中是“没有实际意义的” ）所以错误不会出现在他们身上，但仍然......也许我错过了一些东西这里？

感谢您的任何见解。

1 （编辑）至于“问题在 C++11 和 C99（及更新版本）中没有实际意义”：因此，在这些标准中，内置除法需要截断为零，所以我们不需要调整结果，但这是否意味着当前的实现比需要的更复杂并且不必要地低效？“大评论”已经过时，if测试也没用，所以那部分不应该完全删除吗？

4

1 回答 1

6

作为代码的原作者，我不得不说：你是对的。它坏了。我们没有系统在测试中表现出“错误的方式”，而且我可能在当天太晚（或太早......）写了上面的内容。

我们被更新的标准所拯救，整个事情都应该被清理掉，#ifdef如果需要的话，可能会为 C99 之前的一个小的（和更正的调整代码）。

（另外我会注意到原件没有使用 GNU 风格的缩进 :-)）

于 2013-07-27T19:56:49.373 回答