8

「 C++ の負数を使用した整数除算の丸め」で引用されているように、C99 より前の C (つまり、C89) および C++11 より前の C++ (つまり、C++98 および C++03) では、整数除算の計算について、いずれかのオペランドが負の剰余の符号 (または同等の商の丸め方向) は実装定義です。

次に、商をゼロに向けて切り捨てるようにstd::div指定された標準関数が続きます(つまり、剰余は被除数 (分子) と同じ符号を持ちます) (たとえば、「div() ライブラリ関数の目的は何ですか?」に対するこの回答を参照してください)。

div()( source )の glibc のコードは次のとおりです (「 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 に向かって切り捨てられた場合に結果を「修正」することです。

今質問：

そのコードにバグはありませんか？

最初に call の例を考えてみましょうdiv(42, -5)。「数学では」42/-5は正確に-8.4であるため、理論的には C89 および C++03 では、実装に応じて (切り捨てられた) または(フロア化された) の42 / -5いずれかが生成される可能性があります。コードを読む:-8-9

  • if 42 / -5yields -8then 42 % -5yield 2(as 42 == -8 * -5 + 2)、したがって、テストは(42 >= 0 && 2 < 0)which が真ではなく、上記の関数は必要に応じて-8and2を返します。
  • if 42 / -5yields -9then 42 % -5yields -3(as 42 == -9 * -5 + -3)、したがって、テストは(42 >= 0 && -3 < 0)どちらが真であるかです。したがって、上記の関数は「修正された」-9 + 1and -3 - -5、つまり-8and2を必要に応じて返します。

しかし、ここで呼び出しを考えてみましょうdiv(-42, 5)(符号を反転):

  • if -42 / 5yields -8then -42 % 5yield -2(as -42 == -8 * 5 + -2)、したがって、テストは(-42 >= 0 && -2 < 0)which が真ではなく、上記の関数は必要に応じて-8and-2を返します。
  • if -42 / 5yields -9then -42 % 5yields 3(as -42 == -9 * 5 + 3)、したがって、テストは(-42 >= 0 && 3 < 0)which... はtrue ではありません! 上記の関数はandの代わりにand を返します-93-8-2!

上記のコードの最初のコメントは、修正が必要な状況は「REM が NUMER の反対の符号を持っている」場合であると述べているときは正しいように見えますが、 「これはすべて要約すると次のように単純化されます。NUMER >= 0 の場合」 、しかし REM < 0、間違った答えが得られました」、「if NUMER < 0, but REM > 0」(および前の例)のケースが省略されているため、これは間違っている (不完全) ように思えます。-423

このようなバグが 1992 年または 1990 年以来見過ごされていたとは信じられません (どうやら誰かがそれを「修正」しようとしたようですが、とdiv(-42, 5)が返される可能性があるため、まだ正しくないようです)... ほぼ間違いなく、ほとんどの実装はデフォルトでゼロに向かって切り詰められています ( C99 と C++11 からはすべてそうする必要があるため、最新の標準1では問題は「意味不明」であるため、バグはそれらに現れませんが、それでも... 多分私は何かが欠けていますここ？-108

洞察をありがとう。

1 (編集)「問題は C++11 および C99 (およびそれ以降) では問題ありません」: したがって、これらの標準では、組み込みの除算をゼロに向かって切り捨てる必要があるため、結果を調整する必要はありません。しかし、それは現在の実装が必要以上に複雑で、不必要に非効率的であることを意味しませんか? 「大きなコメント」は時代遅れであり、ifテストは役に立たないので、その部分は完全に削除されるべきではないでしょうか?

4

1 に答える 1

6

コードの最初の作成者として、私は言わなければなりません: あなたは正しいです。壊れてます。テストのために「間違った方法」で動作するシステムはありませんでした。おそらく、上記の記事を書いたのが遅すぎました (または早すぎました...)。

#ifdef私たちは新しい標準によって救われており、必要に応じて C99 以前の小さな (および修正された調整コード) を使用して、全体を一掃する必要があります。

（また、オリジナルはGNUスタイルのインデントでインデントされていないことに注意してください:-)）

于 2013-07-27T19:56:49.373 に答える