在 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 相同的除法和取模的最简单、最有效的方法是什么?
旧 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;
显然这是积极的a。对于负 a 你需要:
r = n % a;
if (r > 0) r += a;
(可能有点令人困惑)组合起来给出以下内容(在 C++ 中。在 C 中,对 int 执行相同的操作,然后冗长地编写一个重复的 long long):
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;
}
我们可以使用一个小气的二值“符号”函数,因为我们已经知道 a!=0,否则 % 将是未定义的。
将相同的原理应用于除法(查看输出而不是输入):
q = n / a;
// assuming round-toward-zero
if ((q < 0) && (q * a != n)) --q;
乘法可以说可能比必要的更昂贵,但如果需要的话,可以稍后在每个架构的基础上进行微优化。例如,如果您有一个除法运算可以为您提供商和余数,那么您将被排序为除法。
[编辑:在某些边缘情况下可能会出错,例如商或余数为 INT_MAX 或 INT_MIN。但无论如何,模拟大值的 python 数学是一个完全不同的问题;-)]
[另一个编辑:标准的 python 实现不是用 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 的解决方案进行基准测试时,很明显该解决方案的执行速度只有一半。
教训是:虽然分支指令使代码变慢,但除法指令更糟糕!
我想我还是发布了这个解决方案,只是为了它的优雅。
这是 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 中的除法和模数行为不再依赖于实现。
问题询问如何模拟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的行为 各自的操作。
由于还没有人发布它,这里是来自 Python 的实际代码(Python-3.12.1/Objects/longobject.c:3982):
/* Fast floor division for single-digit longs. */
static PyObject *
fast_floor_div(PyLongObject *a, PyLongObject *b)
{
sdigit left = a->long_value.ob_digit[0];
sdigit right = b->long_value.ob_digit[0];
sdigit div;
assert(_PyLong_DigitCount(a) == 1);
assert(_PyLong_DigitCount(b) == 1);
if (_PyLong_SameSign(a, b)) {
div = left / right;
}
else {
/* Either 'a' or 'b' is negative. */
div = -1 - (left - 1) / right;
}
return PyLong_FromLong(div);
}
它深入研究了浮点数的丑陋世界,但这些在 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);
}
我不对他们的效率做出任何断言。