Modulo-Operation mit negativen Zahlen

Lesezeit: 7 Minuten

Alvas Benutzeravatar
Alva

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

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

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

Es gab mir Ausgabe als (2, -2 , -2) im gcc. Ich erwartete jedes Mal ein positives Ergebnis. Kann ein Modul negativ sein? Kann sich jemand dieses Verhalten erklären?

  • Mögliches Duplikat von stackoverflow.com/questions/4003232/…

    – James

    30. Juli 2012 um 11:41 Uhr

  • mögliches Duplikat des Modulo-Operators mit negativen Werten

    – sugavaneshb

    8. Februar 2015 um 8:46 Uhr

  • Es gibt zwei verschiedene Interpretationen des Moduls torstencurdt.com/tech/posts/modulo-of-negative-numbers

    – tcurdt

    1. Februar um 12:26 Uhr

Benutzeravatar von ArjunShankar
ArjunShankar

C99 erfordert das wann a/b ist darstellbar:

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

Das macht Sinn, logisch. Recht?

Mal sehen, wozu das führt:


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

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

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


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

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

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

  • Sollte der Compiler schlau genug sein und erkennen, dass ein unsigned modulo ein other unsigned immer positiv ist? Derzeit (na ja, GCC 5.2) scheint der Compiler zu glauben, dass “%” in diesem Fall ein “int” zurückgibt, anstatt “unsigned”, selbst wenn beide Operanden uint32_t oder größer sind.

    – Friedrich Nord

    24. September 2016 um 14:56 Uhr

  • @FrederickNord Hast du ein Beispiel, um dieses Verhalten zu zeigen?

    – chux – Wiedereinsetzung von Monica

    24. Februar 2017 um 16:16 Uhr


  • Verstehe, dass das, was du beschreibst, die übliche int(a/b) (truncate) Beschreibung von mod ist. Es ist aber auch möglich, dass die Regel floor(a/b) ist (Knuth). Im Fall Knuth -5/3 ist -2 und der mod wird 1. Kurz gesagt: ein Modul hat ein Vorzeichen, das auf das Dividendenzeichen folgt (truncate), das andere Modul hat ein Vorzeichen, das auf das Divisorzeichen folgt (Knuth).

    Benutzer8017719

    27. Mai 2018 um 9:36 Uhr

  • 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 abschneiden, möchte aber oft das Gegenteil und muss um C herum arbeiten.

    – Jo

    6. August 2018 um 22:27 Uhr

  • @Nick der a/b im Ausdruck (a/b) * b + a%b oben ist ganzzahlige Division, also (a/b) * b ist ungleich zu a wenn nicht a ist teilbar durch b.

    – Laurence Gonsalves

    17. Dezember 2021 um 17:51 Uhr

Benutzeravatar von ouah
ouah

Das % Operator in C ist nicht der modulo Betreiber aber die Rest Operator.

Modulo- und Restoperatoren unterscheiden sich in Bezug auf negative Werte.

Bei einem Restoperator ist das Vorzeichen des Ergebnisses gleich dem Vorzeichen des Dividenden (Zähler), während bei einem Modulo-Operator das Vorzeichen des Ergebnisses gleich dem Vorzeichen des Divisors (Nenner) ist.

C definiert die % Betrieb für a % b wie:

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

mit / die ganzzahlige Division mit Abschneiden in Richtung 0. Das ist die Kürzung, auf die zugegriffen wird 0 (und nicht in Richtung negative Unendlichkeit), die das definiert % als Restoperator und nicht als Modulo-Operator.

  • Der Rest ist das Ergebnis der Modulo-Operation per Definition. Es sollte keinen Restoperator geben, weil es keinen Restoperator gibt, er heißt Modulo.

    – gronostaj

    27. Juni 2015 um 20:49 Uhr

  • @gronostaj nicht in CS. Schauen Sie sich höhere Sprachen wie Haskell oder Scheme an, die beide zwei verschiedene Operatoren definieren (remainder und modulo im Schema, rem und mod in Haskel). Diese Operatorspezifikationen unterscheiden sich in diesen Sprachen darin, wie die Division durchgeführt wird: Abschneiden in Richtung 0 oder in Richtung negativ unendlich. Übrigens nennt der C-Standard das nie % das Modulo-Operatorsie nennen es einfach das % Operator.

    – au

    21. Dezember 2015 um 16:55 Uhr

  • Nicht zu verwechseln mit der remainder Funktion in C, das den IEEE-Rest mit Round-towards-nearest-Semantik in der Division implementiert

    – Erich

    18. September 2017 um 2:11 Uhr


  • @gronostaj Der Link, den Sie bereitgestellt haben, unterscheidet ausdrücklich zwischen kleinster positiver Restund kleinster absoluter Rest was natürlich nicht immer positiv ist. Es gibt -2 als kleinster absoluter Rest von 43 / 5 (seit 43 = 9 * 5 - 2). Die CS-Definition ist noch einmal anders. Aber es ist erwähnenswert, dass, nur weil wir etwas gelernt haben, als wir 10 Jahre alt waren, es immer noch einige Feinheiten geben kann. Versuchen round(2.5) in Python zum Beispiel. Es ist 2, nicht 3. Und das ist mathematisch korrekt, um Verzerrungen in statistischen Momenten zu vermeiden.

    – Mike Williamson

    18. Februar 2021 um 17:25 Uhr

Benutzeravatar von dewang
dewang

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 die Modulo-Operation können wir die folgende Funktion haben (unter der Annahme b > 0)

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

Mein Fazit ist das a % b in C ist eine Restoperation und keine Modulo-Operation.

  • Dies gibt keine positiven Ergebnisse, wenn b ist negativ (und zwar für r und b beide negativ, es gibt Ergebnisse kleiner als -b). Um positive Ergebnisse für alle Eingaben zu gewährleisten, die Sie verwenden könnten r + abs(b) oder passend bs-Zeichen, auf das Sie die Bedingung ändern könnten r*b < 0 stattdessen.

    – Martin Ender

    20. September 2016 um 11:42 Uhr

  • @MartinEnder r + abs(b) ist UB wann b == INT_MIN.

    – chux – Wiedereinsetzung von Monica

    27. September 2018 um 4:20 Uhr

Benutzeravatar von Udayraj Deshmukh
Udayraj Deshmukh

Ich glaube nicht, dass es keine Notwendigkeit gibt, zu überprüfen, ob die Zahl negativ ist.

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

Bearbeiten: Vorausgesetzt N > 0 und N + N - 1 <= INT_MAX

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

Das funktioniert für sowohl positiv als auch negativ Werte von x.

Original-PS: auch wie von @chux hervorgehoben, wenn Ihr x und N etwas wie INT_MAX-1 bzw. INT_MAX erreichen können, ersetzen Sie einfach int mit long long int.

Und wenn sie auch die Grenzen von long long ü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.

Die anderen Antworten haben in erklärt C99 oder später Division von ganzen Zahlen mit immer negativen Operanden gegen null abschneiden.

Beachten Sie, dass in C89, ob das Ergebnis auf- oder abgerundet wird, ist implementierungsabhängig. Da (a/b) * b + a%b gleich a in allen Standards, das Ergebnis von % Das Einbeziehen negativer Operanden ist ebenfalls in C89 implementierungsdefiniert.

Kann ein Modul negativ sein?

% kann negativ sein, da es der Restoperator ist, der Rest nach der Division, nicht danach Euklidische_Teilung. Seit C99 kann das Ergebnis 0, negativ oder positiv sein.

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

Das modulo OP gesucht ist ein Klassiker Euklidischer Modulonicht %.

Ich erwartete jedes Mal ein positives Ergebnis.

Um ein euklidisches Modulo auszuführen, das wann immer gut definiert ist a/b ist definiert, a,b haben 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   

Benutzeravatar von psqli
psql

Entsprechend C99-StandardSektion 6.5.5 Multiplikative Operatorenwird Folgendes benötigt:

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

Fazit

Das Vorzeichen des Ergebnisses einer Restoperation ist gemäß C99 dasselbe wie das des Dividenden.

Sehen 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 vom arithmetischen Typ sein. Die Operanden der % Der Operator muss vom Typ Integer sein.

Semantik

  1. An den Operanden werden die üblichen arithmetischen Umwandlungen durchgeführt.

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

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

  4. Wenn ganze Zahlen dividiert werden, ist das Ergebnis der / Operator ist der algebraische Quotient, wobei jeder Bruchteil verworfen wird [1]. Wenn der Quotient a/b darstellbar ist, der Ausdruck (a/b)*b + a%b soll gleich sein a.

[1]: Dies wird oft als “Abschneiden in Richtung Null” bezeichnet.

1426530cookie-checkModulo-Operation mit negativen Zahlen

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy