Destacados

Más
Viernes, 27 de octubre, 2006

Multiplicación: Algoritmo de Booth

47 +100K
Publicidad

¡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.

Comparte este artículo
Sobre el autor de Emezeta

Escrito por , más conocido como Manz. Es Ingeniero-Técnico en Informática de Gestión por la Universidad de La Laguna y residente en Santa Cruz de Tenerife.

47 comentarios de lectores
BraZuky BraZuky Viernes, 27 de octubre de 2006, 22:15
1
y yo que a veces que considero geek...... Que equivocado estaba.........
Responder Permalink URL · Mozilla Firefox 2.0 · Windows XP ·
Shadow Shadow Viernes, 27 de octubre de 2006, 22:33
2
Muy bien pero tarde, si lo hubiese tenido el domingo
Responder Permalink Mozilla Firefox 1.5.0.7 · Windows XP ·
Odnei Odnei Sábado, 28 de octubre de 2006, 02:21
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.
Responder Permalink URL · Mozilla Firefox 1.5.0.7 · Windows XP ·
ZiRRuS ZiRRuS Sábado, 28 de octubre de 2006, 14:08
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!
Responder Permalink URL · Mozilla Firefox 2.0 · Windows XP ·
Merks Merks Sábado, 28 de octubre de 2006, 19:27
5
Oigan, esto está muy interesante, voy a aplicarlo... Saludos...
Responder Permalink URL · Internet Explorer 6.0 · Windows XP ·
KL KL Jueves, 9 de noviembre de 2006, 08:15
6
Pues me parece que yo tambien
Responder Permalink URL · Mozilla Firefox 2.0 · Windows XP ·
Dite Domingo, 19 de noviembre de 2006, 23:53
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
Responder Permalink Internet Explorer 6.0 · Windows XP ·
Tania Tania Miércoles, 10 de enero de 2007, 00:50
8
UHY MUY BUERNA PAG, GRACIAS X EL TIP, ^^
Responder Permalink Mozilla Firefox 1.5.0.9 · Windows XP ·
Hoc Jueves, 1 de febrero de 2007, 16:55
9
vas a tener que explicarselo a Demetrio
Responder Permalink Mozilla Firefox 2.0.0.1 · Linux ·
Hoc Jueves, 1 de febrero de 2007, 16:58
10
mucho micro acólito suelto, si que hay si, el algoritmo de booth funciona mejor en Linux. Ese pingüino guaaaapo
Responder Permalink Mozilla Firefox 2.0.0.1 · Linux ·
jasmina lanzas jasmina lanzas Martes, 20 de marzo de 2007, 16:57
11
por que no realizan un programa para calcular el complemento a dos en el lenguaje de c++
Responder Permalink Internet Explorer 6.0 · Windows XP ·
Alan Viernes, 11 de mayo de 2007, 23:00
12
Estaria bien q se agregara el algoritmo correspondiente. pero ya se q pido mucho. De todas formas sta clara la idea, jejejeje.
Responder Permalink Internet Explorer 6.0 · Windows XP ·
monica Jueves, 24 de mayo de 2007, 19:14
13
oye muchas gracias!!! me ha sido muy util!!
Responder Permalink Mozilla Firefox 2.0.0.3 · Windows XP ·
uno uno Martes, 12 de junio de 2007, 14:45
14
¿para hacerlo en c no serviría con not(num)+1?
Responder Permalink Mozilla Firefox 2.0.0.4 · Ubuntu Linux ·
uno uno Martes, 12 de junio de 2007, 14:46
15
¿para hacerlo en c no serviría con not(num)+1?
Responder Permalink Mozilla Firefox 2.0.0.4 · Ubuntu Linux ·
walter walter Viernes, 7 de septiembre de 2007, 16:24
16
muchas gracias
Responder Permalink Internet Explorer 6.0 · Windows XP ·
tOBY tOBY Sábado, 17 de noviembre de 2007, 06:15
17
excelente explcacion, ayuda bastante sobretodo ahora que necesito realizar un circuito multiplicador de punto flotante.. Gracias
Responder Permalink Mozilla Firefox 2.0.0.9 · Windows XP ·
claudio Domingo, 6 de enero de 2008, 02:34
18
excelente explicación....tengo un examen, y no fui a clases, me cayo de perillas.!
Responder Permalink Internet Explorer 7.0 · Windows XP ·
Manasa Manasa Jueves, 13 de marzo de 2008, 22:53
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
Responder Permalink Internet Explorer 6.0 · Windows XP ·
vhanla vhanla Jueves, 17 de julio de 2008, 21:24
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
Responder Permalink Opera 9.51 · Windows XP ·
luis Viernes, 7 de noviembre de 2008, 16:26
21
oy e esta muy claro tu documento, te lo agradezco, me ha servido de mucho
Responder Permalink Internet Explorer 7.0 · Windows XP ·
Nora Nora Martes, 25 de noviembre de 2008, 21:30
22
Buen articulo.! Saludos
Responder Permalink Mozilla Firefox 3.0.4 · Windows XP ·
noe Rodriguez noe Rodriguez Martes, 2 de diciembre de 2008, 13:53
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
Responder Permalink URL · Mozilla Firefox 2.0.0.18 · Windows XP ·
cristian cristian Domingo, 3 de mayo de 2009, 06:43
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??
Responder Permalink Mozilla Firefox 2.0.0.20 · Windows XP ·
Juan Juan Miércoles, 6 de mayo de 2009, 15:09
25
Gracias, no lo entendía, pero ahora algo entiendo. Voy a practicar un poco. Salu2.
Responder Permalink Opera 9.64 · Windows XP ·
javier cuellar javier cuellar Martes, 19 de mayo de 2009, 02:21
26
the explication is veri good
Responder Permalink Internet Explorer 6.0 · Windows XP ·
Xpolito Xpolito Lunes, 8 de junio de 2009, 04:00
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?
Responder Permalink URL · Opera 9.64 · Windows XP ·
aplatanado aplatanado Miércoles, 3 de marzo de 2010, 17:52
28
"el algoritmo de booth funciona mejor en Linux" Jajajajajaaja, lo que tiene uno que leer.
Responder Permalink Mozilla Firefox 3.5.8 · Ubuntu Linux ·
Miguel angel Miguel angel Martes, 20 de abril de 2010, 19:23
29
Ayudenme Hacer Este programa en java diseñar un programa que genere el binario de cualquier numero en java
Responder Permalink Internet Explorer 6.0 · Windows XP ·
Tarxo Tarxo Jueves, 15 de julio de 2010, 01:13
30
Muy buena explicación, por fin lo entiendo. Muchas gracias :-)
Responder Permalink Mozilla Firefox 3.6.6 · Windows XP ·
Spam o errónea
carolina carolina Martes, 31 de agosto de 2010, 01:52
31
@noe Rodriguez: ola amigo si ya tienes el codigo para c++ pasamelo plis mi correo es lafulana_8@hot... urge
Responder Permalink Internet Explorer 7.0 · Windows XP ·
Irrelevante
ahhhhhhhhh ahhhhhhhhh Domingo, 12 de septiembre de 2010, 23:49
32
diablos no entiendo nada
Responder Permalink Opera 9.80 · Linux ·
lobesno lobesno Lunes, 13 de septiembre de 2010, 01:22
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
Responder Permalink Mozilla Firefox 3.6.9 · Windows 7 ·
dassa dassa Lunes, 13 de septiembre de 2010, 22:38
34
sabes me sirvio mucho ......ahora ya se como exponer y dar mi clase.....ya que estudio ing. en sistemas... D: saludos >.
Responder Permalink Internet Explorer 8.0 · Windows 7 ·
Santiago Santiago Miércoles, 15 de septiembre de 2010, 21:39
35
Gracias por toda esta informacion, me servirá mucho, esto es lo que buscaba. Estudio Ingeieria Informatica.
Responder Permalink Internet Explorer 7.0 · Windows XP ·
FANNY FANNY Lunes, 20 de septiembre de 2010, 01:45
36
graziaz ezt0 me zirbi0 muxizim0 para mi tarea... eztudi0 en ing. en ziztemaz c0mputazi0nal...
Responder Permalink Internet Explorer 6.0 · Windows XP ·
MARIO CHUQUITARCO MARIO CHUQUITARCO Lunes, 20 de septiembre de 2010, 22:54
37
Es buena información para los profesionales de la informática. Sigan adelante; éxitos.
Responder Permalink Chrome 6.0.472.62 · Windows 7 ·
racso7712 Viernes, 24 de septiembre de 2010, 16:28
38
muy bien explicado me sirvio para darle una asesoria a un estudiante e ingenieria en sistemas gracias!
Responder Permalink Mozilla Firefox 3.6.10 · Windows XP ·
The Cat The Cat Viernes, 1 de octubre de 2010, 04:56
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
Responder Permalink Internet Explorer 8.0 · Windows Vista ·
anonimo Lunes, 9 de mayo de 2011, 20:10
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
Responder Permalink Mozilla Firefox 3.6.17 · Windows XP ·
arista arista Viernes, 17 de junio de 2011, 18:39
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.....
Responder Permalink Internet Explorer 7.0 · Windows XP ·
Stephan Stephan Lunes, 29 de agosto de 2011, 05:14
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
Responder Permalink Chrome 13.0.782.215 · Windows XP ·
rjcdz06 rjcdz06 Sábado, 11 de febrero de 2012, 20:11
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.
Responder Permalink Chrome 16.0.912.77 · Windows 7 ·
van van Sábado, 24 de marzo de 2012, 19:38
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
Responder Permalink Chrome 17.0.963.79 · Windows 7 ·
roman roman Sábado, 8 de septiembre de 2012, 01:00
45
amigo no tienes un video que se refiera a este tema
Responder Permalink Chrome 21.0.1180.89 · Windows 7 ·
Alexander Alexander Lunes, 24 de septiembre de 2012, 14:57
46
en verdad muchas muchas muchas gracias no sabes me salvaste la vida on!!! en verda te agradezco
Responder Permalink Chrome 21.0.1180.89 · Windows 7 ·
alejandra alejandra Martes, 25 de septiembre de 2012, 23:20
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
Responder Permalink Chrome 21.0.1180.89 · Windows 7 ·
Publica tu opinión



Acepto las condiciones y políticas de privacidad de este sitio web.
Suscribirme a través de FeedBurner a los nuevos artículos del blog por email.

Previsualización

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