Y a-t-il un algorithme cool avec des opérations de bits sages?
6 Réponses :
Souvent, les opérations de module et de division sur un processeur sont la même chose. Par exemple, reportez-vous à la section http://jsimlo.sk/docs/cpu/index. php / div.html . C'est la mise en œuvre de l'instruction de division sur les processeurs Intel.
La plupart du temps, le module est juste calculé en divisant les deux nombres. Le quotient est stocké dans un seul registre et le reste est stocké dans l'autre registre. Vous iriez après le reste.
x mod y = x - y * (x / y)
où (x / y) est une division entier.
En dehors de la méthode évidente utilisant div et idiovis (pour x86) comme mentionné ci-dessus, le résultat de tout numéro modulo'd par une puissance de deux peut être calculé En prenant le bitwise et: x mod y où y est pow2 est identique à celui x et (y-1) . La plupart des compilateurs effectuent cela lorsque cela est possible, car la division est beaucoup plus chère que les ops bitwise
Si le diviseur est connu à l'avance (par exemple, pour le code produit par un compilateur C, il s'agit d'une constante connue au moment de la compilation) puis de la division entier (à partir duquel le module peut être facilement obtenu) peut parfois être mis en œuvre avec une multiplication et un changement. Voir Cet article pour plus de détails (avertissement : Ce n'est pas une lecture légère).
Dans de nombreux processeurs, la multiplication entière est considérablement plus rapide que la division entière; Certains processeurs n'ont même pas de solution de division entière (multiplication sur les valeurs n --bit peuvent être optimisés dans un circuit de profondeur o (journal n) , alors qu'il n'y a pas de connu Méthode pour optimiser un circuit de division sous une profondeur de o (n) ).
Pourquoi GCC utilise-t-il la multiplication par un nombre étrange dans la mise en œuvre de la division entière? explique comment le fonctionnement multiplicatif de point fixe fonctionne, dans une solution facile à -undstand Way.
Vérification également du modulo 2 est facile, car il n'a besoin que de vérifier le bit le moins significatif, généralement.
citant wikipedia:
Pour des cas spéciaux, sur une substance supérieure, des alternatives plus rapides existent. Par exemple, le module de pouvoirs de 2 peut être alternativement exprimé sous forme de sens et de fonctionnement:
x% 2n == x & (2n-1)
Exemples (en supposant que X est un entier positif):
x% 2 == x & 1
x% 4 == x & 3
x% 8 == x & 7
Dans les périphériques et les logiciels qui implémentent des opérations binaire plus efficacement que Modulo, ces formulaires alternatifs peuvent entraîner des calculs plus rapides.
Être que vous notez que vous notez l'assemblage, on dirait que vous voulez le savoir à un niveau très bas, pas quelque chose pour
x mod y similaire 'Sustractez à plusieurs reprises Y de x jusqu'à ce que le résultat soit inférieur à celui de Y'? Me rappelle d'écrire des routines Mul / div dans un cours d'assemblage et être étonné de la durée pendant laquelle ils devaient êtreCORRECT, je me demande s'il y a une manière intelligente à bas niveau que cela se fait mieux que O (n) temps.
Je ne sais pas ce que fait le matériel, mais dans la plupart des ensembles d'instructions
modulus etdivision sont effectués à l'aide de la même instruction. L'instruction Division est mise en œuvre de telle sorte que le quotient soit émis sur un registre et le reste de la sortie simultanée à un second registre.@Aroth - C'est familier maintenant que vous le mentionnez. Suivre un hunch - peut-être pour
x / y x est mis en un registre à partir de laquelle y est soustrait à plusieurs reprises. À chaque soustraction, un autre registre est incrémenté. Ces deux registres sont le quotient et le resteVoir: Stackoverflow.com/Questtions/5189631/... .