Как кодировать оператор по модулю (%) в C / C ++ / Obj-C, который обрабатывает отрицательные числа

Question

Одна из моих любимых ненавистей к C-производным языкам (как к математике) заключается в том, что

(-1) % 8 // comes out as -1, and not 7

fmodf(-1,8) // fails similarly

Какое лучшее решение?

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

Answer 1

Прежде всего я хотел бы отметить, что вы даже не можете полагаться на тот факт, что (-1) % 8 == -1.единственное, на что вы можете положиться - это (x / y) * y + ( x % y) == x.Однако, является ли остаток отрицательным, определяется реализацией .

Теперь зачем использовать шаблоны здесь?Перегрузка для целых и длинных будет делать.

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

, и теперь вы можете назвать его как мод (-1,8), и он будет 7.

Редактировать: Я нашелошибка в моем коде.Это не сработает, если b отрицательно.Поэтому я думаю, что это лучше:

int mod (int a, int b)
{
   if(b < 0) //you can check for b == 0 separately and do what you want
     return mod(a, -b);   
   int ret = a % b;
   if(ret < 0)
     ret+=b;
   return ret;
}

Ссылка: C ++ 03, параграф 5.6, пункт 4:

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

Answer 2

Вот функция C, которая обрабатывает положительные ИЛИ отрицательные целые ИЛИ дробные значения для ОБОИХ ОПЕРАНДОВ

#include <math.h>
float mod(float a, float N) {return a - N*floor(a/N);} //return in range [0, N)

Это, безусловно, самое элегантное решение с математической точки зрения.Тем не менее, я не уверен, что он надежен в обработке целых чисел.Иногда ошибки с плавающей точкой появляются при преобразовании int -> fp -> int.

. Я использую этот код для не-int s и отдельную функцию для int.

ПРИМЕЧАНИЕ.ловушка N = 0!

Код тестера:

#include <math.h>
#include <stdio.h>

float mod(float a, float N)
{
    float ret = a - N * floor (a / N);

    printf("%f.1 mod %f.1 = %f.1 \n", a, N, ret);

    return ret;
}

int main (char* argc, char** argv)
{
    printf ("fmodf(-10.2, 2.0) = %f.1  == FAIL! \n\n", fmodf(-10.2, 2.0));

    float x;
    x = mod(10.2f, 2.0f);
    x = mod(10.2f, -2.0f);
    x = mod(-10.2f, 2.0f);
    x = mod(-10.2f, -2.0f);

    return 0;
}

(Примечание. Вы можете скомпилировать и запустить его прямо из CodePad: http://codepad.org/UOgEqAMA)

Вывод:

fmodf (-10.2, 2.0) = -0.20 == FAIL!

10.2 мод 2.0 = 0.2
10.2 мод -2.0 = -1.8
-10.2 мод 2.0 = 1.8
-10,2 мод -2,0 = -0,2

Answer 3

Я только что заметил, что Бьярн Страуструп помечает % как оператор остаток , не оператор по модулю.

Держу пари, что это формальноимя в спецификациях ANSI C & C ++, и это закралось злоупотребление терминологией. Кто-нибудь знает это наверняка?

Но если это так, то функция C fmodf () С (и, вероятно, другие)очень вводит в заблуждение.они должны быть помечены как fremf () и т. д.

Answer 4

Для целых чисел это просто. Просто сделай

(((x < 0) ? ((x % N) + N) : x) % N)

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

Answer 5

Простейшая общая функция для нахождения положительного по модулю была бы такой: она работала бы как с положительными, так и с отрицательными значениями x.

int modulo(int x,int N){
    return (x % N + N) %N;
}

Answer 6

Лучшее решение для математика - использовать Python.

Перегрузка оператора C ++ имеет мало общего с этим.Вы не можете перегружать операторы для встроенных типов.То, что вы хотите, это просто функция.Конечно, вы можете использовать шаблоны C ++ для реализации этой функции для всех соответствующих типов всего с одним фрагментом кода.

Стандартная библиотека C предоставляет fmod, если я правильно помню имя, для типов с плавающей запятой.

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

#include <stdlib.h>  // abs

template< class Integer >
auto mod( Integer a, Integer b )
    -> Integer
{
    Integer const r = a%b;
    return (r < 0? r + abs( b ) : r);
}

... и просто напишите mod(a, b) вместоиз a%b.

Здесь тип Integer должен быть целочисленным типом со знаком.

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

template< class Integer >
auto floor_div( Integer const a, Integer const b )
    -> Integer
{
    bool const a_is_negative = (a < 0);
    bool const b_is_negative = (b < 0);
    bool const change_sign  = (a_is_negative != b_is_negative);

    Integer const abs_b         = abs( b );
    Integer const abs_a_plus    = abs( a ) + (change_sign? abs_b - 1 : 0);

    Integer const quot = abs_a_plus / abs_b;
    return (change_sign? -quot : quot);
}

template< class Integer >
auto floor_mod( Integer const a, Integer const b )
    -> Integer
{ return a - b*floor_div( a, b ); }

… с тем же ограничением на Integer, что это тип со знаком.

---

^{¹ Поскольку целое число Pythonделение округляет в сторону отрицательной бесконечности.}

Answer 7

Я полагаю, что другим решением этой проблемы было бы использование переменных типа long вместо int.

Я просто работал над кодом, в котором оператор% возвращал отрицательное значение, что вызывало некоторые проблемы (для генерации единообразных случайных величин на [0,1] вы не хотите, чтобы отрицательные числа :)), но после переключения переменные для длинного набора, все работало гладко, и результаты соответствовали тем, которые я получал при запуске одного и того же кода на python (для меня это было важно, так как я хотел иметь возможность генерировать одинаковые «случайные» числа на нескольких платформах.

Answer 8

О, я тоже ненавижу% design для этого ....

Вы можете конвертировать дивиденды в беззнаковые таким образом, как:

unsigned int offset = (-INT_MIN) - (-INT_MIN)%divider

result = (offset + dividend) % divider

, где смещение ближе всего к (-INT_MIN) несколько модулей, поэтому сложение и вычитание не изменится по модулю.Обратите внимание, что у него тип unsigned, и результатом будет целое число.К сожалению, он не может правильно преобразовать значения INT_MIN ... (- offset-1), поскольку они вызывают арифметическое переполнение.Но этот метод имеет преимущество только в одной дополнительной арифметике на операцию (и без условий) при работе с константным делителем, поэтому его можно использовать в приложениях, подобных DSP.

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

dividend&(divider-1)

, например

x mod 2 = x & 1
x mod 4 = x & 3
x mod 8 = x & 7
x mod 16 = x & 15

Более распространенный и менее хитрый способэто получить по модулю, используя эту функцию (работает только с положительным делителем):

int mod(int x, int y) {
    int r = x%y;
    return r<0?r+y:r;
}

Это просто правильный результат, если он отрицательный.

Также вы можете обмануть:

(p% q + q)% q

Это очень короткий, но используйте два% -ых, которые обычно медленны.

Answer 9

Вот новый ответ на старый вопрос, основанный на этой исследовательской работе Microsoft и ссылках в ней.

Обратите внимание, что начиная с C11 и C ++ 11 и выше семантика div стала усечением до нуля (см. [expr.mul]/4). Кроме того, для D, деленного на d, C ++ 11 гарантирует следующее о частном qT и остатке rT

auto const qT = D / d;
auto const rT = D % d;
assert(D == d * qT + rT);
assert(abs(rT) < abs(d));
assert(signum(rT) == signum(D));

, где signum отображается на -1, 0, +1, в зависимости от того, является ли его аргумент <, ==,> чем 0 (см. этот раздел вопросов и ответов для исходного кода).

При усеченном делении знак остатка равен знаку дивиденда D, т. Е. -1 % 8 == -1. C ++ 11 также предоставляет функцию std::div, которая возвращает структуру с членами quot и rem в соответствии с усеченным делением.

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

auto const I = signum(rT) == -signum(d) ? 1 : 0;
auto const qF = qT - I;
auto const rF = rT + I * d;
assert(D == d * qF + rF);
assert(abs(rF) < abs(d));
assert(signum(rF) == signum(d));

При настиленном делении знак остатка равен знаку делителя d. В таких языках, как Haskell и Oberon, есть встроенные операторы для разделения по этажам. В C ++ вам нужно написать функцию, используя приведенные выше определения.

Еще одним способом является евклидово деление , которое также можно определить в терминах встроенного усеченного деления

auto const I = rT >= 0 ? 0 : (d > 0 ? 1 : -1);
auto const qE = qT - I;
auto const rE = rT + I * d;
assert(D == d * qE + rE);
assert(abs(rE) < abs(d));
assert(signum(rE) != -1);

При евклидовом делении знак остатка всегда положительный .

Answer 10

/* Warning: macro mod evaluates its arguments' side effects multiple times. */
#define mod(r,m) (((r) % (m)) + ((r)<0)?(m):0)

... или просто привыкните к любому представителю класса эквивалентности.