C определение оператора остатка / по модулю для положительных аргументов

Я нашел функцию в программе, которую я должен исправить, в которой определена функция mod:

int mod(int a, int b)
{
  int i = a%b;
  if(i<0) i+=b;
  return i;
}

Мне сказали, кстати, что a и b всегда будут положительными ...

Хм? if(i<0)?

Аргумент состоит в том, что что

результатом операции по модулю является класс эквивалентности, и любой член этого класса может быть выбран в качестве представителя

И только как запоздалую мысль

...; однако обычным представителем является наименьший положительный остаток, наименьшее неотрицательное целое число, которое принадлежит этому классу, то есть остаток от евклидова деления. Однако возможны и другие соглашения.

Это означает, что 6 % 7 может вернуть 6 (пока все хорошо), но также и -1. Хм ... правда? (Давайте проигнорируем тот факт, что представленная реализация не обрабатывает все случаи.)

Я знаю, что математически верно, что операция по модулю выглядит так. Но потом кто-то еще сказал мне, что C % на самом деле «не реализует оператор по модулю, а все остальное».

Итак, как C определяет оператор %?

В C-Draft я нахожу только

Результатом оператора / является частное от деления первого операнда на второй; результат оператора% - остаток. В обеих операциях, если значение второго операнда равно нулю, поведение не определено.

Означает ли это, что 6 % 7 всегда 6? Или это тоже может быть -1?


c division modulo integer-division
person towi    schedule 08.11.2019    source источник

Ответы (4)


arrow_upward
4
arrow_downward

Навсегда:

  • a == (a/b)*b + a%b
  • abs(a%b) < abs(b)
  • если a и b положительные, a % b положительно.

Начиная с C99,

  • a/b == trunc(a/b)
  • a%b либо 0, либо имеет знак a.

Мнение о том, что 6 % 7 могло быть -1, вероятно, связано с отсутствием того факта, что результат для a и b положительный всегда был гарантирован, и отсутствием изменения в C99.

person AProgrammer    schedule 08.11.2019

arrow_upward
5
arrow_downward

По стандарту:

Когда целые числа делятся, результатом оператора / является алгебраическое частное с отброшенной дробной частью. Если частное a / b представимо, выражение (a/b)*b + a%b должно быть равно a. [ИСО / МЭК 9899: 2011: 6.5.5]

Это означает, что знак a сохраняется по модулю.

 17 %  3  ->  2
 17 % -3  ->  2
-17 %  3  -> -2
-17 % -3  -> -2

Так что нет, 6%7 не может быть -1, потому что напоминание должно иметь такой же знак дивиденда.

person Davide Spataro    schedule 08.11.2019
comment
Я не спрашивал про знак - person towi; 08.11.2019
comment
Но он отвечает на ваш вопрос. Это не может быть -1, потому что 6 положительно. - person Davide Spataro; 08.11.2019

arrow_upward
2
arrow_downward

Значит ли это, что 6% 7 всегда 6? Или тоже может быть -1?

Согласно этому документу:

Остаток

Бинарный оператор% дает остаток от деления первого операнда на второй (после обычных арифметических преобразований).

[...]

когда тип после обычных арифметических преобразований является целочисленным типом, результатом является алгебраическое частное (не дробная часть), округленное в направлении, определяемом реализацией (до C99), с усечением до нуля (начиная с C99)

Таким образом, 6 / 7 будет 0, а 6 % 7 будет 6 - 0, то есть 6.

Заявление об операциях по модулю и классах эквивалентности интересно, это не то, как это работает в C (и большинстве других языков программирования).

Кроме того, даже если бы это было так, не было бы -8 в том же классе эквивалентности? Тогда if(i<0) i+=b; не решит проблему.

Но потом кто-то еще сказал мне, что C% на самом деле «не реализует оператор по модулю, а остальное».

Хорошая точка зрения. В документации, которую я связал, это называется «Остаток».

person Blaze    schedule 08.11.2019
comment
В самом деле, вам понадобится что-то эквивалентное: while(i<0) i+=b - person Davide Spataro; 08.11.2019
comment
спасибо, у меня такое же толкование. и мой комментарий, давайте проигнорируем ... был именно о вашем последнем предложении. - person towi; 08.11.2019
comment
Документация, на которую вы ссылаетесь, неверна. В стандартном разделе 6.3.5 C89 указывается, что когда целые числа делятся и деление неточное, если оба операнда положительны, результатом оператора / является наибольшее целое число, меньшее алгебраического частного, а результат оператора% положительный. - person Paul Hankin; 08.11.2019
comment
Округление / и знак % определяется только имплицитно (до C99), если один или оба операнда отрицательны: ... Если любой из операндов отрицательный, будет ли результат оператора / наибольшим целым числом, меньшим или равным алгебраическое частное или наименьшее целое число, большее или равное алгебраическому частному, определяется реализацией, как и знак результата оператора%. Если частное a / b представимо, выражение (a / b) * b + a% b должно быть равно a. - person Paul Hankin; 08.11.2019
comment
@PaulHankin, спасибо! Это более достоверно, чем документация. У вас есть ссылка, чтобы я мог добавить ее к ответу? - person Blaze; 08.11.2019

arrow_upward
2
arrow_downward

Существует как минимум три различных способа определения алгоритмов деления и остатка, когда одно или другое число может быть отрицательным. (См. эту статью в Википедии - и особенно там красивая картинка - подробнее.)

Но если вы знаете, что делите положительное число на положительное, никакой двусмысленности нет. Все три определения деления и остатка говорят, что если вы разделите положительное число на положительное, вы получите положительное частное и положительный остаток.

Из трех вариантов C использует тот, который называется «усекающим делением». Но, опять же, для положительных чисел это не имеет значения. (Когда-то компилятор решал, будет ли он использовать усечение или «евклидово» деление, но все остановилось только на одном определении, нескольких ревизиях стандарта C назад.)

Означает ли это, что 6 % 7 всегда 6? Или это тоже может быть -1?

Да, 6 % 7 всегда равно 6 (в C и в любом из трех определений).

См. Также этот эпический вопрос по теме.

person Steve Summit    schedule 08.11.2019