C语言中的Python风格整数除法和取模运算

Question

在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相同类型的除法和取模运算？

- user102008

---

在 JavaScript 中同样会发生这种情况：(-41) % 3 === -2。 - VFDan

Answer 1

在早期的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++中使用负数进行整数除法舍入。

- Ville Laurikari

---

如果你想要高效率，使用查找表。如果这段代码是一个效率问题，唯一真正的替代方案就是使用常规的 / 和 % 运算符，并接受它们的舍入。 - Chris Lutz

这很不错。在这段代码中加入一些括号会很有帮助（由于有太多的条件嵌套，很难分清发生了什么……）。 - Jonathan Sterling

当被除数或除数为负数时，此代码不会产生正确的模数。 - Rufflewind

@VilleLaurikari：这不应该是b:0而不是1:0吗？这对我来说似乎有效： int py_mod(int a, int b) { if ((a >= 0) == (b >= 0)) return a % b; else return (a % -b) + ((a % -b) != 0 ? b : 0); } - Dwayne Robinson

注意！py_mod在a = -1611640551, b = 2的情况下给出了错误的答案。Python返回1，而答案中的代码段返回0。 - kelin

Answer 2

对于取模运算，我认为下面的方法最简单。实现的符号约定无关紧要，我们只需将结果强制转换为所需的符号：

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编写的吗？您可以查看源代码以了解他们的做法]

- Steve Jessop

Answer 3

这个问题有一个比已经呈现的解决方案更短（在代码方面）的解决方案。我将使用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的解决方案进行基准测试时，这个解决方案只有一半的速度。

教训是：分支指令会使代码变慢，而除法指令则更糟糕！

我认为我还是发布这个解决方案，即使只是因为它的优雅。

- josch

---

有没有任何指向它为什么有效的指针，无论是证明还是直观解释？ - Emilio M Bumachar

@EmilioMBumachar 尝试将值插入表达式中，你会看到结果。例如，对于 a=-1 和 b=3，((-1%3)+3)%3=2，但是对于 a=1 和 b=3，((1%3)+3)%3=1，如预期的那样。 - sodiumnitrate

Answer 4

以下是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中，由于C中除法和取模的行为不再依赖于实现，因此您可以避免使用div。

- Rufflewind

Answer 5

这个问题询问如何模拟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除法和模运算的行为与我在6320个测试用例中展示的C实现。由于比较成功，我相信我的解决方案正确地实现了Python相应操作的行为。

- josch

Answer 6

它深入探讨了浮点数的丑陋世界，但在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);
}

我不对它们的效率做任何断言。

- Ry4an Brase

---

虽然这个特定实例可能会为所有可能的输入产生正确的结果，但我仍然会避免它，因为它使用浮点函数进行整数操作。如果您将float替换为double或将long替换为int，则对于某些输入，它将产生错误的结果。此外，如果您将此实例移植到int为64位宽的平台上的C或C++中，它同样会对某些输入产生错误的结果。 - blubberdiblub