Каковы правила модульной арифметики в C?

В предыдущих классах мне учили, что n % d = r и думать об этом как n = d*q + r, где d - это делитель, q - частное, а r - остаток (отмечая, что остаток никогда не может быть отрицательным).

Так, например, -111 mod 11 есть 10, потому что -111 = -11*-11 + 10 (в отличие от -111 = -11*10 -1, видя, как это даст нам отрицательный остаток).

Однако при печати результатов -111 % 11, -1 - результат, а не 10. Зачем? Разве это не технически неправильно?

Ответы

Ответ 1

Короткий ответ:

Стандарт гарантирует, что (a/b)*b + a%b равно a.

В C99 результат деления / будет усечен до нуля. Результат оператора % будет определен, в данном случае -1.

В C89 результат деления / может быть усечен в любом случае для отрицательных операндов. Таким образом, результат оператора % также зависит от машины.

Длинный ответ:

Из C99 6.5.5

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

6 Когда целые числа делятся, результатом оператора/является алгебраическое отношение с любым фракционная часть отбрасывается. Если частное a/b представимо, выражение (a/b) * b + a% b равно a; в противном случае поведение как a/b, так и a% b undefined.

И сноска на той же странице, чтобы объяснить, как работает /, говорится:

Это часто называют "усечением к нулю".

В соответствии с этим правилом -111 / 11 может быть только -10, а не 1. Так как (a/b)*b + a%b должно быть равно a, мы имеем -111 % 11 is -1.

Однако K & R Chapter 2.5 дает другой ответ:

Направление усечения для/и знак результата для% зависят от машины для отрицательных операндов, так же как и действие, выполняемое при переполнении или потоке.

В соответствии с этим, либо -1, либо 10 может быть юридическим результатом.

Причина в C89 3.3.5:

Когда целые числа делятся и деление неточно, если оба операнда положительны, результатом оператора/является наибольшее целое число, меньшее, чем алгебраическое отношение, а результат оператора% положителен. Если либо операнд отрицательный, то ли результат оператора/является наибольшим целым числом, меньшим, чем алгебраическое отношение, или наименьшее целое число, большее, чем алгебраическое отношение, определяется реализацией, равно как и признак результата оператора%. Если частное a/b представимо, выражение (a/b) * b + a% b должно быть равно a.

Оказывается, это изменение от C89 до C99.

C99 Обоснование 6.5.5 содержит некоторые исторические причины:

В C89 разделение целых чисел с отрицательными операндами может округлять вверх или вниз в соответствии с реализацией; цель заключалась в том, чтобы избежать накладных расходов во время выполнения кода, чтобы проверить особые случаи и обеспечить соблюдение определенного поведения. Однако в Fortran результат всегда будет усекаться до нуля, а служебные данные, по-видимому, приемлемы для сообщества численного программирования. Следовательно, C99 теперь требует аналогичного поведения, что должно облегчить перенос кода из Fortran на C. Таблица в §7.20.6.2 этого документа иллюстрирует требуемую семантику.

И вот таблица в §7.20.6.2:

numer denom quot rem
 7      3    2    1
–7      3   –2   –1
 7     –3   –2    1
–7     –3    2   –1

Ответ 2

Для модуля, -1 будет неправильным ответом.

Оператор

C % - оператор остатка, а не оператор модуля, хотя и для остатка допустимы либо 10, либо -1.

Ответ 3

Оператор % реализован таким образом, что a == b * (a / b) + (a % b) является истинным, где мы используем целочисленное деление.

В этом случае -111 / 11 есть -10, поэтому -111 == 11 * -10 + x выполняется x == -1.