Mod der negativen Zahl schmilzt mein Gehirn

187

Ich versuche, eine Ganzzahl zu modifizieren, um eine Array-Position zu erhalten, damit sie sich um eine Schleife dreht. Das i % arrayLengthfunktioniert gut für positive Zahlen, aber für negative Zahlen geht alles schief.

 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

Also brauche ich eine Implementierung von

int GetArrayIndex(int i, int arrayLength)

so dass

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

Ich habe das schon einmal gemacht, aber aus irgendeinem Grund schmilzt es heute mein Gehirn :(

Oberst Panik
quelle
Siehe die Diskussion über den mathematischen Modul auf math.stackexchange.com/questions/519845/…
PPC
blogs.msdn.microsoft.com/ericlippert/2011/12/05/… ist ein großartiger Artikel
Samra

Antworten:

279

Ich benutze immer meine eigene modFunktion, definiert als

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

Wenn Sie sich die Mühe machen, zwei Aufrufe der Moduloperation zu haben, können Sie diese natürlich als schreiben

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

oder Varianten davon.

Der Grund dafür ist, dass "x% m" immer im Bereich [-m + 1, m-1] liegt. Wenn es also überhaupt negativ ist, wird es durch Hinzufügen von m in den positiven Bereich gebracht, ohne seinen Wert modulo m zu ändern.

ShreevatsaR
quelle
7
Hinweis: Zur vollständigen Vollständigkeit der Zahlentheorie möchten Sie möglicherweise oben eine Zeile mit der Aufschrift "if (m <0) m = -m;" einfügen. obwohl es in diesem Fall keine Rolle spielt, da "arrayLength" vermutlich immer positiv ist.
ShreevatsaR
4
Wenn Sie den Wert von m überprüfen möchten, sollten Sie auch Null ausschließen.
Billpg
6
@RuudLenders: Nein. Wenn x = -5 und m = 2, dann r = x%mist -1, danach r+mist 1. Die while-Schleife wird nicht benötigt. Der Punkt ist, dass (wie ich in der Antwort geschrieben habe) x%mimmer streng größer ist als -m, also müssen Sie mhöchstens einmal hinzufügen , um es positiv zu machen.
ShreevatsaR
4
@dcastro: Ich möchte, dass -12 mod -10 8 ist. Dies ist die häufigste Konvention in der Mathematik. Wenn Sie einen Vertreter rfür aModulo auswählen b, ist dies so, dass 0 ≤ r <| b |.
ShreevatsaR
8
+1. Es ist mir egal, was eine einzelne Sprache für einen negativen Modul tut - der 'kleinste nicht negative Rest' weist eine mathematische Regelmäßigkeit auf und beseitigt jegliche Mehrdeutigkeit.
Brett Hale
78

Bitte beachten Sie, dass der% -Operator von C # und C ++ eigentlich KEIN Modulo ist, sondern der Rest. Die Formel für Modulo, die Sie in Ihrem Fall möchten, lautet:

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

Sie müssen dies in C # (oder C ++) neu codieren, aber auf diese Weise erhalten Sie Modulo und keinen Rest.

Петър Петров
quelle
21
"Bitte beachten Sie, dass der% -Operator von C ++ eigentlich KEIN Modulo ist, sondern der Rest." Danke, es macht jetzt Sinn, fragen Sie sich immer, warum es mit negativen Zahlen nie richtig funktioniert hat.
leetNightshade
2
"Bitte beachten Sie, dass der% -Operator von C ++ eigentlich KEIN Modulo ist, sondern der Rest." Ich denke nicht, dass dies korrekt ist, und ich verstehe nicht, warum sich ein Modulo vom Rest unterscheidet. Das steht auch auf der Wikipedia-Seite Modulo Operation. Es ist nur so, dass Programmiersprachen negative Zahlen unterschiedlich behandeln. Der Modulo-Operator in C # zählt offensichtlich Reste "von" Null (-9% 4 = -1, weil 4 * -2 -8 mit einer Differenz von -1 ist), während eine andere Definition -9% 4 als +3 betrachten würde, weil -4 * 3 ist -12, Rest +3 (wie in der Google-Suchfunktion, nicht sicher, welche Back-End-Sprache dort vorhanden ist).
Tyress
17
Tyress, es gibt einen Unterschied zwischen Modul und Rest. Zum Beispiel: -21 mod 4 is 3 because -21 + 4 x 6 is 3. Aber -21 divided by 4 gives -5mit a remainder of -1. Bei positiven Werten gibt es keinen Unterschied. Bitte informieren Sie sich über diese Unterschiede. Und vertraue Wikipedia nicht die ganze Zeit :)
6етър Петров
2
Warum sollte jemand die Restfunktion anstelle eines Modulos verwenden wollen? Warum haben sie den %Rest gemacht?
Aaron Franke
3
@AaronFranke - es ist ein Erbe aus früheren CPUs, die Divisionshardware hatten, um schnell einen Quotienten und einen Rest zu erzeugen - und genau das hat diese Hardware mit einer negativen Dividende erzielt. Die Sprache spiegelte einfach die Hardware wider. Die meisten Programmierer arbeiteten mit positiven Dividenden und ignorierten diese Eigenart. Geschwindigkeit war von größter Bedeutung.
ToolmakerSteve
15

Einzeilige Implementierung mit %nur einmal:

int mod(int k, int n) {  return ((k %= n) < 0) ? k+n : k;  }
Evgeni Sergeev
quelle
1
ist das richtig? da ich es weder als von irgendjemandem akzeptiert sehe, noch irgendwelche Kommentare dazu. Beispielsweise. mod (-10,6) gibt 6 zurück. Ist das richtig? sollte es nicht 4 zurückgeben?
John Demetriou
3
@ JohnDemetriou Ihre Zahlen sind beide falsch: (A) es sollte 2 zurückgeben und (B) es wird 2 zurückgeben; Versuchen Sie, den Code auszuführen. Punkt (A): Um mod(-10, 6)von Hand zu finden , addieren oder subtrahieren Sie 6 wiederholt, bis die Antwort im Bereich liegt [0, 6). Diese Notation bedeutet "links inklusive und rechts exklusiv". In unserem Fall addieren wir 6 zweimal, was 2 ergibt. Der Code ist recht einfach und es ist leicht zu erkennen, dass er richtig ist: Erstens entspricht er dem Addieren / Subtrahieren nwie oben, außer dass er einen nKurzschluss stoppt , wenn er sich nähert die negative Seite. In diesem Fall beheben wir es. Dort: Kommentare :)
Evgeni Sergeev
1
Übrigens, hier ist ein Grund, warum die Verwendung einer Single %eine gute Idee sein könnte. Weitere Informationen finden Sie in der Tabelle Welche Kosten in verwaltetem Code im Artikel Schreiben von schneller verwaltetem Code: Wissen, was Dinge kosten . Die Verwendung %ist ähnlich teuer wie int divin der Tabelle aufgeführt: etwa 36-mal teurer als das Addieren oder Subtrahieren und etwa 13-mal teurer als das Multiplizieren. Natürlich keine große Sache, es sei denn, dies ist der Kern dessen, was Ihr Code tut.
Evgeni Sergeev
2
Aber ist eine Single %teurer als ein Test und ein Sprung, besonders wenn es nicht leicht vorherzusagen ist?
Medinoc
7

Die Antwort von ShreevatsaR funktioniert nicht in allen Fällen, selbst wenn Sie "if (m <0) m = -m;" hinzufügen, wenn Sie negative Dividenden / Teiler berücksichtigen.

Zum Beispiel ist -12 mod -10 8 und sollte -2 sein.

Die folgende Implementierung funktioniert sowohl für positive als auch für negative Dividenden / Teiler und entspricht anderen Implementierungen (nämlich Java, Python, Ruby, Scala, Schema, Javascript und Googles Rechner):

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

Testsuite mit 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
quelle
Erstens wird eine modFunktion normalerweise mit positivem Modul aufgerufen (beachten Sie die Variable arrayLengthin der ursprünglichen Frage, die hier beantwortet wird, die vermutlich nie negativ ist), sodass die Funktion nicht wirklich für den negativen Modul ausgeführt werden muss. (Deshalb erwähne ich die Behandlung des negativen Moduls in einem Kommentar zu meiner Antwort, nicht in der Antwort selbst.) (Fortsetzung ...)
ShreevatsaR
3
(... Fortsetzung) Zweitens ist es eine Frage der Konvention, was für einen negativen Modul zu tun ist. Siehe zB Wikipedia . "Normalerweise wird in der Zahlentheorie immer der positive Rest gewählt", und so habe ich es auch gelernt (in Burtons elementarer Zahlentheorie ). Knuth definiert es auch so (insbesondere r = a - b floor(a/b)ist es immer positiv). Selbst unter Computersystemen definieren Pascal und Maple dies als immer positiv.
ShreevatsaR
@ShreevatsaR Ich weiß, dass die euklidische Definition besagt, dass das Ergebnis immer positiv sein wird - aber ich habe den Eindruck, dass die meisten modernen Mod-Implementierungen einen Wert im Bereich [n + 1, 0] für einen negativen Divisor "n" zurückgeben. was bedeutet, dass -12 mod -10 = -2. Ich habe mir Google Calculator , Python , Ruby und Scala angesehen und alle folgen dieser Konvention.
Dcastro
Außerdem zur Liste hinzufügen: Schema und Javascript
dcastro
1
Auch dies ist immer noch eine gute Lektüre. Die "immer positive" Definition (meine Antwort) stimmt mit ALGOL, Dart, Maple, Pascal, Z3 usw. überein. Das "Zeichen des Teilers" (diese Antwort) stimmt überein mit: APL, COBOL, J, Lua, Mathematica, MS Excel, Perl, Python, R, Ruby, Tcl usw. Beide stimmen nicht mit dem "Zeichen der Dividende" überein, wie in: AWK, Bash, BC, C99, C ++ 11, C #, D, Eiffel, Erlang, Go, Java , OCaml, PHP, Rust, Scala, Swift, VB, x86-Assembly usw. Ich sehe wirklich nicht, wie Sie behaupten können, eine Konvention sei "richtig" und andere "falsch".
ShreevatsaR
6

Verständnis hinzufügen.

Nach euklidischer Definition muss das Mod-Ergebnis immer positiv sein.

Ex:

 int n = 5;
 int x = -3;

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

Ausgabe:

 -1
Ein Eimer
quelle
15
Ich bin verwirrt ... Sie sagen, dass das Ergebnis immer positiv sein sollte, aber dann die Ausgabe auflisten als -1?
Jeff B
@ JeffBridgman Ich habe das basierend auf der euklidischen Definition angegeben. `Für den Rest gibt es zwei Möglichkeiten, eine negative und eine positive, und für den Quotienten gibt es zwei Möglichkeiten. Normalerweise in der Zahlentheorie, the positive remainder is always chosenaber Programmiersprachen wählen in Abhängigkeit von der Sprache und den Vorzeichen von a und / oder n. [5] Standard Pascal und Algol68 geben selbst für negative Teiler einen positiven Rest (oder 0), und einige Programmiersprachen wie C90 überlassen es der Implementierung, wenn entweder n oder a negativ ist. "
Abin
4

Addieren Sie einfach Ihren Modul (arrayLength) zum negativen Ergebnis von% und Sie werden in Ordnung sein.

Sternenblau
quelle
4

Für leistungsorientiertere Entwickler

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

Ein kleiner Leistungsvergleich

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

Informationen zu den Leistungskosten von Cast to Uint finden Sie hier

Markus Cozowicz
quelle
3
Denkt, dass -3 % 10entweder -3 oder 7 sein sollte. Da ein nicht negatives Ergebnis gewünscht wird, wäre 7 die Antwort. Ihre Implementierung gibt 3 zurück. Sie sollten beide Parameter ändern uintund die Umwandlung entfernen.
Ich mochte den alten Stapelüberlauf
5
Arithmetik ohne Vorzeichen ist nur dann äquivalent, wenn nes sich um eine Zweierpotenz handelt. In diesem Fall können Sie einfach ein logisches und ( (uint)k & (n - 1)) verwenden, wenn der Compiler dies nicht bereits für Sie erledigt (Compiler sind oft klug genug, um dies herauszufinden).
j_schultz
4

Vergleich zweier vorherrschender Antworten

(x%m + m)%m;

und

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

Niemand erwähnte tatsächlich die Tatsache, dass der erste eine OverflowExceptionWeile werfen kann, der zweite nicht. Schlimmer noch, wenn der Standardkontext nicht aktiviert ist, gibt die erste Antwort möglicherweise die falsche Antwort zurück (siehe mod(int.MaxValue - 1, int.MaxValue)zum Beispiel). Die zweite Antwort scheint also nicht nur schneller, sondern auch korrekter zu sein.

lilo0
quelle
2

Ich mag den Trick, den Peter N Lewis in diesem Thread vorgestellt hat : "Wenn n einen begrenzten Bereich hat, können Sie das gewünschte Ergebnis erzielen, indem Sie einfach ein bekanntes konstantes Vielfaches von [dem Divisor] hinzufügen, das größer ist als der absolute Wert von Minimum."

Wenn ich also einen Wert d habe , der in Grad angegeben ist und den ich nehmen möchte

d % 180f

und ich möchte die Probleme vermeiden, wenn d negativ ist, dann mache ich stattdessen einfach Folgendes:

(d + 720f) % 180f

Dies setzt voraus, dass d zwar negativ sein kann, es jedoch bekannt ist, dass es niemals negativer als -720 sein wird.

RenniePet
quelle
2
-1: nicht allgemein genug (und es ist sehr einfach, eine allgemeinere Lösung zu geben).
Evgeni Sergeev
4
Das ist eigentlich sehr hilfreich. Wenn Sie einen sinnvollen Bereich haben, kann dies die Berechnung vereinfachen. in meinem Fall math.stackexchange.com/questions/2279751/…
M.kazem Akhgary
Genau, dies wurde nur für die Berechnung von dayOfWeek verwendet (bekannter Bereich von -6 bis +6) und es wurden zwei gespart %.
NetMage
@ EvgeniSergeev +0 für mich: Beantwortet keine OP-Frage, kann aber in einem spezifischeren Kontext hilfreich sein (aber immer noch im Kontext der Frage)
Erdal G.
1

Sie erwarten ein Verhalten, das dem dokumentierten Verhalten des Operators% in c # widerspricht - möglicherweise, weil Sie erwarten, dass es so funktioniert, wie es in einer anderen Sprache funktioniert, an die Sie eher gewöhnt sind. Die Dokumentation zu c # besagt (Schwerpunkt Mine):

Für die Operanden ganzzahliger Typen ist das Ergebnis von a% b der Wert, der durch a - (a / b) * b erzeugt wird. Das Vorzeichen des Restes ungleich Null ist das gleiche wie das des linken Operanden

Der gewünschte Wert kann mit einem zusätzlichen Schritt berechnet werden:

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

Alle Antworten hier funktionieren hervorragend, wenn Ihr Divisor positiv ist, aber nicht ganz vollständig. Hier ist meine Implementierung, die immer in einem Bereich von zurückgibt [0, b), sodass das Vorzeichen der Ausgabe mit dem Vorzeichen des Divisors übereinstimmt und negative Divisoren als Endpunkt für den Ausgabebereich berücksichtigt werden.

PosMod(5, 3)return 2
PosMod(-5, 3)return 1
PosMod(5, -3)return -1
PosMod(-5, -3)return-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;
    }

(wo real_tkann ein beliebiger Nummerntyp sein)

Aaron Franke
quelle
0

Eine einzeilige Implementierung der Antwort von dcastro (die mit anderen Sprachen am kompatibelsten ist):

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

Wenn Sie die Verwendung des %Operators beibehalten möchten (Sie können native Operatoren in C # nicht überladen):

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

Anwendungsfall, beide Werke:

int r = (IntM)a % n;

// Or
int r = a % n(IntM);
Erdal G.
quelle