wake-up-neo.com

Warum unterscheidet sich (a% 256) von (a & 0xFF)?

Ich bin immer davon ausgegangen, dass der Optimierer bei (a % 256) natürlich eine effiziente bitweise Operation verwenden würde, als würde ich (a & 0xFF) schreiben.

Beim Testen mit dem Compiler Explorer gcc-6.2 (-O3):

// Type your code here, or load an example.
int mod(int num) {
    return num % 256;
}

mod(int):
    mov     edx, edi
    sar     edx, 31
    shr     edx, 24
    lea     eax, [rdi+rdx]
    movzx   eax, al
    sub     eax, edx
    ret

Und wenn Sie den anderen Code ausprobieren:

// Type your code here, or load an example.
int mod(int num) {
    return num & 0xFF;
}

mod(int):
    movzx   eax, dil
    ret

Es scheint, als würde mir etwas völlig fehlen ...

c++optimization
142
Elad Weiss

Es ist nicht das gleiche. Versuchen Sie num = -79, und Sie erhalten bei beiden Vorgängen unterschiedliche Ergebnisse. (-79) % 256 = -79, während (-79) & 0xff eine positive Zahl ist. 

Bei Verwendung von unsigned int sind die Operationen gleich und der Code ist wahrscheinlich derselbe. 

PS- Jemand kommentierte 

Sie sollten nicht gleich sein, a % b ist als a - b * floor (a / b) definiert.

So ist es nicht in C, C++, Objective-C definiert (dh alle Sprachen, in denen der Code in der Frage kompiliert werden würde). 

228
gnasher729

Kurze Antwort

-1 % 256 ergibt -1 und nicht 255, was -1 & 0xFF ist. Daher wäre die Optimierung falsch. 

Lange Antwort

C++ hat die Konvention (a/b)*b + a%b == a, was ziemlich natürlich erscheint. a/b gibt immer das arithmetische Ergebnis ohne den gebrochenen Teil zurück (gegen 0 abschneiden). Folglich hat a%b dasselbe Vorzeichen wie a oder ist 0. 

Die Division -1/256 ergibt 0 und daher muss -1%256-1 sein, um die obige Bedingung ((-1%256)*256 + -1%256 == -1) zu erfüllen. Dies unterscheidet sich offensichtlich von -1&0xFF, was 0xFF ist. Daher kann der Compiler nicht wie gewünscht optimieren.

Der relevante Abschnitt im C++ - Standard [expr.mul §4] ab N4606 lautet:

Bei ganzzahligen Operanden ergibt der /-Operator den algebraischen Quotienten, wobei ein Bruchteil ausrangiert wird. Wenn der Quotient a/b im Typ des Ergebnisses darstellbar ist, ist (a/b)*b + a%b gleich a [...].

Aktivierung der Optimierung

Bei mit unsigned-Typen wäre die Optimierung jedoch völlig korrekt und entspricht der obigen Konvention:

unsigned(-1)%256 == 0xFF

Siehe auch dies . 

Andere Sprachen

Dies ist in den verschiedenen Programmiersprachen sehr unterschiedlich, da Sie in Wikipedia nachschlagen können. 

54
Ralph Tandetzky

Seit C++ 11 muss num % 256 nicht positiv sein, wenn num negativ ist.

Das Bitmuster würde also von der Implementierung von vorzeichenbehafteten Typen in Ihrem System abhängen: Für ein negatives erstes Argument ist das Ergebnis nicht die Extraktion der niedrigstwertigen 8 Bits.

Anders wäre es, wenn num in Ihrem Fall unsigned wäre: heutzutage würde ich fast erwarten ein Compiler die Optimierung durchführen, die Sie zitieren.

50
Bathsheba

Ich habe keine telepathischen Einblicke in die Argumentation des Compilers, aber im Fall von % besteht die Notwendigkeit, mit negativen Werten (und Teilungsrunden gegen Null) umzugehen, während mit & immer die unteren 8 Bits erhalten werden.

Die sar-Anweisung klingt für mich wie "Shift Arithmetic Right" und füllt die leeren Bits mit dem Vorzeichenbitwert.

11
Cheers and hth. - Alf

Mathematisch wird Modulo folgendermaßen definiert:

a% b = a - b * Etage (a/b)

Dies hier sollte es für Sie klären. Für ganzzahlige Werte können Sie die Untergrenze eliminieren, da die Ganzzahleinteilung der Untergrenze (a/b) entspricht. Wenn der Compiler jedoch einen allgemeinen Trick verwendet, wie Sie vorschlagen, müsste er für alle a und alle b funktionieren. Leider ist dies einfach nicht der Fall. Mathematisch gesehen ist Ihr Trick für vorzeichenlose Ganzzahlen zu 100% korrekt (Ich sehe einen Antwortstatus, bei dem vorzeichenbehaftete Ganzzahlen gebrochen werden, aber ich kann weder bestätigen noch bestreiten, da -a% b positiv sein sollte). Kannst du diesen Trick für alle b? Wahrscheinlich nicht. Deshalb macht der Compiler das nicht. Wenn Modulo leicht als eine bitweise Operation geschrieben werden könnte, würden wir einfach eine Modulo-Schaltung hinzufügen, wie zum Addieren und für die anderen Operationen.

0
The Great Duck