负数的模运算让我感到困扰

Question

我试图对一个整数取模，以便得到一个数组位置，使其能够循环。对于正数来说，i % arrayLength 运行良好，但对于负数则会出现问题。

 4 % 3 == 1
 3 % 3 == 0
 2 % 3 == 2
 1 % 3 == 1
 0 % 3 == 0
-1 % 3 == -1
-2 % 3 == -2
-3 % 3 == 0
-4 % 3 == -1

所以我需要一个实现

int GetArrayIndex(int i, int arrayLength)

< p >这样的

GetArrayIndex( 4, 3) == 1
GetArrayIndex( 3, 3) == 0
GetArrayIndex( 2, 3) == 2
GetArrayIndex( 1, 3) == 1
GetArrayIndex( 0, 3) == 0
GetArrayIndex(-1, 3) == 2
GetArrayIndex(-2, 3) == 1
GetArrayIndex(-3, 3) == 0
GetArrayIndex(-4, 3) == 2

我以前做过这个，但出于某种原因，今天它让我感到很棘手:(

- gormenghastly

---

请参阅有关http://math.stackexchange.com/questions/519845/modulo-of-a-negative-number的**数学**模数讨论。 - PPC

https://blogs.msdn.microsoft.com/ericlippert/2011/12/05/whats-the-difference-remainder-vs-modulus/ 是一篇很棒的文章。 - Samra

Answer 1

我总是使用自己定义的mod函数，其定义为：

int mod(int x, int m) {
    return (x%m + m)%m;
}

如果你关心对模数操作进行了两次调用，当然可以这样编写：

int mod(int x, int m) {
    int r = x%m;
    return r<0 ? r+m : r;
}

或其变体。

它能够运行的原因是，“x％m”始终在[-m+1，m-1]范围内。因此，如果它是负数，将m添加到它上面就会将其放入正范围内，而不改变其对m取模的值。

- ShreevatsaR

---

注意：为了完整的数论完备性，你可能需要在顶部添加一行代码“if(m<0) m=-m;”，尽管在这种情况下它并不重要，因为“arrayLength”很可能总是正数。 - ShreevatsaR

如果你要检查变量m的值，也应该排除零。 - billpg

@billpg：对于 m=0，mod 运算未定义，因此无法期望该函数对该情况执行任何操作。在我看来，检查这一点应该由调用者负责。（没有人应该希望有任何数 mod 0 的结果。）另一方面，对于负的 m，mod 运算是有定义的，因此如果该函数可能会被调用时 m 为负数，则建议修复代码中的错误。无论如何，错误检查/处理应该在哪里完成是一个长期存在的问题 ：p - ShreevatsaR

不需要while循环。如果x=-5，m=2，则r=x%m为-1，之后r+m为1。关键在于（正如我在回答中所写的），x%m始终严格大于-m，因此最多只需加m一次即可使其为正数。 - ShreevatsaR

我会尽力为您翻译：我并不关心任何一种语言对于负模数的处理方式，但“最小非负剩余”表现出一种数学规律并消除了任何歧义。 - Brett Hale

Answer 2

请注意，C＃和C ++的%运算符实际上不是取模运算，而是余数运算。在您的情况下需要使用的取模公式为：

float nfmod(float a,float b)
{
    return a - b * floor(a / b);
}

你需要在C# (或 C++)中重新编写此代码，这是获取模数而不是余数的方法。

- Петър Петров

---

请注意，C++的%运算符实际上不是模运算，而是余数运算。谢谢，现在我明白了，之前一直不清楚为什么它不能正确地处理负数。 - leetNightshade

请注意，C++的%运算符实际上不是模运算，而是余数。我认为这不准确，也不明白为什么模运算会有所不同。维基百科上的模运算页面也说明了这一点。只是编程语言对负数处理方式不同。在C#中，模运算符显然从零开始计算余数（-9％4 = -1，因为4 * -2是-8，差为-1），而另一种定义则将-9％4视为+3 ，因为-4 * 3为-12，余数为+3（例如Google的搜索函数中使用的方法，不确定后端语言是什么）。 - Tyress

Tyress，模数和余数是有区别的。举个例子：-21 mod 4 是3，因为 -21 + 4 x 6 等于3。但是 -21÷4 是-5，带有 余数-1。对于正数而言，两者没有区别。请了解这些差异，不要总是相信维基百科 :) - Петър Петров

为什么有人想要使用余数函数而不是模运算符？为什么要设计“%”余数函数？ - Aaron Franke

这是早期CPU遗留下来的传统，当时它们有除法硬件可以快速产生商和余数 - 针对负被除数，这就是该硬件的功能。语言只是反映了硬件。大多数时候，程序员都使用正被除数，并忽略了这个怪癖。速度至关重要。 - ToolmakerSteve

Answer 3

仅使用一次 % 的单行实现：

int mod(int k, int n) {  return ((k %= n) < 0) ? k+n : k;  }

- Evgeni Sergeev

---

这个正确吗？因为我没有看到任何人接受它，也没有任何评论。例如，mod(-10,6)将返回6。这是正确的吗？它不应该返回4吗？ - John Demetriou

你的数字都是错误的：（A）应该返回2，（B）它确实返回2；请尝试运行代码。项目（A）：要手动找出mod(-10, 6)，你可以反复加上或减去6直到答案在区间 [0, 6) 内。这个符号表示“左闭右开”。在我们的例子中，我们加了两次6，得到2。这段代码非常简单，很容易看出它是正确的：首先，它做了与上面相同的加法/减法操作，只是从负数的一侧接近时会少一个 n 。在这种情况下，我们进行修正。就是这样，有注释 :) - Evgeni Sergeev

顺便提一下，使用单个“％”的原因可能是一个好主意。请参阅文章《编写更快的托管代码：了解成本》中的表格“托管代码中的成本”。使用“％”与表格中列出的“int div”类似：比加减法昂贵约36倍，比乘法昂贵约13倍。当然，除非这是您的代码核心，否则没有什么大不了的。 - Evgeni Sergeev

一个%操作是否比测试和跳转更昂贵，特别是如果它不能轻易地被预测？ - Medinoc

Answer 4

比较前两个答案

(x%m + m)%m;

和

int r = x%m;
return r<0 ? r+m : r;

实际上没有人提到第一个方法可能会抛出OverflowException，而第二个方法不会。更糟糕的是，使用默认的未经检查的上下文，第一个答案可能会返回错误的结果（例如，看看mod(int.MaxValue - 1, int.MaxValue)）。因此，第二个答案不仅似乎更快，而且更正确。

- lilo0

Answer 5

ShreevatsaR的答案并不适用于所有情况，即使您添加了“if(m<0) m=-m;”，如果考虑到负被除数/除数。

例如，-12模-10将为8，而它应该是-2。

以下实现将适用于正数和负数被除数/除数，并符合其他实现（即Java、Python、Ruby、Scala、Scheme、Javascript和Google的计算器）：

internal static class IntExtensions
{
    internal static int Mod(this int a, int n)
    {
        if (n == 0)
            throw new ArgumentOutOfRangeException("n", "(a mod 0) is undefined.");

        //puts a in the [-n+1, n-1] range using the remainder operator
        int remainder = a%n;

        //if the remainder is less than zero, add n to put it in the [0, n-1] range if n is positive
        //if the remainder is greater than zero, add n to put it in the [n-1, 0] range if n is negative
        if ((n > 0 && remainder < 0) ||
            (n < 0 && remainder > 0))
            return remainder + n;
        return remainder;
    }
}

---

使用xUnit的测试套件:

    [Theory]
    [PropertyData("GetTestData")]
    public void Mod_ReturnsCorrectModulo(int dividend, int divisor, int expectedMod)
    {
        Assert.Equal(expectedMod, dividend.Mod(divisor));
    }

    [Fact]
    public void Mod_ThrowsException_IfDivisorIsZero()
    {
        Assert.Throws<ArgumentOutOfRangeException>(() => 1.Mod(0));
    }

    public static IEnumerable<object[]> GetTestData
    {
        get
        {
            yield return new object[] {1, 1, 0};
            yield return new object[] {0, 1, 0};
            yield return new object[] {2, 10, 2};
            yield return new object[] {12, 10, 2};
            yield return new object[] {22, 10, 2};
            yield return new object[] {-2, 10, 8};
            yield return new object[] {-12, 10, 8};
            yield return new object[] {-22, 10, 8};
            yield return new object[] { 2, -10, -8 };
            yield return new object[] { 12, -10, -8 };
            yield return new object[] { 22, -10, -8 };
            yield return new object[] { -2, -10, -2 };
            yield return new object[] { -12, -10, -2 };
            yield return new object[] { -22, -10, -2 };
        }
    }

- dcastro

---

首先，mod函数通常使用正模数进行调用（请注意原始问题中正在回答的变量arrayLength，它可能永远不会是负数），因此该函数实际上不需要为负模数而工作。（这就是为什么我在我的答案评论中提到了负模数的处理方式，而不是在答案本身中提到。）（续...） - ShreevatsaR

其次，对于负数取模应采用何种约定是有争议的。参见维基百科。“通常，在数论中，总是选择正余数”，我也是这样学习的（Burton的初等数论）。Knuth也这样定义它（具体来说，r = a - b floor(a/b) 总是正的）。即使在计算机系统中，Pascal和Maple也将其定义为始终为正数。 - ShreevatsaR

@ShreevatsaR 我知道欧几里得定义规定结果总是正数，但我认为大多数现代模数实现将返回负除数“n”的[n+1,0]范围内的值，这意味着-12 mod -10 = -2。我查看了Google计算器、Python、Ruby和Scala，它们都遵循这个约定。 - dcastro

再次强调，这篇文章仍然是一篇不错的阅读材料。“始终为正”的定义（我的回答）与ALGOL、Dart、Maple、Pascal、Z3等语言一致。“除数符号”的定义（此回答）与APL、COBOL、J、Lua、Mathematica、MS Excel、Perl、Python、R、Ruby、Tcl等语言一致。两者都与“被除数符号”不一致，例如AWK、bash、bc、C99、C++11、C#、D、Eiffel、Erlang、Go、Java、OCaml、PHP、Rust、Scala、Swift、VB、x86汇编代码等。我真的看不出你如何能声称一个约定是“正确的”，其他约定则是“错误的”。 - ShreevatsaR

顺便提一下，这个答案目前声称与“Java、Python、Ruby、Scala、Scheme、Javascript和Google的计算器”一致，但实际上它与Java、Scala和Javascript不一致——尝试-12 mod 10，它们都会给出-2，而这个答案（以及Python、Ruby和Google的计算器）则给出8。要同时与Python和Java/Javascript一致是不可能的，因为它们彼此不一致。与此同时，Sage有一个mod函数，它总是返回一个正数结果：mod(-12, -10) == mod(-12, 10) == 8。 - ShreevatsaR

Answer 6

我喜欢Peter N Lewis在这个帖子中提出的技巧：“如果n有一个有限的范围，那么你可以通过添加一个已知常数倍数的[除数]来得到你想要的结果，该倍数大于最小值的绝对值。”

因此，如果我有一个以度为单位的值d，我想要进行取模运算

d % 180f

如果d为负数，我希望避免出现问题，那么我只需执行以下操作：

(d + 720f) % 180f

这里假设虽然 d 可能是负数，但已知它不会比 -720 更小。

- RenniePet

---

-1：不够通用，（而且很容易提供更通用的解决方案）。 - Evgeni Sergeev

这实际上非常有帮助。当你有一个有意义的范围时，这可以简化计算。在我的情况下，https://math.stackexchange.com/questions/2279751/how-to-simplify-2-modular-operators。 - M.kazem Akhgary

没错，我只是用它来计算星期几（已知范围为-6到+6），这样就不用写两个“％”了。 - NetMage

@EvgeniSergeev 对我来说是+0：没有回答OP的问题，但在更具体的上下文中可能会有帮助（但仍然在问题的上下文中）。 - Erdal G.

Answer 7

你期望的行为与c#中%运算符的文档行为相反，可能是因为你期望它以其他你更熟悉的语言中它的工作方式来工作。 c#的文档说明(其中强调部分是我的):

对于整数类型的操作数，a % b的结果是由a - (a / b) * b产生的值。 非零余数的符号与左操作数相同 所需的值可以通过一个额外的步骤计算得出。

int GetArrayIndex(int i, int arrayLength){
    int mod = i % arrayLength;
    return (mod>=0) : mod ? mod + arrayLength;
}

- Andrew

---

这个问题的答案有什么新的补充吗？ - ToolmakerSteve

@ToolmakerSteve，首先它实际上解决了官方语言规范的问题，这是关于%如何工作的误解的根源，其他答案都没有做到这一点。 - Andrew

Answer 8

只需将模数（arrayLength）添加到%的负结果中，就可以解决问题。

- starblue

Answer 9

增加理解。

根据欧几里得定义，模运算结果必须始终为正数。

例如：

 int n = 5;
 int x = -3;

 int mod(int n, int x)
 {
     return ((n%x)+x)%x;
 }

输出：

 -1

- Abin

---

我感到困惑...你说结果应该始终为正数，但是却将输出列为“-1”？ - Jeff B

@JeffBridgman 我是基于欧几里得定义提出的。对于余数，有两种可能的选择，一种是负数，另一种是正数，商也有两种可能的选择。通常，在数论中，“选择正余数”，但编程语言的选择取决于语言和a和/或n的符号。[5]标准Pascal和Algol68即使除数为负数也会给出正余数（或0），而一些编程语言（如C90）在n或a为负数时则由实现来决定。 - Abin

澄清：虽然有用，但这不是一个“答案”；它是对另一个答案限制的评论。这是一个建议，不要使用某些答案；查看其他答案以查看确实有效的公式。【吹毛求疵】：同样来自您的链接：“在数学中，模运算的结果是一个等价类，可以选择类的任何成员作为代表”。因此，说“模结果必须为正数”有点过分了。尽管该链接早期的语言如此。 - ToolmakerSteve

Answer 10

针对更注重性能的开发人员

uint wrap(int k, int n) ((uint)k)%n

一个小的性能比较。

Modulo: 00:00:07.2661827 ((n%x)+x)%x)
Cast:   00:00:03.2202334 ((uint)k)%n
If:     00:00:13.5378989 ((k %= n) < 0) ? k+n : k

关于将变量转换为uint类型的性能成本，请参考这里。

- Markus Cozowicz

---

我认为-3 % 10应该是-3或7。由于需要一个非负结果，因此答案应该是7。你的实现返回3。你应该将两个参数更改为uint并删除转换。 - I liked the old Stack Overflow

如果n是2的幂，无符号算术才等价。此时，您可以简单地使用逻辑与((uint)k & (n - 1))，如果编译器没有为您执行此操作（编译器通常足够聪明以找出这一点）。 - j_schultz

总结以上评论：对于负数k，这个答案是错误的。它没有计算模数。不要使用这个答案。（我很抱歉直言不讳，但点赞令人担忧。这表明有些人采用了一个会给出错误答案的实现。） - ToolmakerSteve