Otra de las operaciones aritméticas básicas que debe resolver un procesador de computadoras es la multiplicación. Este artículo explica cómo se ejecuta una multiplicación de números enteros binarios signados en dos complemento dentro de una unidad aritmético-lógica (ALU) de un procesador (CPU).

Para entender los algoritmos aquí demostrados es necesario comprender los conceptos de representación de enteros binarios en dos complemento (complemento a dos o 2's complemento), suma en dos complemento, conversión entre bases binario y decimal, desplazamientos a izquierda y derecha, extensión de signo en sistema binario, y más.



Multiplicación de enteros

Antes de mostrar el algoritmo de multiplicación de enteros en el sistema binario, es conveniente recordar cómo multiplicábamos enteros decimales en la escuela primaria. Por ejemplo, 125 * 32:

¿Qué hicimos en esta operación? Básicamente lo siguiente:

Lo que la maestra o el maestro no nos dijo en la escuela primaria, es que el guion en el segundo renglón de la multiplicación (segunda iteración) era efectivamente un shift a izquierda. Siempre se multiplica por un dígito haciendo shift para avanzar hacia posiciones más significativas y así obtener las sumas parciales correctas.

Multiplicación en binario

En binario (base 2) la multiplicación es mucho más fácil pues sólo hay dos dígitos posibles: 0 ó 1. Con lo cual no es necesario computar múltiplos del multiplicando: por cada bit (dígito binario) del multiplicador (y) se suma el multiplicando (x) o no:

La multiplicación de dos enteros binarios de n bits da como resultado un número entero binario de 2*n bits (como ocurre en cualquier base, la cantidad de dígitos del resultado requiere el doble de dígitos de los operandos):

x (n bits) * y (n bits) = x*y (2n bits)

La ALU (unidad aritmético-lógica) del procesador toma dos operandos de entrada de n bits en los registros B (mutiplicando) y MQ (multiplicador) y produce el resultado en doble extensión en los registros A y MQ, los cuales se concatenan y tienen la capacidad de corrimiento entre sí. El registro MQ es interno a la ALU y su nombre proviene de la abreviación del inglés (multiplier-quotient) ya que es usado como multiplicador en la multiplicación y como cociente en la división.

El algoritmo de multiplicación de binarios que ejecuta la ALU es idéntico al que hacíamos en la escuela al multiplicar decimales. Primero carga el multiplicador (operando a la derecha en la expresión) en el registro MQ y al multiplicando (operando a la izquierda) en el registro interno B. Inicializa el registro A en 0.

Luego ejecuta n iteraciones (siendo los registros A y B de n bits de extensión), una por cada bit del multiplicador. En cada iteración toma el bit menos significativo (LSB) de MQ; suma B en el registro A si el LSB de MQ es 1; y hace un shift a derecha de los registros A-MQ en conjunto (de esta forma se descarta el LSB de MQ y se avanza al siguiente para la próxima iteración).

En cada iteración el resultado parcial va avanzando hacia posiciones menos significativas de MQ, compartiendo el resto de los bits con el multiplicador.

Al finalizar las n iteraciones, A-MQ tienen el resultado de la multiplicación.

Multiplicación en 2's complemento

Ahora bien, cuando ambos operandos son positivos (>=0) la operación es trivial. Sin embargo, ¿qué pasa con los enteros signados en notación dos complemento (complemento a dos)? Más precisamente, ¿qué ocurre si alguno de los operandos es un entero negativo (<0)? Analicemos cada caso por separado.

(I) x*y, con x<0 e y>=0:

Como sabemos, x negativo en 2's complemento equivale a 2n - |x|. Entonces:

x => 2n - |x|
x*y = (2n - |x|)y = 2ny - |x|y

Sin embargo, el resultado correcto es el 2's complemento negativo equivalente a 22n - |x|y.

Hay dos posibilidades entonces:

  1. Corregir el resultado obtenido restando 2ny - 22n. Corresponde al 2's complemento de y corrido n bits a izquierda.
  2. Asumir a x de doble extensión (x => 22n - |x|):
    x*y = 22ny - |x|y = 22n + 22n(y - 1) - |x|y

En la segunda solución el término 22n(y - 1) es mayor a 22n, lo cual corresponde a carry de salida descartado (tal como ocurre en la suma en 2's complemento). Esto significa que el resultado es correcto. Por otro lado, al asumir a x de doble extensión, simplemente se debe extender signo, con lo cual no se requieren bits adicionales en el registro B, sino que ingresa signo en cada shift a derecha.

(II) x*y, con x>=0 e y<0:

En este caso ocurre exactamente lo mismo. Excepto que la solución 2 no se puede aplicar, ya que si se asume al multiplicador de doble extensión se requerirían el doble de iteraciones y el doble de bits en el registro MQ.

Como conclusión, cuando el multiplicando (x) es negativo simplemente se asume de doble extensión sin necesidad de hardware adicional (sólo insertar signo al hacer shift) y cuando el multiplicador (y) es negativo se deberá corregir el resultado en el último paso restando 2nx.

¿Y si ambos son negativos? En este caso se deberán aplicar ambas soluciones: insertar signo en el shift y corregir al final.

Ejemplos de multiplicación de enteros en 2's complemento

Veamos un par de ejemplos de cómo procede el algoritmo de multiplicación dentro de la ALU.

Primer ejemplo: multiplicar 7 * -3:

El dos complemento del multiplicador -3 se obtiene de la siguiente forma:

Se invierten unos y ceros y se suma uno.

Como el multiplicador es negativo, no conviene asumirlo de doble extensión, con lo cual se procede como en una multiplicación de enteros positivos normal y se corrige al final:

En el comienzo se carga el multiplicador (y) en MQ, el multiplicando (x) en B y se inicializa A con ceros.

En cada iteración se observa el LSB de MQ en color rojo. Este bit indica si hay que sumar B (1) o no (0) en el registro A. Luego se hace el shift a derecha donde ingresan siempre ceros en el bit más significativo de A, al mismo tiempo que el bit menos significativo de A pasa a ser el bit más significativo de MQ. El bit menos significativo de MQ, utilizado para determinar si se debe o no sumar B, es descartado.

En verde se observan los bits de la suma parcial, los cuales van ingresando en MQ desde posiciones más significativas en cada shift.

Luego de la última iteración, el resultado es incorrecto. Se debe corregir restando el multiplicador desplazado a izquierda n posiciones. O sea, se suma el dos complemento de x corrido 4 lugares a izquierda:

Por ende, se suma el dos complemento de 7 en A.

La siguiente animación muestra paso a paso todo el proceso tal como ocurre en la ALU con los registros A, B y MQ:

Ahora veamos un ejemplo donde el multiplicando es negativo (con lo cual es posible aplicar extensión de signo sin corregir al final): -7 * 3:

El procedimiento es idéntico, excepto que en cada shift ingresan unos en vez de ceros.

Se observa que en la segunda iteración se produce un overflow virtual luego de sumar B (el bit de signo de A cambia de 1 a 0). Sin embargo, como se asume extensión de signo, es posible ignorarlo y simplemente insertar el signo correspondiente al multiplicando (1) al hacer shift a derecha. Como el multiplicando es negativo, el signo siempre será negativo (1). Es decir, siempre ingresarán unos.

Al finalizar no es necesario corregir y el resultado es correcto.

De yapa, veamos cómo multiplicar x*y = -7 * -3, donde ambos operandos son negativos y es necesario tanto extender el signo del multiplicando como corregir en el último paso:

Referencias


Tal vez pueda interesarte


Compartí este artículo