2009-10-12 20 views
3

Je me demandais s'il y avait un moyen efficace d'effectuer un décalage à droite sur une valeur binaire 8 bits en utilisant seulement ALU opérateurs (NOT, OR, AND, XOR, ADD, SUB)Un poste de barillet droit en utilisant les opérateurs ALU?

Example: 

input: 00110101 
output: 10011010 

Je suis en mesure pour mettre en œuvre un décalage laissé en ajoutant simplement la valeur binaire de 8 bits avec lui-même, car un décalage à gauche équivaut à multiplier par 2. Cependant, je ne peux pas penser à un moyen de faire cela pour le décalage à droite.

La seule méthode que j'ai trouvée jusqu'ici est d'effectuer seulement 7 changements de baril gauche. Est-ce le seul moyen?

+0

probablement vous voulez * rotation *. La rotation est différente du décalage. –

+0

Yah, ça s'appelle * tourne bien *, pas * shift *. – DigitalRoss

+0

L'implémentation shift-left est un vrai changement, car elle se décale en 0 et rejette (déborde) le bit supérieur. – MSalters

Répondre

2

Il est trivial de voir que cela ne peut pas être fait avec {AND, OR, XOR, NOT}. Pour tous ces opérateurs, l'outbit [N] dépend de inbit1 [N] et d'inbit2 [N] seulement. ET ajoute une dépendance sur inbit1 [N] .. inbit1 [0] et inbit2 [N] .. inbit2 [0]. Cependant, dans votre cas, vous avez besoin d'une dépendance sur l'inbit [N + 1]. Par conséquent, il s'ensuit que s'il y a une solution, elle doit inclure un SUB.

Cependant, A - B est juste A + (-B) qui est A + ((B XOR 11111111) +1). Par conséquent, s'il existait une solution utilisant SUB, elle pourrait être réécrite comme une solution utilisant ADD et XOR à la place. Comme nous l'avons montré, ces opérateurs sont insuffisants. Par conséquent, l'ensemble {ADD, OR, XOR, NOT, ADD, SUB} est également insuffisant.

+0

c'est ce que je pensais. Je pensais qu'il y avait peut-être une sorte de masque qui pourrait être utilisé et ensuite manipulé. C'est juste que quand je travaillais avec l'assemblage MIPS, le livre prétendait pouvoir diviser (si c'est une puissance de deux) en 1 cycle d'horloge. Je pense que c'est peut-être à cause d'un shifter de matériel. Merci pour l'entrée. – Tomek

+0

Les shifters de barillet de matériel sont assez communs, et pas trop complexe (apparemment). – MSalters