« Les opérations bit à bit/Les débordements de puissance de deux » : différence entre les versions
Contenu supprimé Contenu ajouté
m Bot: Mise à jour des codes texvc par des équivalentes LaTeX (documentation) |
|||
Ligne 13 :
Par définition, le modulo d'un nombre va prendre le reste de la division par un entier. Si calcule le reste modulo <math>2^x</math>, cela veut dire qu'on doit supprimer tous les multiples de <math>2^x</math> dans l'écriture binaire de notre nombre., en les mettant à zéro. En clair : pour obtenir le modulo, on doit mettre à zéro les n bits les plus à droite dans l'écriture binaire de notre nombre. Cette mise à zéro se fait en utilisant une opération ET, avec la constante égale à <math>2^n - 1</math>.
<math> x \% 2^n = x . (2^n - 1)</math>
[[File:Modulo et quotient d'une division par une puissance de deux en binaire.png|centre|vignette|upright=2.0|Modulo et quotient d'une division par une puissance de deux en binaire.]]
Ligne 93 :
===Méthode sans débordement d'entier===
Pour cela, il existe deux solutions différentes, la première étant plus simple à comprendre que l'autre. La première demande se base sur le fait que l'adresse <math>A</math> peut-être ou non un nombre divisible par la puissance de deux concernée. En clair, on sait que c'est un nombre de la forme <math>A = n \times 2^n + r_0</math>. Un débordement a lieu si, en ajoutant <math>L</math>, on passe au multiple suivant. En clair, un débordement a lieu si <math>A + L = (n + 1) \times 2^n + r_2</math>. En faisant quelques manipulations algébriques (soustraire A des deux cotés), cette condition se traduit alors en : <math>L + r_0 > 2^n</math>. La logique est simple : si la longueur dépasse ce qu'il manque à l'adresse pour atteindre le prochain multiple de <math>2^n</math>, alors l'adresse dépassera cette puissance : c'est un débordement. On peut alors faire le calcul assez simplement, vu que le reste <math>r_0 = A \% 2^n</math>. Le calcul total est le suivant :
<math>(A \% 2^n) + L >= 2^n</math>
On peut alors utiliser la méthode pour calculer le modulo par la puissance de deux :
Ligne 103 :
===Méthode avec débordement d'entier===
Une seconde méthode effectue un calcul similaire, si ce n'est qu'il arrive à remplacer la comparaison par un débordement d'entier. Le principe est très simple et se contente de remplacer l'adresse par le multiple de <math>2^n</math> le plus grand possible qui soit adressable. Prenons par exemple une mémoire de 2^32 adresses, adressée par des adresses de 32 bits, découpée en page de 4096 octets. On suppose aussi que la machine travaille sur les mots/registres de 32 bits, comme les adresses. L'adresse la plus élevée, <math>2^{32} - 1</math>, n'est pas un multiple de 4096. L'adresse la plus grande multiple de 4096 est de 4294963200. Si à cette adresse on ajoute <math>L + A \% 2^n</math>, un débordement se produit si <math>L + A \% 2^n > 4096</math>. En clair, le débordement d'entier traduit un débordement de page. On détecte donc un débordement de page si :
<math>4294963200 + L + (A \% 2^n) > 2^{32}</math>
Il se trouve que le calcul de <math>4294963200 + (A \% 2^n)</math> peut se réaliser sans faire l'addition. Tout ce qu'il faut faire est de remplacer les bits de poids forts de l'adresse par des 1, sans toucher aux bits sélectionnés par le modulo. L'application d'un masque est alors obligatoire, ce qui donne le code suivant :
<math>(A | 4294963200) + L > 2^{32}</math>
| |||