¡Envia tu foto al Fotomaton!
¡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:
(0·2^7+1·2^6+0·2^5+1·2^4+0·2^3+1·2^2+1·2^1+0·2^0 = 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:
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.
Conexión a internet más rápida y veloz.
19 Comentarios
Y yo que a veces que considero geek......
Que equivocado estaba.........
Muy bien pero tarde, si lo hubiese tenido el domingo
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.
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!
Oigan, esto está muy interesante, voy a aplicarlo... Saludos...
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
UHY MUY BUERNA PAG, GRACIAS X EL TIP, ^^
Mucho micro acólito suelto, si que hay si, el algoritmo de booth funciona mejor en Linux. Ese pingüino guaaaapo
Por que no realizan un programa para calcular el complemento a dos en el lenguaje de c++
Estaria bien q se agregara el algoritmo correspondiente. pero ya se q pido mucho. De todas formas sta clara la idea, jejejeje.
Oye muchas gracias!!! me ha sido muy util!!
¿para hacerlo en c no serviría con not(num)+1?
¿para hacerlo en c no serviría con not(num)+1?
Muchas gracias
Excelente explcacion, ayuda bastante sobretodo ahora que necesito realizar un circuito multiplicador de punto flotante.. Gracias
Excelente explicación....tengo un examen, y no fui a clases, me cayo de perillas.!
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
en Internet.
Envia tu fotografía al fotomatón de Emezeta. Puedes enviar varias y saldrás en la portada de Emezeta.
Suscripción gratuita
Sigue los artículos de Emezeta blog.
Me llamo José Román, aka Manz. Soy estudiante
de ingeniería informática en la ULL y vivo en Santa
Cruz de Tenerife. Emezeta blog es mi rincón de la red, en él escribo artículos acerca de
tecnología, curiosidades, informática y todo ello sin olvidar el humor.
Si quieres saber más sobre mi, haz clic en ¿Quién es Manz?. Si lo deseas, también puedes ver mi CV o enviarme un mensaje para contactar conmigo.
Si te interesa el contenido de Emezeta blog, puedes suscribirte en Bloglines, Google o cualquier otro sindicador de contenidos.
Puedes recibir los artículos directamente en tu e-mail si lo deseas:
Si quieres dejar un comentario acerca del artículo, pulsa aquí. Mediante este formulario enviarás un e-mail privado al autor del blog (tu mensaje no será publicado en este sitio). Asegurate de escribir tu e-mail para poder responderte:
¡OJO! Me encanta recibir emails pero no me da tiempo de contestarlos todos. ¡Paciencia! Aunque tarde, siempre los contesto.
miimoWow!!gracias por tu ayuda...fue muy util...agredecido!bayy...
CrowMMMMM yo empezaria en PII con el objetivo de darles un uso coherente, a la fecha h...
Nacho 001El LP Dock USB Turntable me agrada por lo del dock para el iPod (ya que tengo un n...
sofíaaaJajaja bueno a mí todavía no me han contestado es que no sé como funciona esto, en...
davidEl virus lechuck se puede eliminar facilmente, si sabes utilizar el simbolo del si...
¿Quieres anunciar un producto? Sé analizado en Emezeta blog mediante la red Zync. Emezeta blog tiene más de 650.000 páginas vistas al mes.
Envia tus fotos o capturas de webcam para el concurso.
Tus fotos en la portada de una revista:
Si te gusta este sitio, puedes colocar un enlace a Emezeta blog en tu página web o blog, pegando el siguiente código:
Alojado en MediaTemple.
10 consultas efectuadas / Página generada en 0.072 segundos
Programado íntegramente por José Román (Manz) en XHTML y CSS estándar.
Sindicado bajo Feed RSS. Contenido bajo licencia Creative Commons
Estadísticas de visitas · Términos y condiciones · Contacto · Publicidad · Preguntas frecuentes (FAQ)
