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

Question

J'ai toujours supposé que lors de l'exécution de (a % 256) l'optimiseur utiliserait naturellement une opération binaire efficace, comme si j'avais écrit (a & 0xFF) .

Lors des tests sur l'explorateur du 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
 

On dirait que je manque complètement quelque chose. Des idées?

Answer 1

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

À l'aide de unsigned int, les opérations sont les mêmes, et le code sera probablement la même.

PS Quelqu'un a commenté

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

Ce n'est pas la façon dont il est défini en C, C++, Objective-C (c'est à dire toutes les langues où le code à la question de la compilation).

Answer 2

Réponse courte

-1 % 256 rendements en -1 et pas 255 qui -1 & 0xFF. Par conséquent, l'optimisation serait incorrect.

Réponse longue

C++ a la convention qu' (a/b)*b + a%b == a, ce qui semble tout à fait naturel. a/b renvoie toujours l'arithmétique résultat sans la partie fractionnaire (troncature vers 0). En conséquence, a%b a le même signe que a ou est de 0.

La division de l' -1/256 rendements en 0 et, par conséquent -1%256 doit -1 afin de satisfaire à la condition énoncée ci-dessus ((-1%256)*256 + -1%256 == -1). C'est évidemment différent de -1&0xFF qui 0xFF. Par conséquent, le compilateur ne peut pas optimiser la façon dont vous le souhaitez.

La section appropriée dans le standard C++ [expr.mul §4] que de N4606 états:

Intégrale de la opérandes l' / opérateur rendements algébrique quotient avec toute partie fractionnaire jeté; si le quotient a/b est représentable dans le type du résultat, (a/b)*b + a%b est égal à a [...].

L'activation de l'optimisation

Cependant, à l'aide de unsigned types, l'optimisation serait tout à fait correct, satisfaisant à la convention susmentionnée:

unsigned(-1)%256 == 0xFF

Voir aussi cette.

D'autres langues

Ce traitement est très différent dans différents langages de programmation que vous pouvez regarder sur Wikipedia.

Answer 3

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

Le modèle de bits dépend donc de la mise en œuvre 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 différent si num dans votre cas était unsigned : ces jours-ci, je m'attendrais presque à ce qu'un compilateur fasse l'optimisation que vous citez.

Answer 4

Je n'ai pas de compréhension télépathique du raisonnement du compilateur, mais dans le cas de % il est nécessaire de traiter les valeurs négatives (et les divisions autour de zéro), tandis que avec & le résultat est toujours les 8 bits les plus bas.

L'instruction sar me semble être une "modification arithmétique correcte", remplissant les bits vides avec la valeur du bit de signe.

Answer 5

Mathématiquement parlant, le modulo est le suivant:

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

Ce droit devrait clarifier les choses pour vous. Nous pouvons éliminer étage pour les entiers parce que la division entière est équivalent à l'étage(a/b). Toutefois, si le compilateur a été d'utiliser un truc comme vous le suggérez, il serait nécessaire de travailler pour tout a et tout b. Malheureusement, ce n'est tout simplement pas le cas. Mathématiquement parlant, votre truc, c'est 100% de réponses correctes pour les entiers non signés (j'voir la réponse des états entiers signés casser, mais je peux vous confirmer ni infirmer ce que -a % b doit être positif). Cependant, pouvez-vous faire ce truc pour tout b? Probablement pas. C'est pourquoi le compilateur ne pas le faire. Après tout, si modulo ont été facilement écrite comme une opération au niveau du bit, alors il nous faudrait juste ajouter un modulo circuit comme pour l'addition et le autres opérations.