当前位置： 文江博客话题详情

Python 风格的整数除法 C 的模数

发布于 2024-07-19 04:19:29 字数 379 浏览 7 评论 0原文

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

原文

In Python and Ruby, signed integer division truncates towards negative infinity, and signed integer modulus has the same sign the second operand:

>>> (-41) / 3
-14
>>> (-41) % 3
1

However, in C and Java, signed integer division truncates towards 0, and signed integer modulus has the same sign as the first operand:

printf("%d\n", (-41) / 3); /* prints "-13" */
printf("%d\n", (-41) % 3); /* prints "-2" */

What is the simplest and most efficient way in C to perform the same kind of division and modulus as in Python and Ruby?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（7）

我不吻晚风 2024-07-26 04:19:29

旧 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++ 中的负数。

The direction for rounding with signed integer division is not specified in older C standards. However, in C99 it is specified to round towards zero.

Here's portable code which works with all versions of the C standards and CPU architectures:

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

I did some superficial tests and it appears to give the same results as Python. This code may not be maximally efficient, but a good C compiler can probably optimize it adequately, especially if you put the code in a header as static functions.

You may also want to take a look at this closely related question: Integer division rounding with negatives in C++.

回复 原文
睡美人的小仙女 2024-07-26 04:19:29

对于模数，我发现以下最简单。 实现的符号约定是什么并不重要，我们只需将结果强制为我们想要的符号：

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

我们可以使用一个小气的二值“sign”函数，因为我们已经知道 a!=0，否则 % 将是未定义的。

将相同的原理应用于除法（查看输出而不是输入）：

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

乘法可以说可能比必要的更昂贵，但如果需要，可以稍后在每个架构的基础上进行微优化。 例如，如果您有一个除法运算可以为您提供商和余数，那么您将按除法排序。

[编辑：在某些边缘情况下可能会出错，例如商或余数为 INT_MAX 或 INT_MIN。 但无论如何，模拟大值的 python 数学是一个完全不同的问题;-)]

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

For modulo, I find the following simplest. It doesn't matter what the implementation's sign convention is, we just coerce the result to the sign we want:

r = n % a;
if (r < 0) r += a;

Obviously that's for positive a. For negative a you need:

r = n % a;
if (r > 0) r += a;

Which (perhaps a little confusingly) combines to give the following (in C++. In C do the same thing with int, and then tediously write a duplicate for 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;
}

We can use a cheapskate two-valued "sign" function because we already know a!=0, or the % would be undefined.

Applying the same principle to division (look at the output rather than the input):

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

The multiplications arguably could be more expensive than necessary, but can be micro-optimised later on a per-architecture basis if need be. For instance if you have a division op that gives you quotient and remainder, then you're sorted for division.

[Edit: there might be some edge cases where this goes wrong, for instance if the quotient or the remainder is INT_MAX or INT_MIN. But emulating python maths for large values is a whole other question anyway ;-)]

[Another edit: isn't the standard python implementation written in C? You could trawl the source for what they do]

回复 原文
悲凉≈ 2024-07-26 04:19:29

这个问题有一个解决方案，它比已经提出的解决方案短得多（在代码中）。 我将使用 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 的解决方案进行基准测试时，很明显该解决方案的执行速度只有一半。

教训是：虽然分支指令使代码变慢，但除法指令更糟糕！

我想我还是发布了这个解决方案，只是为了它的优雅。

There is a solution to this question that is much shorter (in code) than the already presented ones. I will use the format of Ville Laurikari's answer for mine:

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

Unfortunately, it seems that the above solutions are not performing well. When benchmarking this solution against the one of Ville Laurikari, it becomes apparent that this solution performs only half as fast.

The lesson is: While branching instructions make code slow, division instructions are much worse!

I thought I nevertheless post this solution if only for its elegance.

回复 原文
橙味迷妹 2024-07-26 04:19:29

下面是 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 因为它具有well-定义的行为。

如果您使用的是 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 中除法和模数的行为不再依赖于实施。

Here is a simple implementation of floored division and modulus in 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;
}

Here, div is used because it has well-defined behavior.

If you're using C++11, here is a templated implementation of floored division and modulus:

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

In C99 and C++11, you can avoid using div since the behavior of division and modulus in C are no longer depend on the implementation.

回复 原文
仅冇旳回忆 2024-07-26 04:19:29

该问题询问如何模拟 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的行为
各自的操作。

The question asked about how to emulate Python-style integer division and modulo. All of the answers given here assume the operands of this operation to be integers themselves but Python can also use floats for its modulo operation. Thus, I think the following answer solves the problem even better:

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

And for the modulo:

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

I tested the above two programs against how Python behaves using the following test code:

#!/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)

The above will compare the behaviour of Python division and modulo with the C
implementations I presented on 6320 testcases. Since the comparison succeeded,
I believe that my solution correctly implements Python's behaviour of the
respective operations.

回复 原文
云柯 2024-07-26 04:19:29

由于还没有人发布，这里是来自 Python 的实际代码 (Python-3.12.1/Objects/longobject.c:3982)。 请注意，Python“数字”始终为正数，并且符号单独存储，因此 left 和 right 是两个参数的绝对值。

/* 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);
}

Since nobody has posted it yet, here is the actual code from Python (Python-3.12.1/Objects/longobject.c:3982). Note that Python "digits" are always positive, with the sign stored separately, so left and right are the absolute values of the two arguments.

/* 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);
}
回复 原文
非要怀念 2024-07-26 04:19:29

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

我对它们的效率没有做出任何断言。

It delves into the ugly world of floats, but these give correct answers in 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);
}

I make no assertions about their efficiency.

回复 原文
~没有更多了~

关于作者

放我走吧

暂无简介

0 文章
0 评论
21 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

不再见

文章 0 评论 0

真是无聊啊

文章 0 评论 0

樱娆

文章 0 评论 0

浅语花开

文章 0 评论 0

烛光

文章 0 评论 0

绻影浮沉

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文