So codieren Sie einen Modulo (%) -Operator in C / C ++ / Obj-C, der negative Zahlen verarbeitet

86

Einer meiner Lieblingshasse von C-abgeleiteten Sprachen (als Mathematiker) ist das

(-1) % 8 // comes out as -1, and not 7

fmodf(-1,8) // fails similarly

Was ist die beste Lösung?

C ++ ermöglicht die Möglichkeit des Überladens von Vorlagen und Operatoren, aber beide sind für mich trübes Wasser. Beispiele dankbar erhalten.

P i
quelle
1
Ich denke nicht, dass dies ein "Duplikat" von stackoverflow.com/questions/828092/… unter der offiziellen Definition ist. Es ist nicht wahr, dass die Antworten dieser Frage mit denen dieser Frage zusammengeführt werden können, da diese Frage nur nach dem Modul fragt, nicht auch nach der Teilung. Aber ich denke, diese Frage wird von dieser behandelt, also ist es nah. Meine Antwort ist schon da, FWIW.
Steve Jessop
Vielleicht sollte dieser Thread geteilt werden, da er zwei separate Fragen stellt. Der beste Weg, dies zu tun, besteht darin, die Teilungsfrage separat erneut zu stellen und sie dann auf diese Antwort zu richten. Ich werde es jemandem überlassen, der die Mechanismen dieser Website besser versteht.
P i
3
@ Pi wo %soll das Modulo sein ... es ist der Rest .
Oldrinb
1
Hier ist ein weiterer Thread, von dem dies ein "Duplikat" ist: stackoverflow.com/questions/1082917/… Nur als Referenz zu diesem %Problem.
leetNightshade
Wenn Sie nur Zweierpotenzen teilen, ist es möglicherweise eine bessere Idee, (-1) & 8 == 7
Henricus V.

Antworten:

74

Zunächst möchte ich darauf hinweisen, dass Sie sich nicht einmal darauf verlassen können, dass (-1) % 8 == -1. Das einzige, worauf Sie sich verlassen können, ist das (x / y) * y + ( x % y) == x. Ob der Rest jedoch negativ ist oder nicht, ist implementierungsdefiniert .

Warum nun hier Vorlagen verwenden? Eine Überlastung für Ints und Longs würde genügen.

int mod (int a, int b)
{
   int ret = a % b;
   if(ret < 0)
     ret+=b;
   return ret;
}

und jetzt kannst du es wie mod (-1,8) nennen und es scheint 7 zu sein.

Bearbeiten: Ich habe einen Fehler in meinem Code gefunden. Es wird nicht funktionieren, wenn b negativ ist. Also ich denke das ist besser:

int mod (int a, int b)
{
   if(b < 0) //you can check for b == 0 separately and do what you want
     return -mod(-a, -b);   
   int ret = a % b;
   if(ret < 0)
     ret+=b;
   return ret;
}

Referenz: C ++ 03 Absatz 5.6 Abschnitt 4:

Der Binär / Operator ergibt den Quotienten und der Binäroperator% ergibt den Rest aus der Division des ersten Ausdrucks durch den zweiten. Wenn der zweite Operand von / oder% Null ist, ist das Verhalten undefiniert. ansonsten ist (a / b) * b + a% b gleich a. Wenn beide Operanden nicht negativ sind, ist der Rest nicht negativ. Wenn nicht, ist das Vorzeichen des Restes implementierungsdefiniert .

Armen Tsirunyan
quelle
2
@Ohmu: Ja, das ist im C ++ Standard. <quote> Für integrale Operanden liefert der Operator / den algebraischen Quotienten, wobei jeder gebrochene Teil verworfen wird. Wenn der Quotient a / b in der Art des Ergebnisses darstellbar ist, ist (a / b) * b + a% b gleich a. </ quote>
Ben Voigt
5
-1. Es ist 11 Jahre her, seit diese Implementierung definiert wurde. ISO 9899: 1999 hat es definiert und leider die schlechte Definition gewählt.
R .. GitHub STOP HELPING ICE
3
@Armen: Sie haben die Fußnote <quote> bequem gelöscht ... Die Ganzzahldivision folgt den in der ISO Fortran-Norm ISO / IEC 1539: 1991 definierten Regeln, in denen der Quotient immer auf Null gerundet wird </ quote>. Der neue C ++ - Standard aktualisiert dieses Verhalten von "bevorzugt" auf obligatorisch, genau wie Fortran und C.
Ben Voigt
2
@Armen: Die alte Spezifikation ist defekt, aber die Zerbrochenheit unterscheidet sich von der Zeichenfrage, und es ist leicht zu übersehen, bis Sie sich den neuen Wortlaut ansehen. C ++ 03 hatte nicht "wenn der Quotient a / b in der Art des Ergebnisses darstellbar ist", was Probleme verursacht INT_MIN / -1(bei Zweierkomplementimplementierungen). Unter der alten Spezifikation muss -32768 % -1möglicherweise ausgewertet werden -65536(was auch nicht im Bereich des 16-Bit-Typs liegt, yuck!), Damit die Identität erhalten bleibt.
Ben Voigt
1
re "Ob der Rest jedoch negativ ist oder nicht, ist implementierungsdefiniert." C ++ 11 garantiert, dass die Ganzzahldivision in Richtung 0
gerundet wird.
12

Hier ist eine C-Funktion, die positive ODER negative Ganzzahl- ODER Bruchwerte für BEIDE OPERANDEN verarbeitet

#include <math.h>
float mod(float a, float N) {return a - N*floor(a/N);} //return in range [0, N)

Dies ist aus mathematischer Sicht sicherlich die eleganteste Lösung. Ich bin mir jedoch nicht sicher, ob es robust im Umgang mit ganzen Zahlen ist. Manchmal schleichen sich beim Konvertieren von int -> fp -> int Gleitkommafehler ein.

Ich verwende diesen Code für Nicht-Ints und eine separate Funktion für Int.

HINWEIS: muss N = 0 abfangen!

Testcode:

#include <math.h>
#include <stdio.h>

float mod(float a, float N)
{
    float ret = a - N * floor (a / N);

    printf("%f.1 mod %f.1 = %f.1 \n", a, N, ret);

    return ret;
}

int main (char* argc, char** argv)
{
    printf ("fmodf(-10.2, 2.0) = %f.1  == FAIL! \n\n", fmodf(-10.2, 2.0));

    float x;
    x = mod(10.2f, 2.0f);
    x = mod(10.2f, -2.0f);
    x = mod(-10.2f, 2.0f);
    x = mod(-10.2f, -2.0f);

    return 0;
}

(Hinweis: Sie können es direkt über CodePad kompilieren und ausführen: http://codepad.org/UOgEqAMA )

Ausgabe:

fmodf (-10,2, 2,0) = -0,20 == FAIL!

10,2 mod 2,0 = 0,2
10,2 mod -2,0 = -1,8
-10,2 mod 2,0 = 1,8
-10,2 mod -2,0 = -0,2

P i
quelle
Leider funktioniert dies nicht mit ganzen Zahlen. Sie müssten vor der Division in Gleitkomma konvertiert werden, damit Sie sie verwenden können floor(). Außerdem können Sie beim Konvertieren in Float an Präzision verlieren: Versuchen Sie (float)1000000001/3, Sie werden von den Ergebnissen überrascht sein!
cmaster
9

Ich habe gerade bemerkt, dass Bjarne Stroustrup %als Restoperator und nicht als Modulooperator bezeichnet.

Ich würde wetten, dass dies der formale Name in den ANSI C & C ++ - Spezifikationen ist und dass sich ein Missbrauch der Terminologie eingeschlichen hat. Weiß jemand dies für eine Tatsache?

Wenn dies jedoch der Fall ist, sind die Funktionen fmodf () von C (und wahrscheinlich auch andere) sehr irreführend. Sie sollten mit fremf () usw. bezeichnet werden

P i
quelle
1
Der C11-Standard (oder genauer gesagt der endgültige öffentliche Entwurf ) erwähnt "modulo" sechsmal, jedoch nur in Bezug auf die Darstellung verschiedener Typen. Nicht ein einziges Mal wird "modulo" in Bezug auf den Restoperator ( %) erwähnt.
Nisse Engström
7

Die einfachste allgemeine Funktion, um das positive Modulo zu finden, wäre folgende: Es würde sowohl für positive als auch für negative Werte von x funktionieren.

int modulo(int x,int N){
    return (x % N + N) %N;
}
Udayraj Deshmukh
quelle
6

Für ganze Zahlen ist dies einfach. Mach einfach

(((x < 0) ? ((x % N) + N) : x) % N)

wo ich annehme, Nist das positiv und darstellbar in der Art von x. Ihr Lieblings-Compiler sollte dies optimieren können, sodass es in Assembler nur zu einer Mod-Operation kommt.

Jens Gustedt
quelle
3
Funktioniert nicht: denn int x=-9001; unsigned int N=2000;es gibt 2295, nicht 999.
Hubert Kario
1
@ HubertKario Vielleicht nochmal nachsehen? Es gibt keine Möglichkeit, dass etwas Modulo 2000 2295 gibt, Sie müssen einen Fehler gemacht haben.
Sam Hocevar
2
@ SamHocevar: Ich denke, das Problem hier sind die seltsamen C-Integer-Promotion-Regeln. signierte Heraufstufung zu vorzeichenlos und Heraufstufen eines negativ vorzeichenbehafteten ganzzahligen Werts zu vorzeichenlos ruft undefiniertes Verhalten in C.
datenwolf
1
Ich glaube, eine viel einfachere (und effizientere) Form wäre : (x < 0) ? (x % N + N) : (x % N).
Chris Nolet
3

Die beste Lösung für einen Mathematiker ist die Verwendung von Python.

Das Überladen von C ++ - Operatoren hat wenig damit zu tun. Sie können Operatoren für integrierte Typen nicht überladen. Was Sie wollen, ist einfach eine Funktion. Natürlich können Sie C ++ - Vorlagen verwenden, um diese Funktion für alle relevanten Typen mit nur 1 Code zu implementieren.

Die Standard-C-Bibliothek bietet fmod, wenn ich mich richtig an den Namen erinnere, Gleitkommatypen.

Für ganze Zahlen können Sie eine C ++ - Funktionsvorlage definieren, die immer einen nicht negativen Rest (entsprechend der euklidischen Division) als ... zurückgibt.

#include <stdlib.h>  // abs

template< class Integer >
auto mod( Integer a, Integer b )
    -> Integer
{
    Integer const r = a%b;
    return (r < 0? r + abs( b ) : r);
}

... und schreibe einfach mod(a, b)statt a%b.

Hier muss der Typ Integerein vorzeichenbehafteter Integer-Typ sein.

Wenn Sie das übliche mathematische Verhalten wünschen, bei dem das Vorzeichen des Restes mit dem Vorzeichen des Divisors übereinstimmt, können Sie z

template< class Integer >
auto floor_div( Integer const a, Integer const b )
    -> Integer
{
    bool const a_is_negative = (a < 0);
    bool const b_is_negative = (b < 0);
    bool const change_sign  = (a_is_negative != b_is_negative);

    Integer const abs_b         = abs( b );
    Integer const abs_a_plus    = abs( a ) + (change_sign? abs_b - 1 : 0);

    Integer const quot = abs_a_plus / abs_b;
    return (change_sign? -quot : quot);
}

template< class Integer >
auto floor_mod( Integer const a, Integer const b )
    -> Integer
{ return a - b*floor_div( a, b ); }

… Mit der gleichen Einschränkung Integer, dass es sich um einen signierten Typ handelt.


¹ Weil Pythons ganzzahlige Division in Richtung negativer Unendlichkeit rundet.

Prost und hth. - Alf
quelle
Ihr Code scheint den gleichen Fehler zu haben wie meiner vor meiner Bearbeitung. Was ist, wenn b negativ ist? :)
Armen Tsirunyan
1
@Armen: danke! aber ich bin zu faul, um genau das zu bearbeiten ... :-)
Prost und hth. - Alf
@ArmenTsirunyan: Das rErgebnis muss a= r + b*(a/b)true machen. Unabhängig davon, wie die Ganzzahldivision implementiert ist, b*somethingist das ein Vielfaches von b. Dies rergibt ein gültiges Modulo-Ergebnis, auch wenn es negativ ist. Sie können abs ( b) hinzufügen und es wird immer noch ein gültiges Modulo-Ergebnis sein.
Prost und hth. - Alf
2
@downvoters: Diese Antwort ist immer noch richtig, während die ausgewählte "Lösung" aufgrund neuer Garantien in C ++ 11 jetzt falsche Kommentare enthält. Es ist verdammt ironisch, eine Antwort herunterzustimmen, die immer noch richtig ist. Ohne Angabe von Gründen muss man davon ausgehen, dass mindestens 2 assoziative Personen mit fast absolutem Grad an Unwissenheit den Kommentar dieser Frage lesen und knie-ruck-assoziativ herabgestimmt haben. Bitte erläutern Sie Ihre Abstimmungen.
Prost und hth. - Alf
1
Das mathematisch gewünschte Ergebnis ist, dass der Rest Null ist oder das gleiche Vorzeichen wie der Divisor (Nenner) hat. Wenn der Divisor negativ ist, sollte der Rest Null oder negativ sein. Die C / C ++ - Implementierung führt dazu, dass der Rest Null ist oder das gleiche Vorzeichen wie die Dividende (Zähler) hat.
rcgldr
2

Oh, ich hasse% Design auch dafür ....

Sie können die Dividende folgendermaßen in eine nicht unterzeichnete Dividende umwandeln:

unsigned int offset = (-INT_MIN) - (-INT_MIN)%divider

result = (offset + dividend) % divider

Wenn der Versatz dem (-INT_MIN) Vielfachen des Moduls am nächsten kommt, ändert das Addieren und Subtrahieren des Moduls das Modulo nicht. Beachten Sie, dass der Typ ohne Vorzeichen und das Ergebnis eine Ganzzahl sind. Leider können die Werte INT_MIN ... (- offset-1) nicht korrekt konvertiert werden, da sie einen arifmetischen Überlauf verursachen. Diese Methode bietet jedoch nur eine zusätzliche Arithmetik pro Operation (und keine Bedingungen), wenn mit einem konstanten Teiler gearbeitet wird, sodass sie in DSP-ähnlichen Anwendungen verwendet werden kann.

Es gibt einen Sonderfall, in dem der Teiler 2 N (ganzzahlige Zweierpotenz) ist, für den Modulo mit einfacher arithmetischer und bitweiser Logik berechnet werden kann

dividend&(divider-1)

beispielsweise

x mod 2 = x & 1
x mod 4 = x & 3
x mod 8 = x & 7
x mod 16 = x & 15

Häufiger und weniger schwierig ist es, Modulo mit dieser Funktion zu erhalten (funktioniert nur mit positivem Teiler):

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

Dies ist nur das richtige Ergebnis, wenn es negativ ist.

Sie können auch tricksen:

(p% q + q)% q

Es ist sehr kurz, aber verwenden Sie zwei% -s, die normalerweise langsam sind.

Vovanium
quelle
2

Ich glaube, eine andere Lösung für dieses Problem wäre die Verwendung von Variablen vom Typ long anstelle von int.

Ich habe gerade an einem Code gearbeitet, bei dem der% -Operator einen negativen Wert zurückgegeben hat, der einige Probleme verursacht hat (zum Generieren einheitlicher Zufallsvariablen für [0,1] möchten Sie nicht wirklich negative Zahlen :)), aber nach dem Umschalten der Variablen auf Typ lang, alles lief reibungslos und die Ergebnisse stimmten mit denen überein, die ich beim Ausführen des gleichen Codes in Python erhielt (wichtig für mich, da ich in der Lage sein wollte, die gleichen "Zufallszahlen" auf mehreren Plattformen zu generieren.

David
quelle
2

Hier ist eine neue Antwort auf eine alte Frage, die auf diesem Microsoft Research-Dokument und den darin enthaltenen Referenzen basiert .

Man beachte , dass von C11 und C ++ 11 ab, die Semantik divworden Trunkierung gegen Null (siehe [expr.mul]/4). Darüber hinaus garantiert C ++ 11 für Ddividiert durch dFolgendes den Quotienten qTund den RestrT

auto const qT = D / d;
auto const rT = D % d;
assert(D == d * qT + rT);
assert(abs(rT) < abs(d));
assert(signum(rT) == signum(D));

Dabei signumwerden -1, 0, +1 zugeordnet, je nachdem, ob das Argument <, ==,> als 0 ist ( Quellcode finden Sie in diesen Fragen und Antworten).

Bei abgeschnittener Division ist das Vorzeichen des Restes gleich dem Vorzeichen der DividendeD , d -1 % 8 == -1. H. C ++ 11 bietet auch eine std::divFunktion, die eine Struktur mit Elementen quotund rementsprechend der abgeschnittenen Unterteilung zurückgibt .

Es gibt noch andere Definitionen möglich, zB sogenannte Boden Teilung kann in Bezug auf die builtin abgeschnitten Teilung definiert werden

auto const I = signum(rT) == -signum(d) ? 1 : 0;
auto const qF = qT - I;
auto const rF = rT + I * d;
assert(D == d * qF + rF);
assert(abs(rF) < abs(d));
assert(signum(rF) == signum(d));

Bei einer Bodenteilung entspricht das Vorzeichen des Restes dem Vorzeichen des Teilersd . In Sprachen wie Haskell und Oberon gibt es eingebaute Operatoren für die Teilung von Fußböden. In C ++ müssen Sie eine Funktion mit den obigen Definitionen schreiben.

Ein weiterer Weg ist die euklidische Teilung , die auch als eingebaute abgeschnittene Teilung definiert werden kann

auto const I = rT >= 0 ? 0 : (d > 0 ? 1 : -1);
auto const qE = qT - I;
auto const rE = rT + I * d;
assert(D == d * qE + rE);
assert(abs(rE) < abs(d));
assert(signum(rE) != -1);

Bei der euklidischen Teilung ist das Vorzeichen des Restes immer positiv .

TemplateRex
quelle
2

Für eine Lösung, die keine Zweige und nur 1 Mod verwendet, können Sie Folgendes tun

// Works for other sizes too,
// assuming you change 63 to the appropriate value
int64_t mod(int64_t x, int64_t div) {
  return (x % div) + (((x >> 63) ^ (div >> 63)) & div);
}
Kyle Butt
quelle
1
/ * Warnung: Der Makro-Mod wertet die Nebenwirkungen seiner Argumente mehrmals aus. * /
# mod (r, m) definieren (((r)% (m)) + ((r) <0)? (m): 0)

... oder gewöhnen Sie sich einfach daran, einen Vertreter für die Äquivalenzklasse zu finden.

Eric Towers
quelle
2
"Gewöhne dich daran, einen Vertreter für die Äquivalenzklasse zu bekommen"?! Das ist Unsinn. Wenn Sie möchten, können Sie einfach den ursprünglichen "Vertreter" verwenden r. Der %Operator hat nichts mit Äquivalenzklassen zu tun. Es ist der Restoperator und der Rest ist algebraisch gut definiert, um nicht negativ und kleiner als der Divisor zu sein. Leider hat C es falsch definiert. Trotzdem +1 für eine der besten Antworten.
R .. GitHub STOP HELPING ICE
0

Beispielvorlage für C ++

template< class T >
T mod( T a, T b )
{
    T const r = a%b;
    return ((r!=0)&&((r^b)<0) ? r + b : r);
}

Mit dieser Vorlage ist der zurückgegebene Rest Null oder hat das gleiche Vorzeichen wie der Divisor (Nenner) (das Äquivalent zur Rundung auf negative Unendlichkeit), anstatt dass das C ++ - Verhalten des Restes Null ist oder das gleiche Vorzeichen wie die Dividende hat ( Zähler) (entspricht der Rundung gegen Null).

rcgldr
quelle
-1
unsigned mod(int a, unsigned b) {
    return (a >= 0 ? a % b : b - (-a) % b);
}
Neuer
quelle
-1

Diese Lösung (zur Verwendung, wenn sie modpositiv ist) vermeidet es, alle negativen Teilungs- oder Restoperationen zusammen durchzuführen:

int core_modulus(int val, int mod)
{
    if(val>=0)
        return val % mod;
    else
        return val + mod * ((mod - val - 1)/mod);
}
Robotbugs
quelle
-2

Ich würde tun:

((-1)+8) % 8 

Dies addiert die letztere Zahl zur ersten, bevor das Modulo wie gewünscht 7 ergibt. Dies sollte für jede Zahl bis zu -8 funktionieren. Für -9 addiere 2 * 8.

Toby O'Connell
quelle
2
Und für eine Variable, deren Wert sein könnte -99999?
Keith Thompson