glibc`div()`代码中的错误？

Question

如" 在C++中使用负数进行整数除法 "中所述,在C99之前的C中(即在C89中)和在C++之前的C++中(即在C++ 98和C++ 03中),用于整数除法计算,其中两个操作数都是负数,余数的符号(或等效地,商的舍入方向)是实现定义的.

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

这是glibc的div()(源代码)代码(也引用" Is div function useful(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而不是向零截断,其目的是"校正"结果.

现在的问题是:

该代码中是否有错误？

我们首先考虑一下示例调用div(42, -5)."在数学中" 42/-5正好是-8.4,因此理论上在C89和C++ 03中42 / -5可以产生-8(截断的)或-9(平铺的),具体取决于实现.阅读代码:

• 如果42 / -5产量-8然后42 % -5产生2(as 42 == -8 * -5 + 2),那么测试(42 >= 0 && 2 < 0)不是真的,上面的函数返回,-8并且2如所希望的那样;
• 如果42 / -5产率-9则42 % -5产率-3(如42 == -9 * -5 + -3),所以测试是(42 >= 0 && -3 < 0)这是真实的,因此上述函数返回"校正" -9 + 1和-3 - -5,即-8和2,如想要的.

但现在让我们考虑一下这个电话div(-42, 5)(标志倒置):

• 如果-42 / 5产量-8然后-42 % 5产生-2(as -42 == -8 * 5 + -2),那么测试(-42 >= 0 && -2 < 0)不是真的,上面的函数返回,-8并且-2如所希望的那样;
• 如果-42 / 5产量-9然后-42 % 5产生3(as -42 == -9 * 5 + 3),那么测试是(-42 >= 0 && 3 < 0)...... 不是真的!并且上面的函数返回-9而3不是-8和-2!

上面代码中的注释首先看起来是正确的,它表示需要更正的情况是"REM与NUMER符号相反",但随后它会进行大量简化 "这一切归结为:如果NUMER> = 0 ,但REM <0,我们得到了错误的答案",这似乎是错误的(不完全)对我来说,因为它忽略了一个情况:'如果NUMER <0,但REM> 0’(-42和3在前面的例子).

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

感谢您的任何见解.

---

¹ (编辑)至于"问题在C++ 11和C99(及更新版本)中没有问题":因此,在这些标准中,内置除法需要截断为零,因此我们永远不需要调整结果,但是,这是不是意味着目前的实施比需要的更复杂,而且不必要地效率低下？"大评论"已经过时,if测试没用,所以不应该完全删除那部分吗？

Answer 1

作为代码的原作者,我不得不说:你是对的.它坏了.我们没有任何系统表现出"错误的方式"进行测试,而且我可能在当天或类似的事情上写了太多(或早期......).

我们是按照较新的标准保存的,如果需要的话,可以清理整个事物,也可以使用小的#ifdef(并修正调整代码)预先C99.

(另外我会注意到原始版本没有缩进GNU风格的缩进:-))