Целочисленное деление в стиле Python & amp; модуль в С
Вопрос
В Python и Ruby целочисленное деление со знаком усекается до отрицательной бесконечности, а целочисленный модуль со знаком имеет тот же знак, что и второй операнд:
>>> (-41) / 3
-14
>>> (-41) % 3
1
Однако в C и Java целочисленное деление со знаком усекается до 0, а целочисленный модуль со знаком имеет тот же знак, что и первый операнд:
printf("%d\n", (-41) / 3); /* prints "-13" */
printf("%d\n", (-41) % 3); /* prints "-2" */
Какой самый простой и эффективный способ в C выполнить такое же деление и модуль, как в Python и Ruby?
Решение
Направление округления с целочисленным делением со знаком не указано в более старых стандартах Си. Однако в C99 указано округление до нуля.
Вот переносимый код, который работает со всеми версиями стандартов C и архитектур ЦП:
int py_div(int a, int b)
{
if (a < 0)
if (b < 0)
return -a / -b;
else
return -(-a / b) - (-a % b != 0 ? 1 : 0);
else if (b < 0)
return -(a / -b) - (a % -b != 0 ? 1 : 0);
else
return a / b;
}
int py_mod(int a, int b)
{
if (a < 0)
if (b < 0)
return -(-a % -b);
else
return -a % b - (-a % -b != 0 ? 1 : 0);
else if (b < 0)
return -(a % -b) + (-a % -b != 0 ? 1 : 0);
else
return a % b;
}
Я провел несколько поверхностных тестов, и он, похоже, дает те же результаты, что и Python. Этот код может быть не максимально эффективным, но хороший компилятор C, вероятно, сможет его адекватно оптимизировать, особенно если вы помещаете код в заголовок как статические функции.
Вы также можете взглянуть на этот тесно связанный вопрос: Integer округление деления с негативами в C ++ .
Другие советы
По модулю я считаю следующее простейшим. Неважно, что такое соглашение о знаке реализации, мы просто приводим результат к желаемому знаку:
r = n % a;
if (r < 0) r += a;
Очевидно, что это положительно. Для негатива вам нужно:
r = n % a;
if (r > 0) r += a;
Который (возможно, немного смущающий) объединяется, чтобы дать следующее (в C ++. В C сделать то же самое с int, а затем утомительно написать дубликат на долгое время):
template<typename T> T sign(T t) { return t > T(0) ? T(1) : T(-1); }
template<typename T> T py_mod(T n, T a) {
T r = n % a;
if (r * sign(a) < T(0)) r += a;
return r;
}
Мы можем использовать двузначный знак "знак" функция, потому что мы уже знаем! = 0, иначе% будет неопределенным.
Применяя тот же принцип к делению (посмотрите на вывод, а не на ввод):
q = n / a;
// assuming round-toward-zero
if ((q < 0) && (q * a != n)) --q;
Умножения, возможно, могут быть более дорогими, чем необходимо, но могут быть микрооптимизированы позже для каждой архитектуры в случае необходимости. Например, если у вас есть операция деления, которая дает вам частное и остаток, то вы отсортированы по делению.
[Редактировать: могут быть некоторые крайние случаи, когда это идет не так, например, если частное или остаток - INT_MAX или INT_MIN. Но в любом случае подражание математике Python для больших значений - это совсем другой вопрос; -)]
[Другое редактирование: разве стандартная реализация python написана на C? Вы можете тралить источник за то, что они делают]
Вот простая реализация разделенного по этажам деления и модуля в C89:
#include <stdlib.h>
div_t div_floor(int x, int y)
{
div_t r = div(x, y);
if (r.rem && (x < 0) != (y < 0)) {
r.quot -= 1;
r.rem += y;
}
return r;
}
Здесь используется div
, поскольку он имеет четко определенное поведение .
Если вы используете C ++ 11, вот шаблонная реализация разделенного на части деления и модуля:
#include <tuple>
template<class Integral>
std::tuple<Integral, Integral> div_floor(Integral x, Integral y)
{
typedef std::tuple<Integral, Integral> result_type;
const Integral quot = x / y;
const Integral rem = x % y;
if (rem && (x < 0) != (y < 0))
return result_type(quot - 1, rem + y);
return result_type(quot, rem);
}
В C99 и C ++ 11 вы можете избежать использования div
, поскольку поведение деления и модуля в C больше не зависит от реализации.
Существует решение этого вопроса, которое намного короче (в коде), чем уже представленные. Я буду использовать формат ответа Вилле Лаурикари для моего:
int py_div(int a, int b)
{
return (a - (((a % b) + b) % b)) / b);
}
int py_mod(int a, int b)
{
return ((a % b) + b) % b;
}
К сожалению, вышеприведенные решения неэффективны. При сравнении этого решения с Ville Laurikari становится очевидно, что это решение работает только вдвое быстрее.
Урок: несмотря на то, что инструкции ветвления делают код медленным, инструкции деления намного хуже!
Я думал, что все же выложу это решение хотя бы из-за его элегантности.
Был задан вопрос о том, как эмулировать целочисленное деление в стиле Python и по модулю. Во всех приведенных здесь ответах предполагается, что операнды этой операции сами по себе являются целыми числами, но Python также может использовать числа с плавающей запятой для своей операции по модулю. Таким образом, я думаю, что следующий ответ решает проблему еще лучше:
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
int pydiv(double a, double b) {
int q = a/b;
double r = fmod(a,b);
if ((r != 0) && ((r < 0) != (b < 0))) {
q -= 1;
}
return q;
}
int main(int argc, char* argv[])
{
double a = atof(argv[1]);
double b = atof(argv[2]);
printf("%d\n", pydiv(a, b));
}
И по модулю:
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
double pymod(double a, double b) {
double r = fmod(a, b);
if (r!=0 && ((r<0) != (b<0))) {
r += b;
}
return r;
}
int main(int argc, char* argv[])
{
double a = atof(argv[1]);
double b = atof(argv[2]);
printf("%f\n", pymod(a, b));
}
Я протестировал две вышеупомянутые программы на соответствие поведению Python, используя следующий тестовый код:
#!/usr/bin/python3
import subprocess
subprocess.call(["cc", "pydiv.c", "-lm", "-o", "cdiv"])
subprocess.call(["cc", "pymod.c", "-lm", "-o", "cmod"])
def frange(start, stop, step=1):
for i in range(0, int((stop-start)/step)):
yield start + step*i
for a in frange(-10.0, 10.0, 0.25):
for b in frange(-10.0, 10.0, 0.25):
if (b == 0.0):
continue
pydiv = a//b
pymod = a%b
cdiv = int(subprocess.check_output(["./cdiv", str(a), str(b)]))
cmod = float(subprocess.check_output(["./cmod", str(a), str(b)]))
if pydiv != cdiv:
exit(1)
if pymod != cmod:
exit(1)
Выше будет сравнивать поведение деления Python и по модулю с C Реализации я представил на 6320 тестовых примерах. Поскольку сравнение прошло успешно, Я считаю, что мое решение правильно реализует поведение Python соответствующие операции.
Он погружается в уродливый мир поплавков, но они дают правильные ответы на Java:
public static int pythonDiv(int a, int b) {
if (!((a < 0) ^ (b < 0))) {
return a / b;
}
return (int)(Math.floor((double)a/(double)b));
}
public static int pythonMod(int a, int b) {
return a - b * pythonDiv(a,b);
}
Я не делаю никаких утверждений об их эффективности.