Ist der arithmetische Überlauf gleichbedeutend mit der Modulo-Operation?

Lesezeit: 8 Minuten

Benutzer-Avatar
Avmohan

Ich muss Modulo 256-Arithmetik in C machen. Also kann ich das einfach tun

unsigned char i;
i++;

Anstatt von

int i;
i=(i+1)%256;

  • Nun, seit C99 gibt es stdint.h und Sie können einfach verwenden uintXX_t cplusplus.com/reference/cstdint

    – Benutzer2485710

    6. Februar 2014 um 18:40 Uhr

  • Obwohl dies funktioniert, fällt es in die Kategorie der übertriebenen Tricks, die wahrscheinlich von einem anderen Entwickler entfernt werden, der glaubt, dass Ihr Trick ein Fehler ist. Die explizite Angabe Ihrer Absicht mit modulo verhindert dies.

    – Mötz

    6. Februar 2014 um 18:41 Uhr

  • Wenn Sie sich nicht darauf verlassen müssen, dass jemand anderes Ihren Code verwaltet, dann ja. Ich verstehe nur nicht, warum du das tun würdest. Die zusätzliche Arbeit bei der Pflege von unübersichtlichem Code lohnt sich nicht.

    – Peter Abolins

    6. Februar 2014 um 18:54 Uhr

  • Denken Sie daran % ist Rest nicht modulo! obwohl modulo == Rest für positive Zahlen. Beide Codeteile sind nicht äquivalent, da der erste Ihnen Modulo gibt, während der zweite den Rest (Ihre i ist int nicht unsigned int).

    – Grijesh Chauhan

    6. Februar 2014 um 18:58 Uhr


  • @v3ga – es ist gut, dass du gefragt hast; es führte zu einer interessanten Diskussion und der Einsicht, dass “nicht jedes Byte 8 Bit ist” – was mir neu war. Sie haben Recht, dass Sie mit dem “expliziten” Code besser dran sind, der deutlich macht, was Sie tun – und ein guter Compiler kennt schnelle Tricks %256 Sie müssen also nicht mikrooptimieren. Es spricht viel dafür, klaren Code zu schreiben – besonders wenn es sich um ein Labor handelt und es benotet wird! Danke für den Beginn einer interessanten Diskussion.

    – Flori

    6. Februar 2014 um 19:19 Uhr

Benutzer-Avatar
Alexandre C.

Nein. Dafür gibt es keine Garantie unsigned char hat acht Bit. Verwenden uint8_t aus <stdint.h>, und es wird dir gut gehen. Dies erfordert eine Implementierung, die unterstützt stdint.h: Jeder C99-kompatible Compiler tut es, aber ältere Compiler stellen es möglicherweise nicht bereit.

Hinweis: vorzeichenlose Arithmetik läuft nie über und verhält sich wie “modulo 2^n”. Vorzeichenbehaftete arithmetische Überläufe mit undefiniertem Verhalten.

  • @Floris: Ja, aber ein C-Byte ist nicht unbedingt 8 Bit. es ist definiert als die Größe von einem char.

    – Alexander C.

    6. Februar 2014 um 18:46 Uhr


  • Und das OP erwähnt nicht einmal die Art der Maschine, auf die er abzielt, also wissen Sie es einfach nicht und sollten dies in Ihrer Antwort angeben. Auch andere Personen benötigen diese Informationen möglicherweise.

    – Benutzer2485710

    6. Februar 2014 um 18:50 Uhr

  • @ user2485710: Fertig. Da in solchen Umgebungen Byte-Tricks durchaus üblich sind, ist in der Tat ein Wort der Vorsicht angebracht.

    – Alexander C.

    6. Februar 2014 um 18:52 Uhr

  • Selbst mit einem C99-kompatiblen Compiler werden alle intN_t und uintN_t Typen sind optional und die Verfügbarkeit kann nicht garantiert werden. Auf jedem System, das keine 8-Bit-Bytes hat (zugegebenermaßen wahrscheinlich ungewöhnlich), werden sie wahrscheinlich nicht verfügbar sein.

    – Krähenmann

    6. Februar 2014 um 19:35 Uhr

  • @PaulGriffiths: Ein mir bekanntes Beispiel ist eine bestimmte eingebettete 16-Bit-DSP-Plattform von Texas Instruments, die nur die Wortadressierung unterstützt, sodass alles mindestens 16 Bit beträgt. sizeof(char) == sizeof(short) == sizef(int) == 1 == 16 bits. Die in dieser Antwort vorgeschlagene Annahme würde dort nicht funktionieren.

    – Jason R

    7. Februar 2014 um 2:39 Uhr


Ja, das Verhalten Ihrer beiden Beispiele ist gleich. Sehen C99 6.2.5 §9 :

Eine Berechnung mit vorzeichenlosen Operanden kann niemals überlaufen, da ein Ergebnis, das nicht durch den resultierenden vorzeichenlosen ganzzahligen Typ dargestellt werden kann, modulo um die Zahl reduziert wird, die um eins größer ist als der größte Wert, der durch den resultierenden Typ dargestellt werden kann.

unsigned char c = UCHAR_MAX;
c++;

Grundsätzlich ja, es gibt keinen Überlauf, aber nicht weil c ist von einem vorzeichenlosen Typ. Es gibt eine versteckte Werbung für c zu int hier und eine Integer-Konvertierung von int zu unsigned char und es ist perfekt definiert.

Zum Beispiel,

 signed char c = SCHAR_MAX;
 c++;

ist auch kein undefiniertes Verhalten, denn es ist tatsächlich äquivalent zu:

c = (int) c + 1;

und die Konvertierung von int zu signed char ist hier implementierungsdefiniert (siehe c99, 6.3.1.3p3 zu Integer-Konvertierungen). Vereinfachen CHAR_BIT == 8 wird angenommen.

Für weitere Informationen zum obigen Beispiel empfehle ich, diesen Beitrag zu lesen:

“Die kleine C-Funktion aus der Hölle”

http://blog.regehr.org/archives/482

  • Danke für den Link zu “Die kleine C-Funktion aus der Hölle”. Ich hatte es schon einmal gesehen, aber ich hatte damals vergessen, es zu bookmarken. Da ich mich nicht an den genauen Titel erinnern konnte, fand ich es unmöglich, danach zu googeln.

    – Toni

    6. Februar 2014 um 20:06 Uhr

  • Die Summe von zwei unsigned char Werte werden nicht überlaufen, aber auf Maschinen, wo sizeof (int) ist zwei, das Produkt von zwei unsigned char Werte könnten überlaufen. Historisch gesehen die Tatsache, dass der Standard einem Compiler auf einem 16-Bit-Rechner erlaubte, alles zu tun, was er wollte unsigned char x=255; x*=255; wurde nicht als Mangel angesehen, da in der Praxis sogar Compiler, die 16-Bit verwendeten, verwendet wurden int würde sich vernünftig verhalten. Die Tatsache, dass ein solcher Code zu undefiniertem Verhalten führte, wurde als theoretisches Problem angesehen und nicht als Gelegenheit für Compiler, Gesetze von Zeit und Kausalität zu negieren.

    – Superkatze

    25. Juli 2015 um 20:18 Uhr

Benutzer-Avatar
Keith Thompson

Sehr wahrscheinlich ja, aber die Gründe dafür sind in diesem Fall eigentlich ziemlich kompliziert.

unsigned char i = 255;
i++;

Das i++ ist äquivalent zu i = i + 1.

(Naja fast. i++ ergibt den Wert von i Vor es wurde inkrementiert, also ist es wirklich äquivalent zu (tmp=i; i = i + 1; tmp). Aber da das Ergebnis in diesem Fall verworfen wird, wirft das keine zusätzlichen Probleme auf.)

Seit unsigned char ist ein schmaler Typ, ein unsigned char Operand an die + Betreiber wird befördert int (vorausgesetzt int kann alle möglichen Werte im Bereich von enthalten unsigned char). Also wenn i == 255und UCHAR_MAX == 255dann ist das Ergebnis der Addition 256und ist vom Typ (signiert) int.

Die Zuordnung implizit konvertiert der Wert 256 aus int zurück zu unsigned char. Die Konvertierung in einen vorzeichenlosen Typ ist gut definiert; das Ergebnis ist Modulo reduziert MAX+1wo MAX ist der Maximalwert des Zieltyps ohne Vorzeichen.

Wenn i wurden als deklariert unsigned int:

unsigned int i = UINT_MAX;
i++;

es würde keine Typkonvertierung geben, aber die Semantik der + Operator für vorzeichenlose Typen Auch Reduktionsmodul angeben MAX+1.

Denken Sie daran, dass der zugewiesene Wert i ist mathematisch äquivalent zu (i+1) % UCHAR_MAX. UCHAR_MAX ist normalerweise 255und das garantiert wenigstens 255aber es kann rechtlich größer sein.

Es könnte ein exotisches System geben, auf dem UCHAR_MAX ist auch in einem signierten gespeichert werden int Objekt. Dies würde erfordern UCHAR_MAX > INT_MAXwas bedeutet, dass das System haben müsste wenigstens 16-Bit-Bytes. Auf einem solchen System würde die Förderung ausfallen unsigned char zu unsigned int. Das Endergebnis wäre dasselbe. Es ist unwahrscheinlich, dass Sie auf ein solches System stoßen. Ich denke, es gibt C-Implementierungen für einige DSPs die Bytes größer als 8 Bit haben. Die Anzahl der Bits in einem Byte wird durch angegeben CHAR_BITdefiniert in <limits.h>.

CHAR_BIT > 8 bedeutet nicht unbedingt UCHAR_MAX > INT_MAX. Zum Beispiel könnten Sie haben CHAR_BIT == 16 und sizeof (int) == 2 dh 16-Bit-Bytes und 32 Bit ints).

Benutzer-Avatar
JAB

Es gibt eine andere Alternative, die nicht erwähnt wurde, wenn Sie keinen anderen Datentyp verwenden möchten.

unsigned int i;
// ...
i = (i+1) & 0xFF; // 0xFF == 255

Das funktioniert, weil das Modulo-Element == 2^nwas bedeutet, dass die Reichweite sein wird [0, 2^n-1] und somit wird eine Bitmaske den Wert leicht innerhalb Ihres gewünschten Bereichs halten. Es ist möglich, dass diese Methode nicht viel oder weniger effizient wäre als die unsigned char/uint8_t Version, je nachdem, was Ihr Compiler hinter den Kulissen macht und wie das Zielsystem Nicht-Wort-Ladevorgänge handhabt (z. B. erfordern einige RISC-Architekturen zusätzliche Operationen, um Nicht-Wort-Größenwerte zu laden). Dies setzt auch voraus, dass Ihr Compiler die Verwendung von Zweierpotenz-Modulo-Arithmetik für vorzeichenlose Werte nicht erkennt und natürlich eine Bitmaske für Sie ersetzt, da in solchen Fällen die Modulo-Verwendung einen größeren semantischen Wert hätte (obwohl dies verwendet wird da die Entscheidungsgrundlage natürlich nicht gerade tragbar ist).

Ein Vorteil dieser Methode ist, dass Sie sie für Zweierpotenzen verwenden können, die nicht auch die Größe eines Datentyps haben, z

i = (i+1) & 0x1FF; // i %= 512
i = (i+1) & 0x3FF; // i %= 1024
// etc.

Benutzer-Avatar
Gavin

Dies sollte gut funktionieren, da es nur auf 0 zurücklaufen sollte. Wie in einem Kommentar zu einer anderen Antwort darauf hingewiesen wurde, sollten Sie dies nur tun, wenn der Wert unsigned ist, da Sie mit einem signierten Wert möglicherweise ein undefiniertes Verhalten erhalten.

Es ist jedoch wahrscheinlich am besten, dies mit Modulo zu belassen, da der Code von anderen Personen, die den Code pflegen, besser verstanden wird und ein intelligenter Compiler diese Optimierung möglicherweise sowieso vornimmt, was sie von vornherein sinnlos machen kann. Außerdem wird der Performance-Unterschied wohl so gering sein, dass es erstmal egal wäre.

Benutzer-Avatar
Wajahat

Es funktioniert, wenn die Anzahl der Bits, die Sie zur Darstellung der Zahl verwenden, gleich der Anzahl der Bits in binärer (vorzeichenloser) Darstellung (100000000) des Divisors -1 ist, was in diesem Fall ist: 9-1 = 8 (Zeichen)

1351740cookie-checkIst der arithmetische Überlauf gleichbedeutend mit der Modulo-Operation?

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

Privacy policy