Как указано в «Целочисленное деление, округление с отрицаниями в C ++«, в C до C99 (то есть в C89) и в C ++ до C ++ 11 (т.е. в C ++ 98 и C ++ 03), для вычисления целочисленного деления, где любой операнд является отрицательным знаком остатка (или эквивалентно, направление округления частного) от реализации.
Затем идет стандартная функция std::div
который указан для обрезать частное к нулю (т.е. остаток имеет тот же знак, что и дивиденд (числитель)) (см., например, ответ на вопрос «какова цель библиотечной функции div ()?»).
Вот код Glibc для div()
(источник) (также цитируется вПолезна ли функция div (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
(как 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
(как -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
а также 3
вместо -8
а также -2
!Комментарий в приведенном выше коде сначала кажется правильным, когда говорится, что ситуация, требующая исправления, — это когда «REM имеет противоположный знак NUMER», но затем он делает огромное упрощение «Это все сводится к: если NUMER> = 0, но REM < 0, мы получили неправильный ответ «, что мне кажется неправильным (неполным), потому что это опускает случай «если номер < 0, но REM> 0 «(-42
а также 3
в предыдущем примере).
Я с трудом могу поверить, что такая ошибка осталась бы незамеченной с 1992 или 1990 года (очевидно, кто-то пытался это исправить но это все еще кажется неправильным, потому что div(-42, 5)
мог вернуться -10
а также 8
) … Возможно, большинство реализаций усекалось до нуля по умолчанию (и все должны делать это, начиная с C99 и C ++ 11, поэтому проблема в последних стандартах «спорная» 1) так что ошибка не проявляется на них, но все же … Может быть, я что-то здесь упускаю?
Спасибо за любые идеи.
1 (Редактировать) Что касается «проблема спорная в C ++ 11 и C99 (и новее)»: соответственно, в этих стандартах встроенное деление требуется для усечения до нуля, поэтому нам никогда не нужно корректировать результат, но это не так это означает, что настоящая реализация сложнее, чем нужно а также излишне неэффективный? «Большой комментарий» устарел и if
тест бесполезен, так разве эта часть не должна быть полностью удалена?
Как первоначальный автор кода, я должен сказать: вы правы. Оно сломано. У нас не было систем, которые вели себя «неправильно» для тестирования, и я, вероятно, написал вышеупомянутое слишком поздно (или рано…) в тот же день или что-то в этом роде.
Мы спасены по новым стандартам, и все это должно быть очищено, возможно, с небольшим #ifdef
(и исправленный код регулировки) для предварительного C99, если необходимо.
(Также отмечу, что оригинал не имел отступов в стиле GNU :-))
Но в этом случае Numer равно -42, (так что оно отрицательно), что сделало условие ложным автоматически. На самом деле, если вы попытаетесь выполнить простой код, который содержит функцию, вы увидите (отладку) оператор if:
// false in this case, numer = -42 and result.rem = -2
if(numer >= 0 && result.rem < 0)
Здесь вы можете увидеть скомпилированный результат:введите описание ссылки здесь
Я надеюсь, что ответ правильный и поможет вам понять ошибку.