Multiplicando dos números usando solo el operador de "turno a la izquierda"

Question

En Geeks para Geeks, me encontré con una pregunta "Añadir dos números sin utilizar operadores aritméticos", que básicamente indica que puede multiplicar dos números usando el operador de desplazamiento a la izquierda. Estoy confundido ¿que se puede lograr. Estoy tratando de entender la lógica aquí. Se establece que

Podemos resolver este problema con el operador de desplazamiento. La idea se basa en el hecho de que cada número puede ser representado en forma binaria. Y multiplicación de un número es equivalente a la multiplicación con potencias de 2. Potencias de 2 se puede obtener utilizando el operador de desplazamiento a la izquierda.

Yo no entiendo lo que los medios mencionados anteriormente. Sé que a la izquierda desplazamiento por 1 es igual que multiplicar por 2, y salió de cambio por 2 es igual que multiplicar ese número por 4. Sin embargo, estoy confundido en cómo puedo usar mayús izquierda a evaluar algo así como 7 * 3 ?

Answer 1

He mirado el enlace, pero no podía encontrar donde dice el texto que hemos citado. Independientemente, con lo que dice y por lo que estás pidiendo, es decir, la multiplicación usando el operador de desplazamiento, creo que significa que funciona sólo para la multiplicación de cada uno de los poderes de $2$ por desviación a la izquierda que el valor de la potencia. Usted puede utilizar los procedimientos y código en el enlace para añadir los números sin el uso de operadores aritméticos, pero con esto también usando XOR bit a bit y Y.

Con su ejemplo, tenga en cuenta que $7 = 2^2 + 2^1 + 2^0$ e $3 = 2^1 + 2^0$. Digamos que empezamos con $7$. Tenga en cuenta que $7 \times 3$ es $7 \times \left(2^1 + 2^0\right)$. Utilizamos la distribución de la propiedad para obtener ese $7 \times 3 = 7 \times 2^1 + 7 \times 2^0$. Para el primer término, podemos hacer un desplazamiento de izquierda por $1$ poco, el agregar esto al valor original como el segundo término ya es $7$. Como tal, obtenemos el resultado que se $\left(2^3 + 2^2 + 2^1\right) + \left(2^2 + 2^1 + 2^0\right)$, con esto en decimal ser $14 + 7 = 21$.

Alternativamente, si empezamos con $3 = 2^1 + 2^0$, usaríamos ese $7 = 2^2 + 2^1 + 2^0$ hacer las multiplicaciones y además para conseguir ese $7 \times 3 = \left(2^3 + 2^2\right) + \left(2^2 + 2^1\right) + \left(2^1 + 2^0\right) = 21$. En este caso, los términos son diferentes, y hay $3$ en lugar de $2$, pero la suma es el mismo del curso.

Answer 2

Por ejemplo, para multiplicar $7 \times 3$, escribir en binario : $$ 7 = 111 \quad; \quad 3 = 11 $$

Ahora, el punto es, imaginar haciendo multiplicación larga con estos números : $$ \requieren{encerrar} \begin{array}{} \ \ \ \ 111 \\[-3pt] \underline{\times \ \ \ 11 }\\[-3pt] \ \ \ \ 111 \\[-3pt] \underline{\ \ 1110} \\[-3pt] \underline{10101}(=21) \end{array} $$

La idea es esta : $3$ tiene queridos en tanto sus unidades y "dos" de la posición, así que cambio de $7$ por $0$, a continuación, $7$ por $1$, y sumarlos.

Ahora, imagina que estás haciendo esto para los números con muchos ceros. Por ejemplo , para : $$ 1010 = 10 \quad ; \quad 11 = 1011 $$

Entonces : $$ \requieren{encerrar} \begin{array} \ \ \ \ \ \ \ \ 1010 \\[-3pt] \underline{\ \times \ 1011} \\[-3pt] \ \ \ \ \ \ \ 1010 \\[-3pt] \ \ \ \ \ 10100 \\[-3pt] \ \ \ \color{blue}{000000} \\[-3pt] \underline{\ 1010000} \\[-3pt] \underline{\ 1101110} \end{array} $$

Lo que equivale a la adición de $1010$'s hacia la izquierda desplaza cero veces, de una sola vez y tres veces. Tenga en cuenta que estas son exactamente las posiciones en las que se $1011$ tiene un uno.

Vamos a revertir lo anterior, y de un vistazo :

$$ \requieren{encerrar} \begin{array} \ \ \ \ \ \ \ \ 1011 \\[-3pt] \underline{\ \times \ 1010} \\[-3pt] \ \ \ \ \ \ \ \color{blue}{0000} \\[-3pt] \ \ \ \ \ {10110} \\[-3pt] \ \ \ \color{blue}{000000} \\[-3pt] \underline{\ 1011000} \\[-3pt] \underline{\ 1101110} \end{array} $$

Que es equivalente a la adición de $1011$ desplazado a la izquierda exactamente una vez y tres veces, que son exactamente las posiciones en las que se $1010$ tiene un uno.

---

La anterior sugiere una estrategia para la multiplicación de números binarios $a$ e $b$ :

• Encontrar las posiciones en las que se $b$ tiene un uno. Llamar a estas posiciones $p_1,p_2,...,p_n$.

• Considerar los números binarios formados por la izquierda desplazamiento de $a$ por $p_1, p_2,..,p_n$.

• Agregar todos estos números, para obtener la respuesta.

---

Tenga en cuenta que esto no implica "duro" de la multiplicación, debido a que el desplazamiento a la izquierda es técnicamente multiplicación por potencias de $2$ pero (como para las potencias de $10$ en el decimal caso) se realiza fácilmente, y estamos reducidos a la más fácil de la operación de la suma de la izquierda turnos.

Esta técnica a menudo aparece en los libros que cubren la rápida multiplicación de las técnicas, especialmente por los números que están cerca de los poderes de $2$.

---

EDIT: Para Vakil s $20 \times 13$, en primer lugar se escribieron lo que él hace, entonces, ¿cómo se obtiene la respuesta : $$ \begin{array}{rrr} 0 && 20 && 13 \\ 1 && 40 && 6 \\ 2 && 80 && 3 \\ 3 && 160 && 1 \\[1pt] \end{array} $$

Luego añade, $160+80+20 = 260$, la respuesta correcta.

En el procedimiento , esto es lo que está sucediendo :

• En la primera línea se escribe el dos números y, a continuación, indicar como número de fila cero.

• A continuación, en la siguiente fila se duplica el número en la segunda entrada, dividir la tercera entrada por $2$ y redondee hacia abajo , y se indica como número de fila $1$.

• Hacemos esto hasta llegar a $1$ como la tercera entrada de algunos de fila.

• Ahora, en la segunda columna, la de recoger todas las entradas de manera que los correspondientes tercera entrada es impar. Por eso escogimos $160$ porque $1$ es impar, se recogen $80$ porque $3$ es impar, no coger $40$ como $6$ es incluso y recogió $20$ como $13$ es impar.

• Agregar las entradas para obtener la respuesta.

¿Cómo funciona esto? Vamos a escribir los mismos números que están arriba en el sistema binario para ver lo que está sucediendo : $$ \begin{array}{rrr} 0 && 10100 && 1101 \\ 1 && 101000 && 110 \\ 2 && 1010000 && 11 \\ 3 && 10100000 && 1 \\[1pt] \end{array} $$

Añadimos $10100$ porque $1101$ termina con $1$. Añadimos $1010000$ porque $11$ termina con $1$. Añadimos $10100000$ porque $1$ termina con $1$. Nosotros no añada $101000$ porque $110$ termina con $0$.

Ahora es bastante obvio que este algoritmo viene a nuestro rescate. La "división por dos" paso no es sino "la eliminación de la última bits" en binario. Ahora, nos centramos en el último bit del nuevo número, y si este es $1$ le sumamos que la entrada en la segunda fila, de lo contrario lo dejamos. De nuevo tenemos que dividir por $2$, eliminando así el último bit, etc.

Creo que desde aquí usted puede averiguar cómo funciona el algoritmo, y cómo se corresponde a lo que escribí anteriormente.