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


Das habe ich immer vorausgesetzt (a % 256) der Optimierer würde natürlich eine effiziente bitweise Operation verwenden, so als ob ich geschrieben hätte (a & 0xFF).

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 du den anderen Code ausprobierst:

// 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 ich etwas völlig vermissen. Irgendwelche Ideen?


138
2017-11-08 09:29


Ursprung


Antworten:


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

Verwenden unsigned int, die Operationen sind die gleichen, und der Code wird wahrscheinlich der gleiche sein.

PS- Jemand hat kommentiert

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

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


226
2017-11-08 09:33



Kurze Antwort

-1 % 256 Erträge -1 und nicht 255 welches ist -1 & 0xFF. Daher wäre die Optimierung falsch.

Lange Antwort

C ++ hat die Konvention, dass (a/b)*b + a%b == aDas scheint ziemlich natürlich zu sein. a/b gibt immer das arithmetische Ergebnis ohne den Bruchteil zurück (abschneiden gegen 0). Als Konsequenz, a%b hat das gleiche Zeichen wie a oder ist 0.

Der Unternehmensbereich -1/256 Erträge 0 und daher -1%256 muss sein -1 um die obige Bedingung zu erfüllen ((-1%256)*256 + -1%256 == -1). Dies ist offensichtlich anders als -1&0xFF welches ist 0xFF. Daher kann der Compiler nicht optimieren, wie Sie möchten.

Der relevante Abschnitt in der C ++ Standard [expr.mul §4] ab N4606 Zustände:

Für ganzzahlige Operanden gilt das / Operator liefert den algebraischen Quotienten, wobei jeder gebrochene Teil verworfen wird; wenn der Quotient a/b ist in der Art des Ergebnisses darstellbar, (a/b)*b + a%b entspricht a [...].

Aktivieren der Optimierung

Jedoch, verwenden unsigned Typen wäre die Optimierung völlig korrekt, die obige Konvention erfüllend:

unsigned(-1)%256 == 0xFF

Siehe auch Dies.

Andere Sprachen

Dies wird über verschiedene Programmiersprachen hinweg sehr unterschiedlich gehandhabt, wie Sie nachsehen können Wikipedia.


53
2017-11-08 15:41



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

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

Es wäre eine andere Sache, wenn num in deinem Fall war unsigned: In diesen Tagen würde ich fast erwarten von ein Compiler, um die von Ihnen angegebene Optimierung vorzunehmen.


50
2017-11-08 09:30



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

Das sar Der Befehl klingt für mich wie "Rechtes Rechnen" und füllt die leeren Bits mit dem Vorzeichenbitwert auf.


11
2017-11-08 09:33



Mathematisch wird Modulo folgendermaßen definiert:

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

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


0
2017-11-09 15:58