Ist ((a + (b & 255)) & 255) dasselbe wie ((a + b) & 255)?

Ich habe C ++ - Code durchsucht und so etwas gefunden:

(a + (b & 255)) & 255

Das doppelte UND ärgerte mich, also dachte ich an:

(a + b) & 255

( aund bsind 32-Bit-Ganzzahlen ohne Vorzeichen)

Ich schrieb schnell ein Testskript (JS), um meine Theorie zu bestätigen:

for (var i = 0; i < 100; i++) {
    var a = Math.ceil(Math.random() * 0xFFFF),
        b = Math.ceil(Math.random() * 0xFFFF);

    var expr1 = (a + (b & 255)) & 255,
        expr2 = (a + b) & 255;

    if (expr1 != expr2) {
        console.log("Numbers " + a + " and " + b + " mismatch!");
        break;
    }
}

Obwohl das Skript meine Hypothese bestätigt hat (beide Operationen sind gleich), vertraue ich ihr immer noch nicht, weil 1) zufällig und 2) ich kein Mathematiker bin, ich habe keine Ahnung, was ich tue .

Entschuldigen Sie auch den Lisp-y-Titel. Fühlen Sie sich frei, es zu bearbeiten.

Sie sind gleich. Hier ist ein Beweis:

Notieren Sie zuerst die Identität (A + B) mod C = (A mod C + B mod C) mod C

Lassen Sie sich neu formuliert das Problem , indem in Bezug auf a & 255wie in Vertretung von a % 256. Dies ist wahr, da aes nicht signiert ist.

So (a + (b & 255)) & 255ist es auch(a + (b % 256)) % 256

Dies ist dasselbe wie (a % 256 + b % 256 % 256) % 256(Ich habe die oben angegebene Identität angewendet: Beachten Sie, dass modund %für nicht signierte Typen gleichwertig sind.)

Dies vereinfacht das, (a % 256 + b % 256) % 256worauf es ankommt (a + b) % 256(erneutes Anwenden der Identität). Sie können dann den bitweisen Operator zurücksetzen, um zu geben

(a + b) & 255

den Beweis vervollständigen.

Bei der Positionsaddition, Subtraktion und Multiplikation von vorzeichenlosen Zahlen, um vorzeichenlose Ergebnisse zu erzielen, wirken sich signifikantere Ziffern der Eingabe nicht auf weniger signifikante Ziffern des Ergebnisses aus. Dies gilt für die binäre Arithmetik ebenso wie für die Dezimalarithmetik. Dies gilt auch für vorzeichenbehaftete Arithmetik mit "Zweierkomplement", nicht jedoch für vorzeichenbehaftete arithmetische Arithmetik.

Wir müssen jedoch vorsichtig sein, wenn wir Regeln aus der binären Arithmetik nehmen und auf C anwenden (ich glaube, C ++ hat die gleichen Regeln wie C für dieses Zeug, aber ich bin nicht 100% sicher), weil C-Arithmetik einige arkane Regeln hat, die uns auslösen können oben. Die vorzeichenlose Arithmetik in C folgt einfachen binären Umlaufregeln, aber der vorzeichenbehaftete arithmetische Überlauf ist ein undefiniertes Verhalten. Schlimmer noch, unter bestimmten Umständen "befördert" C automatisch einen nicht signierten Typ zu (signiertem) int.

Undefiniertes Verhalten in C kann besonders heimtückisch sein. Ein dummer Compiler (oder ein Compiler auf einer niedrigen Optimierungsstufe) wird wahrscheinlich das tun, was Sie aufgrund Ihres Verständnisses der binären Arithmetik erwarten, während ein optimierender Compiler Ihren Code auf seltsame Weise beschädigen kann.

Zurück zur Formel in der Frage: Die Äquivalenz hängt von den Operandentypen ab.

Wenn es sich um vorzeichenlose Ganzzahlen handelt, deren Größe größer oder gleich der Größe von ist, intist das Überlaufverhalten des Additionsoperators als einfacher binärer Wraparound definiert. Ob wir die hohen 24 Bits eines Operanden vor der Additionsoperation maskieren oder nicht, hat keinen Einfluss auf die niedrigen Bits des Ergebnisses.

Wenn es sich um Ganzzahlen ohne Vorzeichen handelt, deren Größe geringer intist, werden sie zu (mit Vorzeichen) heraufgestuft int. Der Überlauf von vorzeichenbehafteten Ganzzahlen ist ein undefiniertes Verhalten, aber zumindest auf jeder Plattform, auf die ich gestoßen bin, ist der Größenunterschied zwischen verschiedenen Ganzzahltypen groß genug, dass eine einzelne Addition von zwei heraufgestuften Werten keinen Überlauf verursacht. Wir können also wieder auf das einfach binäre arithmetische Argument zurückgreifen, um die Aussagen als äquivalent zu betrachten.

Wenn es sich um vorzeichenbehaftete Ganzzahlen handelt, deren Größe kleiner als int ist, kann es erneut nicht zu einem Überlauf kommen. Bei Implementierungen mit zwei Komplementen können wir uns auf das Standardargument der binären Arithmetik verlassen, um zu sagen, dass sie gleichwertig sind. Bei Vorzeichengrößen oder solchen, die Implementierungen ergänzen, wären sie nicht gleichwertig.

OTOH wenn aundb vorzeichenbehaftete Ganzzahlen deren Größe größer oder gleich der Größe von int war, dann gibt es sogar bei Implementierungen mit zwei Komplementen Fälle, in denen eine Anweisung gut definiert wäre, während die andere ein undefiniertes Verhalten wäre.

Lemma: a & 255 == a % 256für unsigniertea .

Unsigned aneu geschrieben werden können , wie m * 0x100 + beinige unsigned m, b, 0 <= b < 0xff, 0 <= m <= 0xffffff. Aus beiden Definitionen folgt, dassa & 255 == b == a % 256 .

Zusätzlich brauchen wir:

• die Verteilungseigenschaft: (a + b) mod n = [(a mod n) + (b mod n)] mod n
• die Definition der vorzeichenlosen Addition, mathematisch: (a + b) ==> (a + b) % (2 ^ 32)

So:

(a + (b & 255)) & 255 = ((a + (b & 255)) % (2^32)) & 255      // def'n of addition
                      = ((a + (b % 256)) % (2^32)) % 256      // lemma
                      = (a + (b % 256)) % 256                 // because 256 divides (2^32)
                      = ((a % 256) + (b % 256 % 256)) % 256   // Distributive
                      = ((a % 256) + (b % 256)) % 256         // a mod n mod n = a mod n
                      = (a + b) % 256                         // Distributive again
                      = (a + b) & 255                         // lemma

Also ja, es ist wahr. Für 32-Bit-Ganzzahlen ohne Vorzeichen.

Was ist mit anderen Integer-Typen?

• Für 64-Bit - Ganzzahl um alle der oben genannte gelten ebenso gut, nur ersetzt 2^64zu 2^32.
• Bei 8- und 16-Bit-Ganzzahlen ohne Vorzeichen umfasst das Hinzufügen eine Heraufstufung zu int. Dies intwird bei keinem dieser Vorgänge überlaufen oder negativ sein, sodass alle gültig bleiben.
• Für signierte ganze Zahlen, wenn entweder a+boder a+(b&255)Überlauf, dann ist es nicht definiertes Verhalten. Die Gleichheit kann also nicht gelten - es gibt Fälle, in denen (a+b)&255undefiniertes Verhalten vorliegt, dies jedoch (a+(b&255))&255nicht der Fall ist.

Ja, (a + b) & 255ist in Ordnung.

Erinnerst du dich an den Zusatz in der Schule? Sie fügen Zahlen Ziffer für Ziffer hinzu und fügen der nächsten Ziffernspalte einen Übertragswert hinzu. Es gibt keine Möglichkeit für eine spätere (signifikantere) Ziffernspalte, eine bereits verarbeitete Spalte zu beeinflussen. Aus diesem Grund macht es keinen Unterschied, ob Sie die Ziffern nur im Ergebnis oder auch zuerst in einem Argument auf Null setzen.

Das Obige ist nicht immer wahr, der C ++ - Standard erlaubt eine Implementierung, die dies brechen würde.

Eine solche Deathstation 9000 : - ) müsste ein 33-Bit verwenden int, wenn das OP unsigned shortmit "32-Bit-Ganzzahlen ohne Vorzeichen" gemeint wäre . Wenn unsigned intgemeint wäre, müsste der DS9K ein 32-Bit intund ein 32-Bit unsigned intmit einem Auffüllbit verwenden. (Die vorzeichenlosen Ganzzahlen müssen dieselbe Größe wie ihre vorzeichenbehafteten Gegenstücke gemäß §3.9.1 / 3 haben, und Füllbits sind in §3.9.1 / 1 zulässig.) Andere Kombinationen von Größen und Füllbits würden ebenfalls funktionieren.

Soweit ich das beurteilen kann, ist dies der einzige Weg, es zu brechen, weil:

• Die Ganzzahldarstellung muss ein "rein binäres" Codierungsschema (§3.9.1 / 7 und die Fußnote) verwenden. Alle Bits außer den Füllbits und das Vorzeichenbit müssen einen Wert von 2 ⁿ liefern
• int- intHeraufstufung ist nur zulässig, wenn alle Werte des Quelltyps (§4.5 / 1) dargestellt werden können. Daher intmüssen mindestens 32 Bits zum Wert beitragen, plus ein Vorzeichenbit.
• Das intkann nicht mehr Wertbits haben (ohne das Vorzeichenbit) als 32, da sonst eine Addition nicht überlaufen kann.

Sie haben bereits die kluge Antwort: Vorzeichenlose Arithmetik ist Modulo-Arithmetik und daher gelten die Ergebnisse, Sie können es mathematisch beweisen ...

Eine coole Sache an Computern ist jedoch, dass Computer schnell sind. In der Tat sind sie so schnell, dass die Aufzählung aller gültigen Kombinationen von 32 Bit in angemessener Zeit möglich ist (versuchen Sie es nicht mit 64 Bit).

In Ihrem Fall mag ich es persönlich, es einfach auf einen Computer zu werfen. Ich brauche weniger Zeit, um mich davon zu überzeugen, dass das Programm korrekt ist, als um mich selbst zu überzeugen, als der mathematische Beweis korrekt ist und dass ich kein Detail in der Spezifikation ¹ übersehen habe :

#include <iostream>
#include <limits>

int main() {
    std::uint64_t const MAX = std::uint64_t(1) << 32;
    for (std::uint64_t i = 0; i < MAX; ++i) {
        for (std::uint64_t j = 0; j < MAX; ++j) {
            std::uint32_t const a = static_cast<std::uint32_t>(i);
            std::uint32_t const b = static_cast<std::uint32_t>(j);

            auto const champion = (a + (b & 255)) & 255;
            auto const challenger = (a + b) & 255;

            if (champion == challenger) { continue; }

            std::cout << "a: " << a << ", b: " << b << ", champion: " << champion << ", challenger: " << challenger << "\n";
            return 1;
        }
    }

    std::cout << "Equality holds\n";
    return 0;
}

Dies listet alle möglichen Werte von aund bim 32-Bit-Raum auf und prüft, ob die Gleichheit gilt oder nicht. Wenn dies nicht der Fall ist, wird der Fall gedruckt, der nicht funktioniert hat, und der als Überprüfung der geistigen Gesundheit verwendet werden kann.

Und laut Clang : Gleichheit gilt .

Da die arithmetischen Regeln bitbreitenunabhängig sind (über der intBitbreite), gilt diese Gleichheit für jeden vorzeichenlosen Integer-Typ von 32 Bit oder mehr, einschließlich 64 Bit und 128 Bit.

Hinweis: Wie kann ein Compiler alle 64-Bit-Muster in einem angemessenen Zeitrahmen auflisten? Es kann nicht. Die Schleifen wurden optimiert. Sonst wären wir alle gestorben, bevor die Hinrichtung beendet war.

Ich habe es zunächst nur für 16-Bit-Ganzzahlen ohne Vorzeichen bewiesen. Leider ist C ++ eine verrückte Sprache, in die zuerst kleine Ganzzahlen (kleinere Bitbreiten als int) konvertiert werden int.

#include <iostream>

int main() {
    unsigned const MAX = 65536;
    for (unsigned i = 0; i < MAX; ++i) {
        for (unsigned j = 0; j < MAX; ++j) {
            std::uint16_t const a = static_cast<std::uint16_t>(i);
            std::uint16_t const b = static_cast<std::uint16_t>(j);

            auto const champion = (a + (b & 255)) & 255;
            auto const challenger = (a + b) & 255;

            if (champion == challenger) { continue; }

            std::cout << "a: " << a << ", b: " << b << ", champion: "
                      << champion << ", challenger: " << challenger << "\n";
            return 1;
        }
    }

    std::cout << "Equality holds\n";
    return 0;
}

Und noch einmal laut Clang : Gleichheit gilt .

Na siehst du :)

¹ Wenn ein Programm jemals versehentlich undefiniertes Verhalten auslöst, würde es natürlich nicht viel beweisen.

Die schnelle Antwort lautet: Beide Ausdrücke sind gleichwertig

• schon seit a und b32-Bit-Ganzzahlen ohne Vorzeichen sind, ist das Ergebnis auch im Falle eines Überlaufs dasselbe. Die vorzeichenlose Arithmetik garantiert dies: Ein Ergebnis, das nicht durch den resultierenden vorzeichenlosen Ganzzahltyp dargestellt werden kann, wird modulo um die Zahl reduziert, die eins größer ist als der größte Wert, der durch den resultierenden Typ dargestellt werden kann.

Die lange Antwort lautet: Es gibt keine bekannten Plattformen, auf denen sich diese Ausdrücke unterscheiden würden, aber der Standard garantiert dies aufgrund der Regeln der integralen Werbung nicht.

• Wenn der Typ von aund b(vorzeichenlose 32-Bit-Ganzzahlen) einen höheren Rang als hat int, wird die Berechnung als vorzeichenloses Modulo 2 ^{32 ausgeführt} und liefert für beide Ausdrücke für alle Werte von aund das gleiche definierte Ergebnis b.

• Wenn umgekehrt der Typ aund bkleiner als ist int, werden beide heraufgestuft intund die Berechnung wird unter Verwendung einer vorzeichenbehafteten Arithmetik durchgeführt, wobei ein Überlauf ein undefiniertes Verhalten hervorruft.

  • Wenn intmindestens 33 Wertbits vorhanden sind, kann keiner der oben genannten Ausdrücke überlaufen, sodass das Ergebnis perfekt definiert ist und für beide Ausdrücke den gleichen Wert hat.

  • Wenn intgenau 32 Wert Bits hat, die Berechnung kann für Überlauf beiden Ausdrücke, zum Beispiel Werten a=0xFFFFFFFFund b=1würde einen Überlauf in den beiden Ausdrücken führen. Um dies zu vermeiden, müssten Sie schreiben ((a & 255) + (b & 255)) & 255.

• Die gute Nachricht ist, dass es keine solchen Plattformen gibt ¹ .

¹ Genauer gesagt gibt es keine solche reale Plattform, aber man könnte einen DS9K so konfigurieren, dass er ein solches Verhalten aufweist und dennoch dem C-Standard entspricht.

Identisch unter der Annahme, dass kein Überlauf vorliegt . Keine der Versionen ist wirklich immun gegen Überlauf, aber die Doppel- und Version ist widerstandsfähiger dagegen. Mir ist kein System bekannt, bei dem ein Überlauf in diesem Fall ein Problem darstellt, aber ich kann sehen, dass der Autor dies tut, falls es eines gibt.

Ja, Sie können es mit Arithmetik beweisen, aber es gibt eine intuitivere Antwort.

Beim Hinzufügen beeinflusst jedes Bit nur diejenigen, die wichtiger sind als es selbst; niemals die weniger bedeutenden.

Was auch immer Sie mit den höheren Bits vor dem Hinzufügen tun, ändert daher nichts am Ergebnis, solange Sie nur Bits beibehalten, die weniger wichtig sind als das niedrigste modifizierte Bit.

Der Beweis ist trivial und als Übung für den Leser hinterlassen

Aber um dies tatsächlich als Antwort zu legitimieren, heißt es in Ihrer ersten Codezeile, nehmen Sie die letzten 8 Bits von b** (alle höheren Bits von bauf Null gesetzt) ​​und fügen Sie diese hinzua und nehmen Sie dann nur die letzten 8 Bits der Ergebnismenge, die alle höher sind Bits auf Null.

In der zweiten Zeile steht add aundb und nimm die letzten 8 Bits mit allen höheren Bits Null.

Nur die letzten 8 Bits sind im Ergebnis von Bedeutung. Daher sind nur die letzten 8 Bits in den Eingängen von Bedeutung.

** letzte 8 Bits = 8 LSB

Es ist auch interessant festzustellen, dass die Ausgabe äquivalent zu wäre

char a = something;
char b = something;
return (unsigned int)(a + b);

Wie oben sind nur die 8 LSB signifikant, aber das Ergebnis ist eine unsigned intmit allen anderen Bits Null. Der a + bWille läuft über und erzeugt das erwartete Ergebnis.