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中执行相同类型的除法和模数的最简单,最有效的方法是什么？

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++中用负数舍入.

Answer 2

对于模数,我发现以下最简单.实现的符号约定无关紧要,我们只是将结果强制转换为我们想要的符号:

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;
}

我们可以使用cheapskate二值"符号"函数,因为我们已经知道了!= 0,或者%将是未定义的.

将相同的原理应用于除法(查看输出而不是输入):

q = n / a;
// assuming round-toward-zero
if ((q < 0) && (q * a != n)) --q;

这些乘法可能比必要的更昂贵,但如果需要,可以在每个架构的基础上进行微优化.例如,如果你有一个为你提供商和余数的除法运算,那么你就会对除法进行排序.

[编辑:可能存在一些出现问题的边缘情况,例如,如果商或余数是INT_MAX或INT_MIN.但是,为大值模拟python数学无论如何都是另一个问题;-)]

[另一个编辑:不是用C编写的标准python实现吗？你可以搜索他们所做的事情的来源]