stringtranslate.com

Representaciones de números con signo

En informática , se requieren representaciones de números con signo para codificar números negativos en sistemas numéricos binarios.

En matemáticas , los números negativos en cualquier base se representan anteponiéndoles un signo menos ("−"). Sin embargo, en los registros de la RAM o la CPU , los números se representan solo como secuencias de bits , sin símbolos adicionales. Los cuatro métodos más conocidos para extender el sistema de numeración binario para representar números con signo son: signo-magnitud, complemento a uno, complemento a dos y binario desfasado. Algunos de los métodos alternativos utilizan signos implícitos en lugar de explícitos, como el binario negativo, utilizando la base −2. Se pueden idear métodos correspondientes para otras bases , ya sean positivas, negativas, fraccionarias u otras elaboraciones sobre estos temas.

No existe un criterio definitivo según el cual alguna de las representaciones sea universalmente superior. Para los números enteros, la representación que se utiliza en la mayoría de los dispositivos informáticos actuales es el complemento a dos, aunque los mainframes de la serie Unisys ClearPath Dorado utilizan el complemento a uno.

Historia

Los primeros días de la informática digital estuvieron marcados por ideas en pugna sobre la tecnología de hardware y la tecnología matemática (sistemas de numeración). Uno de los grandes debates fue el formato de los números negativos, y algunos de los principales expertos de la época expresaron opiniones muy firmes y diferentes. [ cita requerida ] Un grupo apoyó el complemento a dos , el sistema que es dominante hoy en día. Otro grupo apoyó el complemento a uno, donde un valor negativo se forma invirtiendo todos los bits en su equivalente positivo. Un tercer grupo apoyó el signo-magnitud, donde un valor se cambia de positivo a negativo simplemente alternando el bit de orden más alto de la palabra.

Hubo argumentos a favor y en contra de cada uno de los sistemas. El signo-magnitud permitió un seguimiento más fácil de los volcados de memoria (un proceso común en la década de 1960) ya que los valores numéricos pequeños usan menos bits 1. Estos sistemas hacían matemáticas de complemento a uno internamente, por lo que los números tendrían que convertirse a valores de complemento a uno cuando se transmitían desde un registro a la unidad matemática y luego convertirse nuevamente a signo-magnitud cuando el resultado se transmitía de vuelta al registro. La electrónica requería más puertas que los otros sistemas, una preocupación clave cuando el costo y el empaquetado de los transistores discretos eran críticos. IBM fue uno de los primeros partidarios del signo-magnitud, y sus computadoras de las series 704 , 709 y 709x son quizás los sistemas más conocidos que lo usaban.

El complemento a uno permitió diseños de hardware algo más simples, ya que no había necesidad de convertir valores cuando se pasaban hacia y desde la unidad matemática. Pero también compartía una característica indeseable con el signo-magnitud: la capacidad de representar cero negativo (−0). El cero negativo se comporta exactamente como el cero positivo: cuando se usa como operando en cualquier cálculo, el resultado será el mismo ya sea que un operando sea cero positivo o negativo. La desventaja es que la existencia de dos formas del mismo valor requiere dos comparaciones al verificar la igualdad con cero. La resta del complemento a uno también puede resultar en un préstamo de fin de vuelta (descrito a continuación). Se puede argumentar que esto hace que la lógica de suma y resta sea más complicada o que la hace más simple, ya que una resta requiere simplemente invertir los bits del segundo operando a medida que se pasa al sumador. La PDP-1 , la serie CDC 160 , la serie CDC 3000 , la serie CDC 6000 , la serie UNIVAC 1100 y la computadora LINC usan la representación del complemento a uno.

El complemento a dos es el más fácil de implementar en hardware, lo que puede ser la razón última de su popularidad generalizada. [1] Los procesadores en los primeros mainframes a menudo constaban de miles de transistores, por lo que eliminar una cantidad significativa de transistores fue un ahorro de costos significativo. Mainframes como el IBM System/360 , la serie GE-600 , [2] y el PDP-6 y PDP-10 usan el complemento a dos, al igual que minicomputadoras como el PDP-5 y PDP-8 y las máquinas PDP-11 y VAX . Los arquitectos de las primeras CPU basadas en circuitos integrados ( Intel 8080 , etc.) también eligieron usar matemáticas de complemento a dos. A medida que la tecnología de circuitos integrados avanzó, la tecnología de complemento a dos se adoptó en prácticamente todos los procesadores, incluidos x86 , [3] m68k , Power ISA , [4] MIPS , SPARC , ARM , Itanium , PA-RISC y DEC Alpha .

Signo-magnitud

En la representación signo-magnitud , también llamada signo-y-magnitud o magnitud con signo , un número con signo se representa mediante el patrón de bits correspondiente al signo del número para el bit de signo (a menudo el bit más significativo , establecido en 0 para un número positivo y en 1 para un número negativo), y la magnitud del número (o valor absoluto ) para los bits restantes. Por ejemplo, en un byte de ocho bits , solo siete bits representan la magnitud, que puede variar de 0000000 (0) a 1111111 (127). Por lo tanto, los números que van desde −127 10 a +127 10 se pueden representar una vez que se agrega el bit de signo (el octavo bit). Por ejemplo, −43 10 codificado en un byte de ocho bits es 1 0101011 mientras que 43 10 es 0 0101011. El uso de la representación signo-magnitud tiene múltiples consecuencias que las hacen más complejas de implementar: [5]

  1. Hay dos formas de representar el cero, 00000000 (0) y 10000000 ( −0 ).
  2. La suma y la resta requieren un comportamiento diferente según el bit de signo, mientras que el complemento de uno puede ignorar el bit de signo y solo hacer un acarreo de fin a fin, y el complemento de dos puede ignorar el bit de signo y depender del comportamiento de desbordamiento.
  3. La comparación también requiere inspeccionar el bit de signo, mientras que en el complemento a dos, uno puede simplemente restar los dos números y verificar si el resultado es positivo o negativo.
  4. El número negativo mínimo es −127, en lugar de −128 como en el caso del complemento a dos.

Este enfoque es directamente comparable a la forma común de mostrar un signo (colocar un "+" o "−" junto a la magnitud del número). Algunas computadoras binarias tempranas (por ejemplo, IBM 7090 ) usan esta representación, tal vez debido a su relación natural con el uso común. Signo-magnitud es la forma más común de representar la mantisa en valores de punto flotante .

Complemento a uno

En la representación del complemento a uno , [6] un número negativo se representa mediante el patrón de bits correspondiente al NOT bit a bit (es decir, el "complemento") del número positivo. Al igual que la representación de signo-magnitud, el complemento a uno tiene dos representaciones de 0: 00000000 (+0) y 11111111 ( −0 ). [7]

Por ejemplo, la forma de complemento a uno de 00101011 (43 10 ) se convierte en 11010100 (−43 10 ). El rango de números con signo que utilizan el complemento a uno se representa por −(2 N −1 − 1) a (2 N −1 − 1) y ±0. Un byte convencional de ocho bits es −127 10 a +127 10 , donde cero es 00000000 (+0) o 11111111 (−0).

Para sumar dos números representados en este sistema, se hace una suma binaria convencional, pero luego es necesario hacer un acarreo de extremo a extremo : es decir, agregar cualquier acarreo resultante nuevamente a la suma resultante. [8] Para ver por qué esto es necesario, considere el siguiente ejemplo que muestra el caso de la suma de −1 (11111110) a +2 (00000010):

 decimal binario 11111110 −1+ 00000010 +2─────────── ── 1 00000000 0 ← No es la respuesta correcta 1 +1 ← Añadir carry─────────── ── 00000001 1 ← Respuesta correcta

En el ejemplo anterior, la primera suma binaria da 00000000, lo cual es incorrecto. El resultado correcto (00000001) solo aparece cuando se vuelve a sumar el acarreo.

Un comentario sobre la terminología: El sistema se conoce como "complemento a uno" porque la negación de un valor positivo x (representado como el NOT bit a bit de x ) también se puede formar restando x de la representación de complemento a uno de cero que es una secuencia larga de unos (−0). La aritmética de complemento a dos, por otro lado, forma la negación de x restando x de una única gran potencia de dos que es congruente con +0. [9] Por lo tanto, las representaciones de complemento a uno y complemento a dos del mismo valor negativo diferirán en uno.

Tenga en cuenta que la representación de complemento a uno de un número negativo se puede obtener a partir de la representación de signo-magnitud simplemente complementando bit a bit la magnitud (invirtiendo todos los bits después del primero). Por ejemplo, el número decimal −125 con su representación de signo-magnitud 11111101 se puede representar en forma de complemento a uno como 10000010.

Complemento a dos

En la representación del complemento a dos , un número negativo se representa mediante el patrón de bits correspondiente al NOT bit a bit (es decir, el "complemento") del número positivo más uno, es decir, al complemento a unos más uno. Esto evita los problemas de las representaciones múltiples de 0 y la necesidad del acarreo de fin de la representación del complemento a unos. Esto también se puede considerar como el bit más significativo que representa el inverso de su valor en un entero sin signo; en un byte sin signo de 8 bits, el bit más significativo representa el lugar 128, mientras que en el complemento a dos ese bit representaría −128.

En complemento a dos, solo hay un cero, representado como 00000000. La negación de un número (ya sea negativo o positivo) se realiza invirtiendo todos los bits y luego sumando uno a ese resultado. [10] Esto en realidad refleja la estructura de anillo en todos los números enteros módulo 2 N : . La suma de un par de números enteros en complemento a dos es lo mismo que la suma de un par de números sin signo (excepto para la detección de desbordamiento , si se realiza); lo mismo es cierto para la resta e incluso para N bits significativos más bajos de un producto (valor de la multiplicación). Por ejemplo, una suma en complemento a dos de 127 y −128 da el mismo patrón de bits binarios que una suma sin signo de 127 y 128, como se puede ver en la tabla de complemento a dos de 8 bits.

Un método más sencillo para obtener la negación de un número en complemento a dos es el siguiente:

Método dos:

  1. Invierte todos los bits del número. Esto calcula el mismo resultado que restarle menos uno.
  2. Agregar uno

Ejemplo: para +2, que es 00000010 en binario (el carácter ~ es el operador NOT bit a bit de C , por lo que ~X significa "invertir todos los bits en X"):

  1. ~00000010 → 11111101
  2. 11111101 + 1 → 11111110 (−2 en complemento a dos)

Desplazamiento binario

En la representación binaria desfasada , también llamada exceso- K o sesgada , un número con signo se representa mediante el patrón de bits correspondiente al número sin signo más K , donde K es el valor de sesgo o desfase . Por lo tanto, 0 se representa mediante K y − K se representa mediante un patrón de bits compuesto únicamente por ceros. Esto puede verse como una ligera modificación y generalización del complemento a dos antes mencionado, que es virtualmente la representación en exceso-(2 N −1 ) con el bit más significativo negado .

Las representaciones sesgadas se utilizan ahora principalmente para el exponente de números de punto flotante . El estándar de punto flotante IEEE 754 define el campo exponencial de un número de precisión simple (32 bits) como un campo de exceso de 127 de 8 bits . El campo exponencial de precisión doble (64 bits) es un campo de exceso de 1023 de 11 bits ; consulte sesgo de exponente . También se utilizaba para números decimales codificados en binario como exceso de 3 .

Base -2

En la representación de base −2 , un número con signo se representa utilizando un sistema numérico con base −2. En los sistemas numéricos binarios convencionales, la base, o radix , es 2; por lo tanto, el bit más a la derecha representa 2 0 , el siguiente bit representa 2 1 , el siguiente bit 2 2 , y así sucesivamente. Sin embargo, también es posible un sistema numérico binario con base −2. El bit más a la derecha representa (−2) 0 = +1 , el siguiente bit representa (−2) 1 = −2 , el siguiente bit (−2) 2 = +4 y así sucesivamente, con signo alternado. Los números que se pueden representar con cuatro bits se muestran en la siguiente tabla de comparación.

El rango de números que se pueden representar es asimétrico. Si la palabra tiene un número par de bits, la magnitud del mayor número negativo que se puede representar es el doble de grande que el mayor número positivo que se puede representar, y viceversa si la palabra tiene un número impar de bits.

Tabla comparativa

La siguiente tabla muestra los números enteros positivos y negativos que se pueden representar utilizando cuatro bits.

La misma tabla, vista desde "dados estos bits binarios, ¿cuál es el número tal como lo interpreta el sistema de representación":

Otros sistemas

La "codificación en zigzag" de Protocol Buffers de Google es un sistema similar al de signo-magnitud, pero utiliza el bit menos significativo para representar el signo y tiene una única representación de cero. Esto permite que una codificación de cantidad de longitud variable destinada a números enteros no negativos (sin signo) se utilice de manera eficiente para números enteros con signo. [11]

Un método similar se utiliza en los estándares de compresión de vídeo Advanced Video Coding/H.264 y High Efficiency Video Coding/H.265 para ampliar la codificación exponencial de Golomb a los números negativos. En esa extensión, el bit menos significativo es casi un bit de signo; cero tiene el mismo bit menos significativo (0) que todos los números negativos. Esta elección da como resultado que el número positivo representable de mayor magnitud sea uno más alto que el número negativo de mayor magnitud, a diferencia de lo que ocurre en la codificación en complemento a dos o en la codificación en zigzag de Protocol Buffers.

Otro enfoque consiste en dar a cada dígito un signo, lo que da como resultado la representación de dígitos con signo . Por ejemplo, en 1726, John Colson abogó por reducir las expresiones a "números pequeños", los numerales 1, 2, 3, 4 y 5. En 1840, Augustin Cauchy también expresó su preferencia por esos números decimales modificados para reducir los errores en los cálculos.

Véase también

Referencias

  1. ^ Choo, Hunsoo; Muhammad, K.; Roy, K. (febrero de 2003). "Multiplicador de uso compartido de cálculo de complemento a dos y sus aplicaciones a DFE de alto rendimiento". IEEE Transactions on Signal Processing . 51 (2): 458–469. Bibcode :2003ITSP...51..458C. doi :10.1109/TSP.2002.806984.
  2. ^ Manual de referencia de programación GE-625/635. General Electric . Enero de 1966. Consultado el 15 de agosto de 2013 .
  3. ^ Manual del desarrollador de software de arquitecturas Intel 64 e IA-32 (PDF) . Intel . Sección 4.2.1 . Consultado el 6 de agosto de 2013 .
  4. ^ Power ISA Versión 2.07 (PDF) . Power.org . Sección 1.4 . Consultado el 2 de noviembre de 2023 .,
  5. ^ Bacon, Jason W. (2010–2011). «Computer Science 315 Lecture Notes». Archivado desde el original el 14 de febrero de 2020. Consultado el 21 de febrero de 2020 .
  6. ^ US 4484301, "Multiplicador de matriz que opera en formato de complemento a uno", publicado el 10 de marzo de 1981 
  7. ^ US 6760440, "Combinador criptográfico de complemento a uno", publicado el 11 de diciembre de 1999 
  8. ^ Shedletsky, John J. (1977). "Comentario sobre el comportamiento secuencial e indeterminado de un sumador de acarreo de extremo a extremo". IEEE Transactions on Computers . 26 (3): 271–272. doi :10.1109/TC.1977.1674817. S2CID  14661474.
  9. ^ Donald Knuth: El arte de la programación informática , Volumen 2: Algoritmos seminuméricos, capítulo 4.1
  10. ^ Thomas Finley (abril de 2000). "Two's Complement". Universidad de Cornell . Consultado el 15 de septiembre de 2015 .
  11. ^ Buffers de protocolo: números enteros con signo