Modulo-Betrieb mit negativen Zahlen

190

In einem C-Programm habe ich die folgenden Operationen versucht (nur um das Verhalten zu überprüfen)

 x = 5 % (-3);
 y = (-5) % (3);
 z = (-5) % (-3); 

printf("%d ,%d ,%d", x, y, z); 

gab mir Ausgabe wie (2, -2 , -2)in gcc. Ich hatte jedes Mal ein positives Ergebnis erwartet. Kann ein Modul negativ sein? Kann jemand dieses Verhalten erklären?

Alva
quelle
Mögliches Duplikat von stackoverflow.com/questions/4003232/…
James
1
mögliches Duplikat des Modulo-Operators mit negativen Werten
sugavaneshb

Antworten:

167

C99 erfordert, dass wann darstellbar a/bist:

(a/b) * b + a%b soll gleich seina

Dies ist logischerweise sinnvoll. Richtig?

Mal sehen, wozu das führt:


Beispiel A. 5/(-3)ist-1

=> (-1) * (-3) + 5%(-3) =5

Dies kann nur passieren, wenn 5%(-3)2 ist.


Beispiel B. (-5)/3ist-1

=> (-1) * 3 + (-5)%3 =-5

Dies kann nur passieren, wenn dies der Fall (-5)%3ist-2

ArjunShankar
quelle
1
Sollte der Compiler klug genug sein und erkennen, dass ein vorzeichenloses Modulo eines anderen vorzeichenlosen immer positiv ist? Derzeit (naja, GCC 5.2) scheint der Compiler zu denken, dass "%" in diesem Fall ein "int" zurückgibt und nicht "unsigned", selbst wenn beide Operanden uint32_t oder größer sind.
Frederick Nord
@FrederickNord Haben Sie ein Beispiel, um dieses Verhalten zu zeigen ?
chux
10
Verstehe, dass das, was du beschreibst, die übliche int (a / b) (abgeschnittene) Beschreibung von mod ist. Es ist aber auch möglich, dass die Regel Etage (a / b) (Knuth) ist. Im Knuth-Fall -5/3ist -2und der Mod wird 1. Kurz gesagt: Ein Modul hat ein Vorzeichen, das dem Dividendenzeichen folgt (abgeschnitten), das andere Modul hat ein Vorzeichen, das dem Divisorzeichen (Knuth) folgt.
Isaac
1
Dies ist ein Fall, in dem der C-Standard genau nicht das ist, was ich will. Ich wollte nie auf Null oder negative Modulo-Zahlen kürzen, aber ich möchte oft das Gegenteil und muss um C.
Joe
141

Der %Operator in C ist nicht der Modulo- Operator, sondern der Restoperator .

Modulo- und Restoperatoren unterscheiden sich hinsichtlich negativer Werte.

Bei einem Restoperator entspricht das Vorzeichen des Ergebnisses dem Vorzeichen der Dividende, während bei einem Modulo-Operator das Vorzeichen des Ergebnisses dem Divisor entspricht.

C definiert die %Operation für a % b:

  a == (a / b * b) + a % b

mit /der ganzzahligen Division mit Kürzung in Richtung 0. Dies ist die Kürzung, die in Richtung 0(und nicht in Richtung negativer Unendlichkeit) vorgenommen wird und die den %Operator als Restoperator und nicht als Modulooperator definiert .

ouah
quelle
7
Der Rest ist per Definition das Ergebnis der Modulo-Operation . Es sollte keinen Restoperator geben, da es keinen Restoperator gibt, er heißt Modulo.
Gronostaj
40
@gronostaj nicht in CS. Sehen Sie sich übergeordnete Sprachen wie Haskell oder Scheme an, die beide zwei verschiedene Operatoren definieren ( remainderund moduloin Scheme remund modin Haskell). Diese Operatorspezifikationen unterscheiden sich in diesen Sprachen hinsichtlich der Art und Weise, wie die Division durchgeführt wird: Abschneiden gegen 0 oder gegen negative Unendlichkeit. Übrigens nennt der C-Standard niemals %den Modulo-Operator , sondern nennt ihn nur den % -Operator .
Ouah
2
Nicht zu verwechseln mit der remainder Funktion in C, die den IEEE-Rest mit einer auf die nächste Runde hin nächsten Semantik in der Division implementiert
Eric
67

Basierend auf der C99-Spezifikation: a == (a / b) * b + a % b

Wir können eine zu berechnende Funktion schreiben (a % b) == a - (a / b) * b!

int remainder(int a, int b)
{
    return a - (a / b) * b;
}

Für den Modulo-Betrieb können wir die folgende Funktion haben (vorausgesetzt b > 0)

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

Mein Fazit ist, dass a % bin C eine Restoperation und KEINE Modulooperation ist.

Dewang
quelle
3
Dies gibt nicht positive Ergebnisse , wenn bnegativ ist (und in der Tat für rund bsowohl negative als es gibt die Ergebnisse weniger als -b). Um positive Ergebnisse für alle Eingaben zu gewährleisten, die Sie verwenden können, r + abs(b)oder um mit dem bVorzeichen übereinzustimmen, können Sie r*b < 0stattdessen die Bedingung in ändern .
Martin Ender
@MartinEnder r + abs(b)ist UB wenn b == INT_MIN.
chux
60

Ich glaube nicht, dass überprüft werden muss, ob die Zahl negativ ist.

Eine einfache Funktion, um das positive Modulo zu finden, wäre dies -

Edit: Angenommen N > 0undN + N - 1 <= INT_MAX

int modulo(int x,int N){
    return (x % N + N) %N;
}

Dies funktioniert sowohl für positive als auch für negative Werte von x.

Original PS: auch Wie von @chux, Wenn x und N können so etwas wie INT_MAX-1 erreichen und INT_MAX jeweils nur ersetzen intmit long long int.

Und wenn sie auch lange lange Grenzen überschreiten (dh in der Nähe von LLONG_MAX), müssen Sie positive und negative Fälle getrennt behandeln, wie in anderen Antworten hier beschrieben.

Udayraj Deshmukh
quelle
1
Beachten Sie, dass N < 0das Ergebnis wie in negativ sein kann modulo(7, -3) --> -2. Auch x % N + Nkann überlaufen intMathe , das Verhalten ist nicht definiert. zB modulo(INT_MAX - 1,INT_MAX)könnte -3 ergeben.
chux
Ja, in diesem Fall können Sie long long intden negativen Fall einfach verwenden oder separat behandeln (auf Kosten des Verlusts der Einfachheit).
Udayraj Deshmukh
9

Die anderen Antworten haben in C99 oder später erklärt, dass die Division von ganzen Zahlen mit negativen Operanden immer gegen Null abschneidet .

Beachten Sie, dass in C89 die Implementierungsdefinition festgelegt ist, ob das Ergebnis nach oben oder unten gerundet wird. Denn (a/b) * b + a%bgleich ain allen Standards, das Ergebnis %ist negativ Operanden beteiligt auch die Implementierung definiert in C89.

Yu Hao
quelle
5

Kann ein Modul negativ sein?

%kann negativ sein, da es sich um den Restoperator handelt , den Rest nach der Division, nicht nach Euclidean_division . Seit C99 kann das Ergebnis 0 sein, negativ oder positiv.

 // a % b
 7 %  3 -->  1  
 7 % -3 -->  1  
-7 %  3 --> -1  
-7 % -3 --> -1  

Das gewünschte Modulo OP ist ein klassisches euklidisches Modulo , nicht %.

Ich hatte jedes Mal ein positives Ergebnis erwartet.

Um ein euklidisches Modulo auszuführen, das immer dann gut definiert a/bist, wenn es definiert ist, hat a,bes ein beliebiges Vorzeichen und das Ergebnis ist niemals negativ:

int modulo_Euclidean(int a, int b) {
  int m = a % b;
  if (m < 0) {
    // m += (b < 0) ? -b : b; // avoid this form: it is UB when b == INT_MIN
    m = (b < 0) ? m - b : m + b;
  }
  return m;
}

modulo_Euclidean( 7,  3) -->  1  
modulo_Euclidean( 7, -3) -->  1  
modulo_Euclidean(-7,  3) -->  2  
modulo_Euclidean(-7, -3) -->  2   
chux - Monica wieder einsetzen
quelle
2

Das Ergebnis der Modulo-Operation hängt vom Vorzeichen des Zählers ab, und daher erhalten Sie -2 für y und z

Hier ist die Referenz

http://www.chemie.fu-berlin.de/chemnet/use/info/libc/libc_14.html

Integer Division

In diesem Abschnitt werden Funktionen zum Durchführen einer Ganzzahldivision beschrieben. Diese Funktionen sind in der GNU C-Bibliothek redundant, da in GNU C der Operator '/' immer gegen Null rundet. In anderen C-Implementierungen kann '/' jedoch mit negativen Argumenten anders gerundet werden. div und ldiv sind nützlich, weil sie angeben, wie der Quotient gerundet werden soll: gegen Null. Der Rest hat das gleiche Vorzeichen wie der Zähler.

Kartik Anand
quelle
5
Sie beziehen sich auf einen Text über ANSI C. Dies ist eine ziemlich alte Norm von C. Sie sind sich nicht sicher, ob der Text in Bezug auf ANSI C korrekt ist, aber definitiv nicht in Bezug auf C99. In C99 ist §6.5.5 Integer Division so definiert, dass es immer gegen Null abschneidet.
Palec
2

In der Mathematik, aus der diese Konventionen stammen, gibt es keine Behauptung, dass die Modulo-Arithmetik ein positives Ergebnis liefern sollte.

Z.B.

1 mod 5 = 1, kann aber auch gleich -4 sein. Das heißt, 1/5 ergibt einen Rest 1 von 0 oder -4 von 5. (Beide Faktoren von 5)

In ähnlicher Weise ist -1 mod 5 = -1, aber es kann auch gleich 4 sein. Das heißt, -1/5 ergibt einen Rest -1 von 0 oder 4 von -5. (Beide Faktoren von 5)

Weitere Informationen finden Sie in den Äquivalenzklassen in Mathematik.

DarkPurple141
quelle
Die Äquivalenzklasse ist ein anderes Konzept und Modulo wird sehr streng definiert. Nehmen wir an, wir haben zwei ganzzahlige Zahlen aund b, b <> 0. Nach dem euklidischen Divisionssatz existiert genau ein Paar von ganzen Zahlen m, rwobei a = m * b + rund 0 <= r < abs( b ). Das Gesagte rist das Ergebnis der (mathematischen) Modulo-Operation und per Definition nicht negativ. Weitere Informationen und Links auf Wikipedia: en.wikipedia.org/wiki/Euclidean_division
Ister
Das stimmt nicht 1 mod 5ist immer 1. -4 mod 5könnte auch 1 sein, aber es sind verschiedene Dinge.
FelipeC
2

Gemäß dem C99-Standard , Abschnitt 6.5.5 Multiplikative Operatoren , ist Folgendes erforderlich:

(a / b) * b + a % b = a

Fazit

Das Vorzeichen des Ergebnisses einer Restoperation gemäß C99 ist das gleiche wie das der Dividende.

Schauen wir uns einige Beispiele an ( dividend / divisor):

Wenn nur die Dividende negativ ist

(-3 / 2) * 2  +  -3 % 2 = -3

(-3 / 2) * 2 = -2

(-3 % 2) must be -1

Wenn nur der Divisor negativ ist

(3 / -2) * -2  +  3 % -2 = 3

(3 / -2) * -2 = 2

(3 % -2) must be 1

Wenn sowohl Divisor als auch Dividende negativ sind

(-3 / -2) * -2  +  -3 % -2 = -3

(-3 / -2) * -2 = -2

(-3 % -2) must be -1

6.5.5 Multiplikative Operatoren

Syntax

  1. multiplikativer Ausdruck:
    • cast-expression
    • multiplicative-expression * cast-expression
    • multiplicative-expression / cast-expression
    • multiplicative-expression % cast-expression

Einschränkungen

  1. Jeder der Operanden muss einen arithmetischen Typ haben. Die Operanden des Operators % müssen vom Typ Integer sein.

Semantik

  1. Die üblichen arithmetischen Konvertierungen werden an den Operanden durchgeführt.

  2. Das Ergebnis des binären * Operators ist das Produkt der Operanden.

  3. Das Ergebnis des Operators / ist der Quotient aus der Division des ersten Operanden durch den zweiten; Das Ergebnis des Operators % ist der Rest. Wenn in beiden Operationen der Wert des zweiten Operanden Null ist, ist das Verhalten undefiniert.

  4. Wenn ganze Zahlen geteilt werden, ist das Ergebnis des Operators / der algebraische Quotient, wobei jeder gebrochene Teil verworfen wird [1]. Wenn der Quotient darstellbar a/bist, muss der Ausdruck (a/b)*b + a%bgleich sein a.

[1]: Dies wird oft als "Abschneiden gegen Null" bezeichnet.

Ricardo Biehl Pasquali
quelle
1

Der Moduloperator gibt den Rest an. Der Moduloperator in c nimmt normalerweise das Vorzeichen des Zählers an

  1. x = 5% (-3) - hier ist der Zähler positiv, daher ergibt sich 2
  2. y = (-5)% (3) - hier ist der Zähler negativ, daher ergibt sich -2
  3. z = (-5)% (-3) - hier ist der Zähler negativ, daher ergibt sich -2

Auch der Moduloperator (Restoperator) kann nur mit einem ganzzahligen Typ und nicht mit einem Gleitkomma verwendet werden.

Kavya
quelle
1
Es wäre schön, wenn Sie dies mit Links zu externen Ressourcen sichern könnten.
J ... S
1

Ich glaube, es ist nützlicher, daran zu denken, modwie es in der abstrakten Arithmetik definiert ist. nicht als Operation, sondern als eine ganz andere Klasse von Arithmetik mit verschiedenen Elementen und verschiedenen Operatoren. Das bedeutet, dass die Addition in mod 3nicht mit der "normalen" Addition identisch ist. das ist; Ganzzahladdition.

Also, wenn Sie tun:

5 % -3

Sie versuchen, die Ganzzahl 5 einem Element in der Menge von zuzuordnen mod -3. Dies sind die Elemente von mod -3:

{ 0, -2, -1 }

So:

0 => 0, 1 => -2, 2 => -1, 3 => 0, 4 => -2, 5 => -1

Angenommen, Sie müssen aus irgendeinem Grund 30 Stunden aufbleiben. Wie viele Stunden haben Sie noch an diesem Tag? 30 mod -24.

Aber was C implementiert, ist nicht mod, es ist ein Rest. Der Punkt ist jedenfalls, dass es sinnvoll ist, Negative zurückzugeben.

FelipeC
quelle