Comment puis-je multiplier et diviser en n'utilisant que le transfert et l'ajout de bits?

Question

Comment puis-je multiplier et diviser en n'utilisant que le transfert et l'ajout de bits?

Answer 1

Pour multiplier en termes d'ajouter et de déplacement que vous souhaitez décomposer les nombres par des puissances de deux, comme ceci:

21 * 5 = 10101_2 * 101_2             (Initial step)
       = 10101_2 * (1 * 2^2  +  0 * 2^1  +  1 * 2^0)
       = 10101_2 * 2^2 + 10101_2 * 2^0 
       = 10101_2 << 2 + 10101_2 << 0 (Decomposed)
       = 10101_2 * 4 + 10101_2 * 1
       = 10101_2 * 5
       = 21 * 5                      (Same as initial expression)

(_2 moyen de la base 2)

Comme vous pouvez le voir, la multiplication peut être décomposé en ajoutant des et de déplacement et de retour à nouveau. C'est aussi pourquoi la multiplication prend plus de temps que peu de postes ou l'ajout d' - il est O(n^2) plutôt que de O(n) le nombre de bits. Réel des systèmes informatiques (par opposition à la théorie des systèmes informatiques) ont un nombre fini de bits, de sorte que la multiplication prend une constante multiples de temps par rapport à l'addition et de déplacement. Si je me souviens bien, les processeurs modernes, si canalisée correctement, peut faire une multiplication à peu près aussi rapide que l'addition, par interférence avec l'utilisation de l'Utm (arithmétique unités) dans le processeur.

Answer 2

La réponse d'Andrew Toulouse peut être étendu à la division.

La division par des constantes entières est examiné en détail dans le livre "Hacker s Delight" par Henry S. Warren (ISBN 9780201914658).

La première idée de la mise en œuvre de la division est d'écrire l'inverse de la valeur du dénominateur dans la base de deux.

E. g., 1/3 = (base-2) 0.0101 0101 0101 0101 0101 0101 0101 0101 .....

Donc, a/3 = (a >> 2) + (a >> 4) + (a >> 6) + ... + (a >> 30) pour les 32 bits de l'arithmétique.

En combinant les termes d'une façon évidente, nous pouvons réduire le nombre d'opérations:

b = (a >> 2) + (a >> 4)

b += (b >> 4)

b += (b >> 8)

b += (b >> 16)

Il y a de plus excitant façons de calculer la division et les restes.

EDIT1:

Si l'OP moyens de multiplication et de division d'un nombre arbitraire, pas la division par un nombre constant, alors ce fil pourrait être utile: http://stackoverflow.com/a/12699549/1182653

EDIT2:

L'un des moyens les plus rapides pour diviser par des constantes entières est d'exploiter l'arithmétique modulaire et Montgomery réduction: Quel est le moyen le plus rapide pour diviser un nombre entier par 3?

Answer 3

X * 2 = décalage de 1 bit à gauche
X / 2 = décalage de 1 bit à droite
X * 3 = décaler à gauche de 1 bit puis ajouter X

Answer 4

x << k == x multiplied by 2 to the power of k
x >> k == x divided by 2 to the power of k

Vous pouvez utiliser ces décalages pour effectuer n'importe quelle opération de multiplication. Par exemple:

x * 14 == x * 16 - x * 2 == (x << 4) - (x << 1)
x * 12 == x * 8 + x * 4 == (x << 3) + (x << 2)

Pour diviser un nombre par un non-pouvoir de deux, je ne connais aucun moyen simple, sauf si vous souhaitez implémenter une logique de bas niveau, utiliser d'autres opérations binaires et utiliser une certaine forme d'itération.

Answer 5

1. Un décalage à gauche par 1 équivaut à une multiplication par 2. Un décalage à droite équivaut à une division par 2.
2. Vous pouvez ajouter une boucle pour se multiplier. En choisissant correctement la variable de boucle et la variable d’ajout, vous pouvez lier les performances. Une fois que vous avez exploré cela, vous devriez utiliser la multiplication paysanne