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

Question

Я нашел функцию в программе, которую я должен исправить, для которой определена функция 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

Answer 1

В соответствии со стандартом:

Когда целые числа делятся, результатом оператора / является алгебраический коэффициент с любой отброшенной дробной частью. Если частное 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, поскольку напоминание должно иметь одинаковый знак дивиденда.

Answer 2

Навсегда:

• 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.

Answer 3

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

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

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

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

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

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

Answer 4

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

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

Остаток

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

[...]

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

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

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

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

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

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