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

86

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

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

fmodf(-1,8) // fails similarly

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

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

Число Пи
источник
1
Я не думаю, что это настоящий «дубликат» stackoverflow.com/questions/828092/… в соответствии с официальным определением. Неверно, что ответы на этот вопрос можно объединить с этим, потому что этот вопрос спрашивает только о модуле, а не о делении. Но я думаю, что этот вопрос покрывается этим, так что он близок. Мой ответ уже есть, FWIW.
Стив Джессоп,
Может быть, эту ветку следует разделить, поскольку она задает два отдельных вопроса. лучший способ сделать это - повторно задать вопрос о разделении отдельно, а затем направить его к этому ответу. Я оставлю это тому, кто лучше разбирается в механизмах этого сайта.
P i
3
@Pi owhere как %говорят, по модулю ... это остаток .
obataku 09
1
Вот еще один поток, который является «дубликатом»: stackoverflow.com/questions/1082917/… Просто для справки по этой %проблеме.
leetNightshade
Если вы делите только силы двух, то, возможно, было бы лучше использовать и:(-1) & 8 == 7
Хенрикус В.

Ответы:

74

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

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

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

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

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

Армен Цирунян
источник
2
@Ohmu: Да, это в стандарте C ++. <quote> Для целочисленных операндов оператор / возвращает алгебраическое частное с отброшенной дробной частью; если частное a / b представимо в типе результата, (a / b) * b + a% b равно a. </quote>
Бен Фойгт,
5
-1. Прошло 11 лет с тех пор, как эта реализация была определена. ISO 9899: 1999 определил это, но, к сожалению, выбрал плохое определение.
R .. GitHub НЕ ПОМОГАЕТ ICE
3
@Armen: Вы удалили сноску <quote> ... целочисленное деление следует правилам, определенным в стандарте ISO Fortran, ISO / IEC 1539: 1991, в котором частное всегда округляется до нуля </quote>. Новый стандарт C ++ модернизирует это поведение с «предпочтительного» до обязательного, точно так же, как Fortran и C.
Бен Фойгт
2
@Armen: Старая спецификация не работает, но поломка отличается от проблемы со знаком, и ее легко пропустить, пока вы не посмотрите новую формулировку. В C ++ 03 не было «если частное a / b представимо в типе результата», что вызывает проблемы для INT_MIN / -1(в двух реализациях дополнения). В соответствии со старой спецификацией, -32768 % -1возможно, придется оценивать значение -65536(которое также не входит в диапазон 16-битного типа, фу!), Чтобы идентичность сохранялась.
Бен Фойгт,
1
re «Однако, является ли остаток отрицательным, определяется реализацией.», C ++ 11 гарантирует, что целочисленное деление округляется до 0.
Ура и hth. - Alf
12

Вот функция 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 и отдельную функцию для 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

Число Пи
источник
К сожалению, с целыми числами это не работает. Их необходимо преобразовать в числа с плавающей запятой перед делением, чтобы вы могли их использовать floor(). Кроме того, вы можете потерять точность при преобразовании в float: попробуйте (float)1000000001/3, вы будете удивлены результатами!
cmaster - восстановить
9

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

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

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

Число Пи
источник
1
Стандарт C11 (или, если быть точным, окончательный публичный проект ) упоминает «по модулю» шесть раз, но только в отношении представления различных типов. Ни разу не упоминается «по модулю» по отношению к оператору остатка ( %).
Nisse Engström
7

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

int modulo(int x,int N){
    return (x % N + N) %N;
}
Удайрадж Дешмукх
источник
6

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

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

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

Йенс Густедт
источник
3
Не работает: int x=-9001; unsigned int N=2000;дает 2295, а не 999.
Hubert Kario
1
@HubertKario Может быть, еще раз проверим? Невозможно, чтобы что-то по модулю 2000 давало 2295, вы, должно быть, ошиблись.
Sam Hocevar
2
@SamHocevar: Я думаю, что проблема здесь в странных правилах продвижения целых чисел C.
преобразование
1
Я считаю, что гораздо проще (и более эффективная) форма будет: (x < 0) ? (x % N + N) : (x % N).
Крис Нолет
3

Лучшее решение ¹ для математика - использовать 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 округляется до отрицательной бесконечности.

Приветствия и hth. - Альф
источник
похоже, в вашем коде та же ошибка, что и в моем до моего редактирования. Что делать, если b отрицательно? :)
Армен Цирунян
1
@Armen: спасибо! но мне лень редактировать только это ... :-)
Ура и hth. - Альф,
@ArmenTsirunyan: rрезультат должен быть a= r + b*(a/b)true. независимо от того, как реализовано целочисленное деление, оно b*somethingкратно b. это дает rдействительный результат по модулю, даже если он отрицательный. вы можете добавить к нему abs ( b), и он все равно будет действительным результатом по модулю.
Приветствия и hth. - Alf
2
@downvoters: этот ответ по-прежнему верен, хотя выбранное «решение» теперь содержит неверный комментарий из-за новых гарантий в C ++ 11. Довольно иронично отрицать ответ, который все еще верен. Без указания причин следует предположить, что по крайней мере 2 ассоциативных человека с почти абсолютной степенью невежества прочитали комментарий к этому вопросу и были ассоциативно отвергнуты. Пожалуйста, объясните свои отрицательные голоса.
Приветствия и hth. - Альф
1
Математически желаемый результат состоит в том, чтобы остаток был равен нулю или имел тот же знак, что и делитель (знаменатель). Если делитель отрицательный, то остаток должен быть нулевым или отрицательным. Реализация C / C ++ приводит к тому, что остаток равен нулю или имеет тот же знак, что и делимое (числитель).
rcgldr
2

О, я тоже ненавижу дизайн за это ...

Вы можете преобразовать дивиденды в беззнаковые следующим образом:

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

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

Вованиум
источник
2

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

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

Дэвид
источник
2

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

Обратите внимание, что начиная с C11 и C ++ 11 семантика divстала усечением до нуля (см. [expr.mul]/4). Кроме того, для деления Dна dC ++ 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);

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

TemplateRex
источник
2

Для решения, которое не использует веток и только 1 мод, вы можете сделать следующее

// Works for other sizes too,
// assuming you change 63 to the appropriate value
int64_t mod(int64_t x, int64_t div) {
  return (x % div) + (((x >> 63) ^ (div >> 63)) & div);
}
Кайл Батт
источник
1
/ * Предупреждение: макромод многократно оценивает побочные эффекты своих аргументов. * /
#define mod (r, m) (((r)% (m)) + ((r) <0)? (m): 0)

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

Эрик Тауэрс
источник
2
«Привыкайте к любому представителю класса эквивалентности» ?! Это чепуха. Если вы этого хотите, вы можете просто использовать оригинального «представителя» r. %Оператор не имеет ничего общего с классами эквивалентности. Это оператор остатка, а остаток хорошо определен алгебраически как неотрицательный и меньший, чем делитель. К сожалению, C неправильно определил это. Тем не менее, +1 за один из лучших ответов.
R .. GitHub НЕ ПОМОГАЕТ ICE
0

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

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

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

rcgldr
источник
-1
unsigned mod(int a, unsigned b) {
    return (a >= 0 ? a % b : b - (-a) % b);
}
Neuer
источник
-1

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

int core_modulus(int val, int mod)
{
    if(val>=0)
        return val % mod;
    else
        return val + mod * ((mod - val - 1)/mod);
}
Роботы-жуки
источник
-2

Я бы сделал:

((-1)+8) % 8 

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

Тоби О'Коннелл
источник
2
А для переменной, значение которой может быть -99999?
Кейт Томпсон,