Pourquoi (a% 256) est-il différent de (a & 0xFF)?

J'ai toujours supposé qu'en faisant (a % 256)l'optimiseur utiliserait naturellement une opération efficace au niveau du bit, comme si j'écrivais (a & 0xFF).

Lors du test sur l'explorateur de compilateur 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

Et en essayant l'autre code:

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

mod(int):
    movzx   eax, dil
    ret

Il semble que je manque complètement quelque chose. Des idées?

Ce n'est pas la même chose. Essayez num = -79, et vous obtiendrez des résultats différents des deux opérations. (-79) % 256 = -79, tandis que (-79) & 0xffc'est un certain nombre positif.

En utilisant unsigned int, les opérations sont les mêmes et le code sera probablement le même.

PS - Quelqu'un a commenté

Ils ne devraient pas être les mêmes, a % best défini comme a - b * floor (a / b).

Ce n'est pas ainsi que cela est défini en C, C ++, Objective-C (c'est-à-dire tous les langages où le code de la question se compilerait).

Réponse courte

-1 % 256cède -1et non 255ce qui est -1 & 0xFF. Par conséquent, l'optimisation serait incorrecte.

Longue réponse

C ++ a la convention que (a/b)*b + a%b == a, ce qui semble tout à fait naturel. a/brenvoie toujours le résultat arithmétique sans la partie fractionnaire (tronquée vers 0). Par conséquent, a%ba le même signe que aou vaut 0.

La division -1/256cède 0et -1%256doit donc être -1pour satisfaire la condition ci-dessus ( (-1%256)*256 + -1%256 == -1). C'est évidemment différent de -1&0xFFce qui est 0xFF. Par conséquent, le compilateur ne peut pas optimiser comme vous le souhaitez.

La section pertinente de la norme C ++ [expr.mul §4] à partir de N4606 déclare:

Pour les opérandes intégraux, l' /opérateur donne le quotient algébrique avec toute partie fractionnaire rejetée; si le quotient a/best représentable dans le type du résultat, (a/b)*b + a%best égal à a[...].

Activer l'optimisation

Cependant, en utilisant des unsignedtypes, l'optimisation serait complètement correcte , satisfaisant la convention ci-dessus:

unsigned(-1)%256 == 0xFF

Voyez aussi ceci .

Autres langues

Ceci est géré de manière très différente selon les langages de programmation, comme vous pouvez le rechercher sur Wikipedia .

Depuis C ++ 11, num % 256doit être non positif si numest négatif.

Ainsi, le modèle de bits dépendrait de l'implémentation des types signés sur votre système: pour un premier argument négatif, le résultat n'est pas l'extraction des 8 bits les moins significatifs.

Ce serait une autre question si numdans votre cas était unsigned: ces jours-ci, je m'attendrais presque à ce qu'un compilateur fasse l'optimisation que vous citez.

Je n'ai pas d'aperçu télépathique du raisonnement du compilateur, mais dans le cas où %il y a la nécessité de traiter des valeurs négatives (et la division arrondit vers zéro), alors que &le résultat est toujours les 8 bits inférieurs.

L' sarinstruction me semble "décaler l'arithmétique vers la droite", remplissant les bits vides avec la valeur du bit de signe.

Mathématiquement parlant, modulo est défini comme suit:

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

Ce droit ici devrait éclaircir pour vous. Nous pouvons éliminer le plancher pour les nombres entiers car la division entière est équivalente au plancher (a / b). Cependant, si le compilateur devait utiliser une astuce générale comme vous le suggérez, il devrait fonctionner pour tout a et tout b. Malheureusement, ce n'est tout simplement pas le cas. Mathématiquement parlant, votre astuce est correcte à 100% pour les entiers non signés (je vois une réponse indique que les entiers signés cassent mais je peux le confirmer ou le nier car -a% b devrait être positif). Cependant, pouvez-vous faire cette astuce pour tous les b? Probablement pas. C'est pourquoi le compilateur ne le fait pas. Après tout, si modulo était facilement écrit comme une opération au niveau du bit, alors nous ajouterions simplement un circuit modulo comme pour l'addition et les autres opérations.