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

Ответ 1

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

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

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

и теперь вы можете называть его как mod (-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;
}

Ссылка: С++ 03, пункт 5.6, раздел 4:

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

Ответ 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 mod -2.0 = -0.2

Ответ 3

Я только что заметил, что Bjarne Stroustrup называет % как оператор остаток, а не оператор modulo.

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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

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

#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 ); }

& hellip; с тем же ограничением на Integer, что это подписанный тип.

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

Ответ 6

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

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

Ответ 7

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

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

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

result = (offset + dividend) % divider

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

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

Ответ 8

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

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

Ответ 9

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

... или просто привыкнуть к получению любого представителя для класса эквивалентности.

Ответ 10

Вот новый ответ на старый вопрос, основанный на этом Microsoft Research paper и ссылки на него.

Обратите внимание, что из C11 и С++ 11 семантика div стала усечением в сторону нуля (см. [expr.mul]/4). Кроме того, для D, деленного на D, С++ 11 гарантирует следующее о quotient 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 (см. этот Q & A для исходного кода).

С усеченным делением знак остатка равен знаку дивиденда D, т.е. -1 % 8 == -1. С++ 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, есть встроенные операторы для разделения полов. В С++ вам нужно написать функцию, используя приведенные выше определения.

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

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);

С евклидовым делением знак остатка всегда положителен.

Ответ 11

Пример шаблона для С++

template< class T >
T mod( T a, T b )
{
    T const r = a%b;
    return ((r!=0)&&((r^b)<0) ? r + b : r);
}

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

Ответ 12

Просто (х + мод)% мод

Ответ 13

define  MOD(a, b)       ((((a)%(b))+(b))%(b))

Ответ 14

unsigned mod(int a, unsigned b) {
    return (a >= 0 ? a % b : b - (-a) % b);
}

Ответ 15

Это решение (для использования при mod положительно) позволяет избежать всех операций с отрицательным делением или остатком:

int core_modulus(int val, int mod)
{
    if(val>=0)
        return val % mod;
    else
        return val + mod * ((mod - val - 1)/mod);
}

Ответ 16

Я бы сделал:

((-1)+8) % 8 

Это добавляет последнее число к первому, прежде чем делать по модулю предложение 7 по желанию. Это должно работать для любого числа до -8. Для -9 добавить 2 * 8.