负数的Mod快把我的脑子都融化了

我试图mod一个整数，以获得一个数组的位置，以便它将循环。正在执行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

我以前也这么做过，但不知为何，今天我的脑子都要融化了:(

140382 次浏览
小开

只需将您的模量(arrayLength)添加到%的负结果，就可以了。

小开

我总是使用自己的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的模的值。

小开

请注意，c#和c++的%运算符实际上不是模数，而是余数。在你的例子中，求模的公式是:

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

你必须用c#(或c++)重新编码，但这是你得到模数而不是余数的方法。

小开

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

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

d % 180f

并且我想避免d为负时的问题，那么我只这样做:

(d + 720f) % 180f

这假设尽管d可能是负数，但已知它永远不会比-720更负。

小开

增加一些理解。

通过欧几里得的定义, mod结果必须始终为正。

例:

 int n = 5;
int x = -3;


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

输出:

 -1
小开

ShreevatsaR的答案并不适用于所有情况，即使你加上“如果(m<0) m=-m;”，如果你考虑负红利/除数。

例如，-12 mod -10将是8，它应该是-2。

以下实现将适用于正负的红利/除数，并符合其他实现(即Java, Python, Ruby, Scala, Scheme, Javascript和谷歌的计算器):

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

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

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

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

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的性能成本，请查看在这里

小开

比较前两个答案

(x%m + m)%m;

而且

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

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

小开

如果你的除数是正数，这里所有的答案都很有效，但它并不完全。下面是我的实现，它总是在[0, b)范围内返回，这样输出的符号与除数的符号相同，允许负除数作为输出范围的端点。

PosMod(5, 3)返回2
PosMod(-5, 3)返回1
PosMod(5, -3)返回-1
PosMod(-5, -3)返回-2

    /// <summary>
/// Performs a canonical Modulus operation, where the output is on the range [0, b).
/// </summary>
public static real_t PosMod(real_t a, real_t b)
{
real_t c = a % b;
if ((c < 0 && b > 0) || (c > 0 && b < 0))
{
c += b;
}
return c;
}

(其中real_t可以是任何数字类型)

小开

您期望的行为与c#中%操作符的记录行为相反——可能是因为您期望它以一种在您更习惯的另一种语言中工作的方式工作。c#上的文档状态(强调我的):

对于整数类型的操作数，a % b的结果是a - (a / b) * b. 非零余数的符号与左操作数的符号相同产生的值

你想要的值可以通过一个额外的步骤来计算:

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

dcastro的答案的单行实现(与其他语言最兼容):

int Mod(int a, int n)
{
return (((a %= n) < 0) && n > 0) || (a > 0 && n < 0) ? a + n : a;
}

如果你想保留%操作符的使用(你不能在c#中重载本机操作符):

public class IntM
{
private int _value;


private IntM(int value)
{
_value = value;
}


private static int Mod(int a, int n)
{
return (((a %= n) < 0) && n > 0) || (a > 0 && n < 0) ? a + n : a;
}


public static implicit operator int(IntM i) => i._value;
public static implicit operator IntM(int i) => new IntM(i);
public static int operator %(IntM a, int n) => Mod(a, n);
public static int operator %(int a, IntM n) => Mod(a, n);
}

用例，两者都适用:

int r = (IntM)a % n;


// Or
int r = a % n(IntM);
小开

下面是基于这个答案的正整数的一行代码:

用法:

(-7).Mod(3); // returns 2

实现:

static int Mod(this int a, int n) => (((a %= n) < 0) ? n : 0) + a;
小开

mod函数有很多实现，我认为列出所有实现是值得的——至少根据维基百科，我相信还有更多。

// Important to be able to use `MathF`.
using System;


public static class MathFUtils {
public static class Mod {
public static float Trunc(float a, float b) =>
a - b * ((int)(a / b));


public static float Round(float a, float b) =>
a - b * MathF.Round(a / b);


public static float Floor(float a, float b) =>
a - b * MathF.Floor(a / b);


public static float Ceil(float a, float b) =>
a - b * MathF.Ceiling(a / b);


public static float Euclidean(float a, float b) =>
a - MathF.Abs(b) * MathF.Floor(a / MathF.Abs(b));
}
}

根据维基百科(以及我的经验)坚持Euclidean。它在数学和概率性质方面是最有用的。如果你需要Trunc，那么我相信%可以做到这一点。

此外，对于那些可能对它们各自做什么以及如何做感到困惑的人，我强烈建议阅读维基百科的文章(即使很难)并查看每个表示的图像。

当然，这些不一定是性能最好的，但它们确实有效。如果你关心性能，我建议你找一个本地的c#之神，或者在他们经过我们的尘世时问他。

小开

ShreevatsaR的第二个答案是:

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

可以在新版本的c#中使用var模式和switch表达式作为一行程序来编写:

int mod(int x, int m) => (x % m) switch
{
< 0 and var r => r + m, var r => r
}

提交答案