¿Cómo puedo multiplicar y dividir usando solo el desplazamiento y la suma de bits?
¿Cómo puedo multiplicar y dividir usando solo el desplazamiento y la suma de bits?
Para multiplicar en términos de suma y desplazamiento, debes descomponer uno de los números en potencias de dos, así:
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)
( _2significa base 2)
Como puede ver, la multiplicación se puede descomponer en suma y desplazamiento y viceversa. Esta es también la razón por la que la multiplicación lleva más tiempo que los cambios de bits o la suma: es O(n^2) en lugar de O(n) en el número de bits. Los sistemas informáticos reales (a diferencia de los sistemas informáticos teóricos) tienen un número finito de bits, por lo que la multiplicación requiere un múltiplo constante de tiempo en comparación con la suma y el desplazamiento. Si no recuerdo mal, los procesadores modernos, si se canalizan correctamente, pueden realizar multiplicaciones casi tan rápido como sumas, alterando la utilización de las ALU (unidades aritméticas) en el procesador.
La respuesta de Andrew Toulouse puede extenderse a la división.
La división por constantes enteras se analiza en detalle en el libro "Hacker's Delight" de Henry S. Warren (ISBN 9780201914658).
La primera idea para implementar la división es escribir el valor inverso del denominador en base dos.
P.ej,
1/3 = (base-2) 0.0101 0101 0101 0101 0101 0101 0101 0101 .....
Entonces,
a/3 = (a >> 2) + (a >> 4) + (a >> 6) + ... + (a >> 30)
para la aritmética de 32 bits.
Combinando los términos de forma obvia podemos reducir el número de operaciones:
b = (a >> 2) + (a >> 4)
b += (b >> 4)
b += (b >> 8)
b += (b >> 16)
Hay formas más interesantes de calcular la división y el resto.
EDITAR1:
Si el OP significa multiplicación y división de números arbitrarios, no división por un número constante, entonces este hilo podría ser útil: https://stackoverflow.com/a/12699549/1182653
EDITAR2:
Una de las formas más rápidas de dividir por constantes enteras es aprovechar la aritmética modular y la reducción de Montgomery: ¿Cuál es la forma más rápida de dividir un número entero entre 3?
X * 2 = desplazamiento de 1 bit a la izquierda
X / 2 = desplazamiento de 1 bit a la derecha
X * 3 = desplazamiento de 1 bit a la izquierda y luego agregar X
