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

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

Beim Testen auf 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

Scheint, als würde mir etwas völlig fehlen. Irgendwelche Ideen?

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

Bei Verwendung unsigned intsind die Vorgänge identisch, und der Code ist wahrscheinlich identisch.

PS: Jemand hat kommentiert

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

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

Kurze Antwort

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

Lange Antwort

C ++ hat die Konvention (a/b)*b + a%b == a, die ganz natürlich erscheint. a/bGibt immer das arithmetische Ergebnis ohne den Bruchteil zurück (Abschneiden in Richtung 0). Infolgedessen a%bhat das gleiche Vorzeichen wie aoder ist 0.

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

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

Für integrale Operanden /liefert der Operator den algebraischen Quotienten, wobei jeder gebrochene Teil verworfen wird. Wenn der Quotient a/bin der Art des Ergebnisses darstellbar ist, (a/b)*b + a%bist er gleich a[...].

Optimierung aktivieren

Bei Verwendung von unsignedTypen wäre die Optimierung jedoch vollständig korrekt und würde die obige Konvention erfüllen:

unsigned(-1)%256 == 0xFF

Siehe auch dies .

Andere Sprachen

Dies wird in verschiedenen Programmiersprachen sehr unterschiedlich gehandhabt, da Sie auf Wikipedia nachschlagen können .

Da C ++ 11, num % 256muss nicht positiv sein, wenn numnegativ ist.

Das Bitmuster hängt also von der Implementierung vorzeichenbehafteter Typen auf Ihrem System ab: Bei einem negativen ersten Argument ist das Ergebnis nicht die Extraktion der niedrigstwertigen 8 Bits.

numIn Ihrem Fall wäre es eine andere Sache unsigned: Heutzutage würde ich fast erwarten, dass ein Compiler die von Ihnen zitierte Optimierung vornimmt.

Ich habe keinen telepathischen Einblick in die Argumentation des Compilers, aber im Fall von %besteht die Notwendigkeit, mit negativen Werten umzugehen (und Divisionsrunden gegen Null), während &das Ergebnis immer die unteren 8 Bits sind.

Der sarBefehl klingt für mich wie "Arithmetik nach rechts verschieben" und füllt die frei gewordenen Bits mit dem Vorzeichenbitwert.

Mathematisch gesehen ist Modulo wie folgt definiert:

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

Dies hier sollte es für Sie klären. Wir können Floor für Ganzzahlen eliminieren, da die Ganzzahldivision dem Floor (a / b) entspricht. Wenn der Compiler jedoch einen allgemeinen Trick verwenden würde, wie Sie ihn vorschlagen, müsste er für alle a und alle b funktionieren. Dies ist leider nicht der Fall. Mathematisch gesehen ist Ihr Trick für vorzeichenlose Ganzzahlen zu 100% korrekt (ich sehe eine Antwort, dass vorzeichenbehaftete Ganzzahlen brechen, aber ich kann dies bestätigen oder leugnen, da -a% b positiv sein sollte). Können Sie diesen Trick jedoch für alle b machen? 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 wie für die Addition und die anderen Operationen hinzufügen.