负数的Mod正在融化我的大脑

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)

这样的

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

我以前做过这个,但由于某种原因,它今天融化了我的大脑:(

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的值.

Answer 2

请注意,C#和C++的%运算符实际上不是模数,它是余数.在您的情况下,您想要的模数公式为:

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

您必须在C#(或C++)中重新编码,但这是您获得模数而不是余数的方式.

Answer 3

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

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

Answer 4

比较两个主要答案

(x%m + m)%m;

和

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

实际上没有人提到第一个可能会抛出OverflowException而第二个不会的事实。更糟糕的是，在默认的未经检查的上下文中，第一个答案可能会返回错误的答案（参见mod(int.MaxValue - 1, int.MaxValue)示例）。所以第二个答案不仅看起来更快，而且更正确。

Answer 5

增加一些了解.

根据欧几里德的定义,mod结果必须始终为正.

例如:

 int n = 5;
 int x = -3;

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

输出:

 -1

Answer 6

我喜欢 Peter N Lewis 在这个线程中提出的技巧：“如果 n 的范围有限，那么您只需添加一个已知的[除数]常量倍数即可得到您想要的结果，该倍数大于除数的绝对值最低限度。”

所以如果我有一个以度为单位的值d并且我想取

d % 180f

如果d为负数，我想避免出现问题，那么我只需这样做：

(d + 720f) % 180f

这假设虽然d可能为负数，但已知它永远不会比 -720 更负。

Answer 7

ShreevatsaR的答案不适用于所有情况,即使您添加"if(m <0)m = -m;",如果您考虑负红利/除数.

例如,-12 mod -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 };
        }
    }

Answer 8

只需将模数（arrayLength）添加到 % 的负结果中就可以了。