Multiplicación binaria como combinación de suma y desplazamiento a la izquierda

Question

El desplazamiento a la izquierda de un número binario consiste en desplazar cada bit un lugar a la izquierda y añadir un 0 como bit menor. menos significativo. (El desplazamiento a la izquierda de 1011 es 10110.) ¿Puede la multiplicación de dos números binarios cualesquiera, por ejemplo la multiplicación de 1101 por 110001, como una combinación de sumas y desplazamientos a la izquierda?

Answer 1

Se trata básicamente de una variante del algoritmo habitual de multiplicación en lápiz y papel, realizada en base dos. Una multiplicación de lápiz y papel podría tener este aspecto:

    110001  
      1101  
    ------  
    110001  
  110001  
 110001  
----------  
1001111101

Puedes dividirlo en desplazamientos a la izquierda y sumas de la siguiente manera. Para cada $1$ en el multiplicador tendrás una copia del multiplicando desplazada a la izquierda un número de veces correspondiente a la potencia de $2$ representado por ese $1$ . Aquí, por ejemplo, los tres $1$ s en $1101$ representa $2^3,2^2$ y $2^0$ para que tengas copias de $110001$ desplazado a la izquierda $3$ , $2$ y $0$ veces. Éstas (en orden inverso) son las tres filas del producto de la multiplicación, las que están entre las dos líneas horizontales. Una vez que las tengas, simplemente suma dos de ellas, luego añade la siguiente a esa suma parcial, y sigue así hasta que termines.

Answer 2

Todo es binario, desplazamiento a la izquierda de $10101$ denotado como $l(10101) = 101010$ Obsérvese que $10*x = l(x)$ . La idea básica es dividir uno de los números y utilizar la ley distributiva. Así que tu ejemplo sería así:

\begin{eqnarray*} 1101 \cdot 110001 &=& 1101 \cdot (1 + 10000 + 100000) \\ &=& 1101 \cdot (1^0 + 10^4 + 10^5) \\ &=& 1101 \cdot 1^0 + 1101 \cdot 10^4 + 1101 \cdot 10^5 \\ &=& l^0(1101) + l^4(1101) + l^5(1101) \\ &=& 1101 + l(l(l(l(1101)))) + l(l(l(l(l(1101))))) \end{eqnarray*}