Credit image

Multiplicación: Algoritmo de Booth

¡OJO! Si no eres informático o estudiante de ingenieria computacional, probablemente este artículo no te interese.

Hace unos días necesité implementar el algoritmo de Booth en C++ para una parte de una de las prácticas de la asignatura Teoría de autómatas y lenguajes formales y la verdad, aunque existe bastante información, eché en falta una explicación didáctica para comprender el procedimiento desde un punto de partida. Asi pues, en este artículo intentaré explicar el procedimiento del algoritmo lo mejor posible.

El algoritmo de Booth es un método rápido y sencillo para obtener el producto de dos números binarios con signo en notación complemento a dos.

Debemos saber que un número binario está formado por bits de ceros y unos, y que se puede traducir a decimal fácilmente de la siguiente forma:

Sabiendo que la posición de cada bit es 2^n (elevado a n) y partimos de n=0 de derecha a izquierda, sólo queda realizar la suma total de multiplicar por dicho bit, en este caso, lo que muestro a continuación:
0·27+1·26+0·25+1·24+0·23+1·22+1·21+0·20 = 86.

También debemos saber que el complemento a uno de un número binario es cambiar sus ceros por unos, y sus unos por ceros (complementar): (010010 -> ca1: 101101) y que el complemento a dos de un número binario es el resultado de sumar 1 al complemento a uno de dicho número binario (NOTA: En el Ca1 sólo se complementa si el número es negativo):

Realizar una suma con dos números binarios es tarea fácil, pero la multiplicación resulta algo más complicada. Con el algoritmo de Booth, resulta mucho más sencillo de implementar. Partimos del ejemplo de la multiplicación 6·2=12:

Como se puede ver en la imagen superior, partiendo de los números binarios de la multiplicación 6·2 (multiplicando y multiplicador) creamos tres nuevos números binarios del doble de tamaño (16 en el ejemplo): A, S y P.

Partiendo del número P (producto) comenzamos a comparar los últimos 2 bits de la derecha, siguiendo los casos base del recuadro:

Se realizará esta comparación 8 veces en este ejemplo (número de bits de los operandos) y al final de cada comparación, realizamos un desplazamiento de un bit hacia la derecha, manteniendo el último bit de la izquierda, y descartando el último bit del lado contrario. Si hacemos una traza paso a paso nos quedarían los siguientes resultados:

Finalmente obtenemos el número en binario resultante (12 en este ejemplo), descartando el bit extra que hemos añadido al principio del procedimiento y que se encuentra en el extremo a la derecha.

Espero que esto les sirva tanto como me sirvió a mi en su momento.

Escrito por Manz, el , en ingenieria. Comentarios recibidos: 47.

47 comentarios de lectores
BraZuky
BraZuky
1

y yo que a veces que considero geek...... Que equivocado estaba.........

Shadow
Shadow
2

Muy bien pero tarde, si lo hubiese tenido el domingo

Odnei
Odnei
3

Otro modo de hacer el complemento a 2, es leyendo de derecha a izquierda el número binario, a partir del primer 1 que nos encontremos (sin incluir al propio 1), complementar todos los bits. Ejemplo: 8 en decimal (8 bits) es 00001010, el -8 en C2 sería 11110110.

ZiRRuS
ZiRRuS
4

Ufff, esto me hubiera venido bien en segundo de carrera en Sistemas Digitales. Pero hace ya unos años de eso ;) Magnífica explicación Nos vemos!

Merks
Merks
5

Oigan, esto está muy interesante, voy a aplicarlo... Saludos...

KL
KL
6

Pues me parece que yo tambien

Dite
Dite
7

Muy buena forma de explicar el algoritmo de booth, ojala mi profesor de Arquitectura de Computadoras hubiera hecho un copy paste de tu articulo jajajaj

Tania
Tania
8

UHY MUY BUERNA PAG, GRACIAS X EL TIP, ^^

Hoc
Hoc
9

vas a tener que explicarselo a Demetrio

Hoc
Hoc
10

mucho micro acólito suelto, si que hay si, el algoritmo de booth funciona mejor en Linux. Ese pingüino guaaaapo

jasmina lanzas
jasmina lanzas
11

por que no realizan un programa para calcular el complemento a dos en el lenguaje de c++

Alan
Alan
12

Estaria bien q se agregara el algoritmo correspondiente. pero ya se q pido mucho. De todas formas sta clara la idea, jejejeje.

monica
monica
13

oye muchas gracias!!! me ha sido muy util!!

uno
uno
14

¿para hacerlo en c no serviría con not(num)+1?

uno
uno
15

¿para hacerlo en c no serviría con not(num)+1?

walter
walter
16

muchas gracias

tOBY
tOBY
17

excelente explcacion, ayuda bastante sobretodo ahora que necesito realizar un circuito multiplicador de punto flotante.. Gracias

claudio
claudio
18

excelente explicación....tengo un examen, y no fui a clases, me cayo de perillas.!

Manasa
Manasa
19

odni estas confundido, el 8 en binario es 1000, pero para representarlo en complemento a 2 es necesario tener en cuenta el bit de signo (=0 indica positivo, =1 indica negativo) entonces el numero 8 seria 01000, y su complemento a dos es decir el -8 seria: 11000

vhanla
vhanla
20

El complemento a 2 de n = el complemento a 1 de n-1. Ej: 8 = 00001 000 luego para convertir mediante complemento a 2 hacemos 1. Complemento a 1 de 8 = 11110111 ( que es la negación en realidad) 2. Complemento a 2 : se le suma 1 -> 11110111+00000001 = 11111000 entonces -8 = 11111000 Otra forma de hacerlo > usamos n-1 es decir no 8 sino 7 = 00000111 1. Complemento a 1 de 7 = 11111000 entonces -8 = 11111000

luis
luis
21

oy e esta muy claro tu documento, te lo agradezco, me ha servido de mucho

Nora
Nora
22

Buen articulo.! Saludos

noe Rodriguez
noe Rodriguez
23

Hola brother sabes ese algoritmo esta excelente pero bueno nose si podrias pasarme el codigo en c++ de ese algoritmo te lo agradeceria bastante aqui te djeo mi msn crespo_168@hotmail.com te agradezco de ante mano tu apoyo bye

cristian
cristian
24

en la facu me pidieron que baje cualquier simulador de algoritmo de booth, busque en la web y no encontre nada. alguien sabe el nombre de alguno??

Juan
Juan
25

Gracias, no lo entendía, pero ahora algo entiendo. Voy a practicar un poco. Salu2.

javier cuellar
javier cuellar
26

the explication is veri good

Xpolito
Xpolito
27

Tu imagen esta bien??? 0000 0110 0000 0000 0 A 1111 1010 0000 0000 0 S 0000 0000 0000 0010 0 P [0 y 0 nada -> 0000 0000 0000 0001 0 [1 y 0] p = p + s 1111 1010 0000 0001 0 -> 0111 1101 0000 0000 1 [0 y 1] p = p + a En esa linea por que tu tienes 1111 1101 0000 0000 1 Que no tendria que ser 0 el primer bit? O por que?

aplatanado
aplatanado
28

"el algoritmo de booth funciona mejor en Linux" Jajajajajaaja, lo que tiene uno que leer.

Miguel angel
Miguel angel
29

Ayudenme Hacer Este programa en java diseñar un programa que genere el binario de cualquier numero en java

Tarxo
Tarxo
30

Muy buena explicación, por fin lo entiendo. Muchas gracias :-)

carolina
carolina
31

@noe Rodriguez: ola amigo si ya tienes el codigo para c++ pasamelo plis mi correo es lafulana_8@hot... urge

ahhhhhhhhh
ahhhhhhhhh
32

diablos no entiendo nada

lobesno
lobesno
33

WTF!??! Facil y sencilla con el algoritmo de booth?! xDD no me digas... me se el metodo pero prefiero multiplicar a la manera normal...mas rapido y mas sencillo sin tantas linias xDD... PD: ta buena la explicacion

dassa
dassa
34

sabes me sirvio mucho ......ahora ya se como exponer y dar mi clase.....ya que estudio ing. en sistemas... D: saludos >.

Santiago
Santiago
35

Gracias por toda esta informacion, me servirá mucho, esto es lo que buscaba. Estudio Ingeieria Informatica.

FANNY
FANNY
36

graziaz ezt0 me zirbi0 muxizim0 para mi tarea... eztudi0 en ing. en ziztemaz c0mputazi0nal...

MARIO CHUQUITARCO
MARIO CHUQUITARCO
37

Es buena información para los profesionales de la informática. Sigan adelante; éxitos.

racso7712
racso7712
38

muy bien explicado me sirvio para darle una asesoria a un estudiante e ingenieria en sistemas gracias!

The Cat
The Cat
39

gracias hermano..... el metodo Booth es muy ineficiente para nosotros, se que ahi varios mejores y mas rapidos pero me ayudo mucho tu informacion porque soy ingresante de sistemas y necesitaba saber como hace algunas operaciones la maquina........ graxx

anonimo
anonimo
40

ese ejercicio esta mal echo revisalo bien primero que todo el C'2 del numero dos no es ese debe de ir es 1110 no 1010 como esta hay

arista
arista
41

gracias esta chido la pgina y me encanta de echo todos mis numeros y los nombres los tengo en binarios y estudio comp. informatica.....

Stephan
Stephan
42

Porque son 8 bits los que se tienen que poner? apenas lo estoy aprendiendo :S porque si solo necesita de 4 bits se tienen que poner los 8 bits aun cuando el 6 y el 2 con signo positivo pueden representarse con solo 4 o.O? me confundo

rjcdz06
rjcdz06
43

Excelente apunte!!!. Me sirvió para implementarlo con assembler en un simulador del mhc6800. Lo había hecho hace 4 años. Como vi de nuevo este sitio no pude evitar agradecer por el apunte que en ese momento me fue de gran utilidad. Saludos. Gracias.

van
van
44

esta padre el procedimiento, pero creí que explicabas el algoritmo en c++ o para saber como imprimir la matriz con todos los pasos y si usaste colas para saber la multiplicación en los pasos. estudio ingeniería en informática,,, pero amigo quisiera saber como hacer para retroceder los números y ir eliminando los del principio, en los pasos ???? espero y me puedes ayudar claro si realmente le entiendes a lo de el código y hacer lo en un lenguaje xd yo no s^` como

roman
roman
45

amigo no tienes un video que se refiera a este tema

Alexander
Alexander
46

en verdad muchas muchas muchas gracias no sabes me salvaste la vida on!!! en verda te agradezco

alejandra
alejandra
47

hola lo que pasa que estoy estudiando ingeniera informática pero lo que pasa que tengo un problema es que estoy viendo números binarios y no les entiendo muy bien no se si me podrán ayudar plisss

Publica tu opinión

Si lo deseas, puedes utilizar el siguiente formulario para publicar tu opinión o responder a alguna de las existentes:

Previsualización

Aquí se previsualizará su comentario. Revise que sea correcto antes de publicarlo.