C中的Python样式整数除法和模数
在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中执行相同类型的除法和模数的最简单，最有效的方法是什么？
在旧C标准中未指定带有符号整数除法的舍入方向。 但是，在C99中，它被指定为向零舍入。
这里的可移植代码适用于所有版本的C标准和CPU架构：
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编译器可以充分地优化它，特别是如果你把代码作为静态函数放在头中。
您可能还想看看这个密切相关的问题： 整数除法在C ++中用负数舍入 。
对于模数，我发现以下最简单。 实现的符号约定无关紧要，我们只是将结果强制转换为我们想要的符号：
r = n % a; if (r < 0) r += a;
显然这是积极的。 对于负面的你需要：
r = n % a; if (r > 0) r += a;
哪个（可能有点令人困惑）结合起来给出了以下内容（在C ++中。在C中用int执行相同的操作，然后冗长地编写一个重复的long）：
template T sign(T t) { return t > T(0) ? T(1) : T(-1); } template T py_mod(T n, T a) { T r = n % a; if (r * sign(a) < T(0)) r += a; return r; }
我们可以使用cheapskate二值“符号”函数，因为我们已经知道了！= 0，或者％将是未定义的。
将相同的原理应用于除法（查看输出而不是输入）：
q = n / a; // assuming round-toward-zero if ((q < 0) && (q * a != n)) --q;
可以说，乘法可能比必要的更昂贵，但如果需要，可以在每个架构的基础上进行微优化。 例如，如果你有一个为你提供商和余数的除法运算，那么你就会对除法进行排序。
[编辑：可能存在一些出现问题的边缘情况，例如，如果商或余数是INT_MAX或INT_MIN。 但是，为大值模拟python数学是另外一个问题;-)]
[另一个编辑：是不是用C编写的标准python实现？ 你可以搜索他们所做的事情的来源]
这是C89中的分层和模数的简单实现：
#include 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 template std::tuple div_floor(Integral x, Integral y) { typedef std::tuple 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中除法和模数的行为不再依赖于实现。
这个问题的解决方案比已经提出的解决方案短得多（在代码中）。 我将使用Ville Laurikari的答案格式：
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 #include #include 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 #include #include 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 division和modulo的行为与我在6320测试用例中提供的C实现。 由于比较成功，我相信我的解决方案正确实现了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); }
我对他们的效率没有断言。