Одна из моих любимых ненавистников к языкам, производным от C (как математик), заключается в том, что
(-1) % 8 // comes out as -1, and not 7
fmodf(-1,8) // fails similarly
Какое лучшее решение?
C ++ допускает возможность использования шаблонов и перегрузки операторов, но и то, и другое для меня непонятно. примеры с благодарностью получены.
%
говорят, по модулю ... это остаток .%
проблеме.(-1) & 8 == 7
Ответы:
Прежде всего, хочу отметить, что на это нельзя даже рассчитывать
(-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:
источник
INT_MIN / -1
(в двух реализациях дополнения). В соответствии со старой спецификацией,-32768 % -1
возможно, придется оценивать значение-65536
(которое также не входит в диапазон 16-битного типа, фу!), Чтобы идентичность сохранялась.Вот функция 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 )
Выход:
источник
floor()
. Кроме того, вы можете потерять точность при преобразовании в float: попробуйте(float)1000000001/3
, вы будете удивлены результатами!Я только что заметил, что Бьярн Страуструп помечает
%
как оператор остатка , а не оператор по модулю.Я готов поспорить, что это его формальное название в спецификациях ANSI C и C ++, и что злоупотребление терминологией закралось. Кто-нибудь знает это наверняка?
Но если это так, то функция C fmodf () (и, возможно, другие) вводит в заблуждение. они должны быть помечены как fremf () и т. д.
источник
%
).Самая простая общая функция для нахождения положительного по модулю будет следующая: она будет работать как с положительными, так и с отрицательными значениями x.
int modulo(int x,int N){ return (x % N + N) %N; }
источник
Для целых чисел это просто. Просто делать
(((x < 0) ? ((x % N) + N) : x) % N)
где я предполагаю, что
N
это положительно и представимо в видеx
. Ваш любимый компилятор должен быть в состоянии оптимизировать это так, чтобы он завершился всего за одну операцию модификации в ассемблере.источник
int x=-9001; unsigned int N=2000;
дает 2295, а не 999.(x < 0) ? (x % N + N) : (x % N)
.Лучшее решение ¹ для математика - использовать 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 округляется до отрицательной бесконечности.
источник
r
результат должен бытьa
=r + b*(a/b)
true. независимо от того, как реализовано целочисленное деление, оноb*something
кратноb
. это даетr
действительный результат по модулю, даже если он отрицательный. вы можете добавить к нему abs (b
), и он все равно будет действительным результатом по модулю.О, я тоже ненавижу дизайн за это ...
Вы можете преобразовать дивиденды в беззнаковые следующим образом:
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
Он очень короткий, но используются два процента, которые обычно медленные.
источник
Я считаю, что другим решением этой проблемы было бы использование переменных типа long вместо int.
Я просто работал над некоторым кодом, в котором оператор% возвращал отрицательное значение, что вызывало некоторые проблемы (для генерации однородных случайных величин на [0,1] вам действительно не нужны отрицательные числа :)), но после переключения переменных на type long, все шло гладко, и результаты совпадали с теми, которые я получал при запуске того же кода на Python (это важно для меня, так как я хотел иметь возможность генерировать одинаковые «случайные» числа на нескольких платформах.
источник
Вот новый ответ на старый вопрос, основанный на этом документе Microsoft Research и ссылках в нем.
Обратите внимание, что начиная с 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);
При евклидовом делении знак остатка всегда положительный .
источник
Для решения, которое не использует веток и только 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); }
источник
... или просто привыкните к любому представителю класса эквивалентности.
источник
r
.%
Оператор не имеет ничего общего с классами эквивалентности. Это оператор остатка, а остаток хорошо определен алгебраически как неотрицательный и меньший, чем делитель. К сожалению, C неправильно определил это. Тем не менее, +1 за один из лучших ответов.Пример шаблона для 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 ++, когда остаток равен нулю или имеет тот же знак, что и делимое ( числитель) (эквивалент округления до нуля).
источник
define MOD(a, b) ((((a)%(b))+(b))%(b))
источник
unsigned mod(int a, unsigned b) { return (a >= 0 ? a % b : b - (-a) % b); }
источник
Это решение (для использования при
mod
положительном значении) позволяет избежать одновременного использования отрицательных операций деления или остатка:int core_modulus(int val, int mod) { if(val>=0) return val % mod; else return val + mod * ((mod - val - 1)/mod); }
источник
Я бы сделал:
((-1)+8) % 8
Это добавляет последнее число к первому перед тем, как выполнить операцию по модулю, дающую 7 по желанию. Это должно работать для любого числа до -8. Для -9 прибавьте 2 * 8.
источник
-99999
?