Cómo hacer multiplicación bit a bit

Supongo que por “bit-wise” te refieres a “base 2”.

También supongo que está pensando en cómo extender la precisión de una computadora más allá de lo que esté integrado.

Finalmente, consideraremos solo números positivos.

Para simplificar, asumimos que hay un tipo de datos disponible en C en su entorno favorito llamado NIBBLE que representa números del o al 15 (decimal), es decir, 8 bits.

También asumimos que su computadora (o su calculadora manual en modo “programador”) puede multiplicar 2 NIBBLES para obtener un valor de 2 NIBBLES (1 BYTE). También suponemos que tiene una forma de agregar valores BYTE de forma nativa. En un paquete de multiprecisión, estos probablemente se escalarían a valores de 32 bits y 64 bits, respectivamente. Una cosa a entender es que cuando trabajamos, por ejemplo, en C o C ++ o C #, es extremadamente importante usar valores sin signo.

Así que echemos un vistazo a la multiplicación de algunos valores de 4 nibbles para obtener un resultado de 8 nibbles.

X = 1 2 3 4

Y = 5 6 7 8

Z = Producto de X e Y = 06260060

Procedemos de esta manera

  1. 4 * 8 = 20 (hexadecimal) y entonces 0 es el dígito menos significativo del producto, y llevamos 2 al siguiente paso
  2. Segundo dígito del producto: 2 + 3 * 8 + 4 * 7 = 36 (hexadecimal). Publicar 6, llevar 3
  3. Tercer dígito: 3 + 2 * 8 + 3 * 7 + 4 * 6 = 40. Post 0 carry 4
  4. Cuarto dígito: 4 + 1 * 8 + 2 * 7 + 3 * 6 + 4 * 5 = 40. Publicar 0 llevar 4
  5. Quinto dígito: 4 + 1 * 7 + 2 * 6 + 3 * 5 = 26. Puesto 6 llevar 2
  6. Sexto dígito: 2 + 1 * 6 + 2 * 5 = 12. Puesto 2 Llevar 1
  7. Séptimo dígito: 1 + 1 * 5 = 6. Puesto 6 Llevar 0
  8. Octavo dígito: Llevar desde el paso anterior = 0

La clave es separar un valor de dos unidades en un dígito publicado y un carry para el siguiente paso.

Podemos hacer lo mismo solo con operaciones bit a bit, que pueden ser lo que quieres decir

Para el mismo ejemplo, exprese X e Y como números de 16 bits

X = 0001 0010 0011 0100

Y = 0101 0110 0111 1000

Paso 1: Agregue 16 0 bits a X

El producto P comienza con 32 bits, todos 0

0000 0000 0000 0000 0000 0000 0000 0000

Establecer índice = 0

Establecer X2 = copia de doble ancho de X (agregar 16 bits altos)

Para índice de 0 a 15

hacer

si el índice de bits de Y = 1, entonces agregue X2 a P

Shift X2 dejó 1 bit

hecho

En el caso que nos ocupa, el primer bit de Y que no es cero es el bit 3 (la cuarta interacción del bucle que comienza en 0), por lo que se agrega X << 3 al producto.

En resumen, Y tiene los siguientes bits distintos de cero: 14,12,10,9,6,5,4,3, y así

P = X2 << 14 + X2 << 12 + X2 << 9 + X2 << 6 + X2 << 5 + X2 << 4 + X2 << 3

¿Cómo se hace la multiplicación bit a bit?

Escribe los números y los multiplica de la misma manera que multiplicaría los números decimales. No estoy bromeando. Es completamente simple.

De hecho, es mucho, mucho más fácil que multiplicar números decimales, porque toda la tabla de multiplicar tiene solo 4 hechos, y 3 de ellos son 0: 0 x 0 = 0, 1 x 0 = 0, 0 x 1 = 0, 1 x 1 = 1.

Entonces, digamos que desea multiplicar 111 (7 en decimal) por 111 (7 en decimal nuevamente). Tenga en cuenta que elegí algo que es corto, pero que es más complicado que la mayoría de las cosas, porque habrá mucho transporte.

Escríbelos uno debajo del otro y multiplica:

111
x 111
——-
111
111
111
———

Luego solo agrégalos. Recuerde que 1 + 1 = 0 lleva el 1. 1 + 1 + 1 = 1 lleva el 1. 1 + 1 + 1 + 1 = 0 lleva el 10 (porque 2 se escribe como 10 en binario):

110001

Ahí está la respuesta. Vamos a verlo

Es un 1 en el lugar del 1, 0 en el lugar de los 2, 4 y 8, 1 en el lugar de los 16, 1 en el lugar de los 32. Suma los valores con un 1 juntos: 1 + 16 + 32 = 49. Eso es 7 x 7. Listo.