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éndolos con un signo menos ("-"). Sin embargo, en el hardware de la computadora , 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 numérico binario para representar números con signo son: signo y magnitud , complemento a unos , complemento a dos y binario de compensación . 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, fraccionadas u otras elaboraciones sobre dichos temas.
No existe un criterio definitivo por el cual cualquiera de las representaciones sea universalmente superior. Para los números enteros, la representación utilizada en la mayoría de los dispositivos informáticos actuales es el complemento de dos, aunque los mainframes de la serie Unisys ClearPath Dorado utilizan el complemento de uno.
Historia
Los primeros días de la computación digital estuvieron marcados por una gran cantidad de ideas en competencia sobre tecnología de hardware y tecnología matemática (sistemas de numeración). Uno de los grandes debates fue el formato de los números negativos, algunos de los principales expertos de la época tenían opiniones muy fuertes y diferentes. [ cita requerida ] Un campamento apoyó el complemento de dos , el sistema que es dominante hoy. Otro campo apoyó el complemento de unos, donde cualquier valor positivo se convierte en su equivalente negativo invirtiendo todos los bits en una palabra. Un tercer grupo admitía "signo y magnitud" (signo-magnitud), donde un valor se cambia de positivo a negativo simplemente alternando el bit de signo de la palabra (orden superior).
Hubo argumentos a favor y en contra de cada uno de los sistemas. El signo y la magnitud permitieron 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 1 bit. Internamente, estos sistemas hacían matemáticas complementarias a unos, por lo que los números tendrían que convertirse a valores complementarios a unos cuando se transmitían desde un registro a la unidad matemática y luego se volvían a convertir a magnitud de signo cuando el resultado se transmitía de nuevo al registro. La electrónica requería más puertas que los otros sistemas, una preocupación clave cuando el costo y el empaque de los transistores discretos eran críticos. IBM fue uno de los primeros en apoyar la magnitud de los signos, y sus computadoras de las series 704 , 709 y 709x son quizás los sistemas más conocidos para usarlo.
El complemento de Ones 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 la magnitud del signo: la capacidad de representar cero negativo (−0). El cero negativo se comporta exactamente como el cero positivo; cuando se utiliza como operando en cualquier cálculo, el resultado será el mismo si un operando es cero positivo o negativo. Sin embargo, la desventaja es que la existencia de dos formas del mismo valor requiere dos en lugar de una sola comparación cuando se comprueba la igualdad con cero. La resta del complemento de unos también puede resultar en un préstamo final (descrito a continuación). Se puede argumentar que esto hace que la lógica de suma / resta sea más complicada o que la simplifica ya que una resta requiere simplemente invertir los bits del segundo operando a medida que se pasa al sumador. El PDP-1 , la serie CDC 160 , la serie CDC 3000 , la serie CDC 6000 , la serie UNIVAC 1100 y la computadora LINC utilizan la representación del complemento de uno.
El complemento de dos es el más fácil de implementar en hardware, lo que puede ser la razón última de su amplia popularidad. [1] Los procesadores de los primeros mainframes a menudo consistían en miles de transistores; la eliminación de un número significativo de transistores supuso un ahorro de costes significativo. Los mainframes como IBM System / 360 , la serie GE-600 , [2] y el PDP-6 y PDP-10 utilizan el complemento de dos, al igual que los miniordenadores como el PDP-5 y PDP-8 y el PDP-11 y VAX . Los arquitectos de las primeras CPU basadas en circuitos integrados ( Intel 8080 , etc.) optaron por utilizar las matemáticas complementarias a dos. A medida que avanzaba la tecnología IC, prácticamente todos adoptaron la tecnología de complemento a dos. Los procesadores x86 , [3] m68k , Power ISA , [4] MIPS , SPARC , ARM , Itanium , PA-RISC y DEC Alpha son el complemento de dos.
Representación de magnitud firmada
Esta representación también se denomina representación de "signo-magnitud" o "signo y magnitud". En este enfoque, el signo de un número se representa con un bit de signo : establecer ese bit (a menudo el bit más significativo ) en 0 para un número positivo o cero positivo, y establecerlo en 1 para un número negativo o cero negativo. Los bits restantes del número indican la magnitud (o valor absoluto ). Por ejemplo, en un byte de ocho bits , solo siete bits representan la magnitud, que puede oscilar entre 0000000 (0) y 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 de magnitud con signo tiene múltiples consecuencias, lo que hace que su implementación sea más compleja: [5]
- Hay dos formas de representar cero, 00000000 (0) y 10000000 ( −0 ).
- 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 simplemente hacer un acarreo de extremo, y el complemento de dos puede ignorar el bit de signo y depender del comportamiento de desbordamiento.
- 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.
- El número mínimo negativo es −127 en lugar de −128 en el caso del complemento a dos.
Este enfoque es directamente comparable a la forma común de mostrar un signo (colocando un "+" o "-" junto a la magnitud del número). Algunas de las primeras computadoras binarias (por ejemplo, IBM 7090 ) usan esta representación, quizás debido a su relación natural con el uso común. La magnitud con signo es la forma más común de representar el significado en valores de punto flotante .
Complemento de unos
Valor binario | Interpretación del complemento de unos | Interpretación sin firmar |
---|---|---|
00000000 | +0 | 0 |
00000001 | 1 | 1 |
⋮ | ⋮ | ⋮ |
01111101 | 125 | 125 |
01111110 | 126 | 126 |
01111111 | 127 | 127 |
10000000 | −127 | 128 |
10000001 | −126 | 129 |
10000010 | −125 | 130 |
⋮ | ⋮ | ⋮ |
11111101 | −2 | 253 |
11111110 | −1 | 254 |
11111111 | −0 | 255 |
Alternativamente, se puede utilizar un sistema conocido como complemento a unos [6] para representar números negativos. La forma de complemento a unos de un número binario negativo es el NO bit a bit que se le aplica, es decir, el "complemento" de su contraparte positiva. Al igual que la representación de signo y magnitud, el complemento a unos tiene dos representaciones de 0: 00000000 (+0) y 11111111 ( −0 ). [7]
Como ejemplo, la forma de complemento a unidades de 00101011 (43 10 ) se convierte en 11010100 (−43 10 ). El rango de números con signo que utilizan el complemento a unos está representado por - (2 N −1-1 ) a (2 N −1-1 ) y ± 0. Un byte convencional de ocho bits es de −127 10 a +127 10, siendo cero 00000000 (+0) o 11111111 (−0).
Para sumar dos números representados en este sistema, uno hace una suma binaria convencional, pero luego es necesario hacer un acarreo final : es decir, agregar cualquier acarreo resultante 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 ← Agregar acarreo─────────── ── 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 agregar el acarreo.
Una observación sobre la terminología: El sistema se conoce como "complemento a unos" 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 del cero en complemento a uno que es una secuencia larga de unos (−0). La aritmética en complemento a dos, por otro lado, forma la negación de x al restar x de una sola gran potencia de dos que es congruente con +0. [9] Por lo tanto, las representaciones en complemento a uno y complemento a dos del mismo valor negativo diferirán en uno.
Tenga en cuenta que la representación en complemento a unos de un número negativo se puede obtener a partir de la representación de magnitud de signo simplemente complementando la magnitud a nivel de bits (invirtiendo todos los bits después del primero). Por ejemplo, el número decimal −125 con su representación de magnitud de signo 11111101 se puede representar en forma de complemento a unos como 10000010.
Complemento a dos
Valor binario | Interpretación del complemento a dos | Interpretación sin firmar |
---|---|---|
00000000 | 0 | 0 |
00000001 | 1 | 1 |
⋮ | ⋮ | ⋮ |
01111110 | 126 | 126 |
01111111 | 127 | 127 |
10000000 | −128 | 128 |
10000001 | −127 | 129 |
10000010 | −126 | 130 |
⋮ | ⋮ | ⋮ |
11111110 | −2 | 254 |
11111111 | −1 | 255 |
Los problemas de las representaciones múltiples de 0 y la necesidad del acarreo de extremo alrededor son eludidos por un sistema llamado complemento a dos . En complemento a dos, los números negativos están representados por el patrón de bits que es uno mayor (en un sentido sin signo) que el complemento a uno del valor positivo.
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 agregando uno a ese resultado. [10] Esto en realidad refleja la estructura del anillo en todos los números enteros módulo 2 N :. La suma de un par de enteros en complemento a dos es lo mismo que la suma de un par de números sin signo (excepto por la detección de desbordamiento , si se hace); lo mismo es cierto para la resta e incluso para los N bits significativos más bajos de un producto (valor de 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 puede verse 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:
Ejemplo 1 | Ejemplo 2 | |
---|---|---|
1. A partir de la derecha, busque el primer "1" | 0010100 1 | 00101 1 00 |
2. Invierte todos los bits a la izquierda de ese "1" | 1101011 1 | 11010 100 |
Método dos:
- Invierte todos los bits a través del número
- Agrega 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"):
- ~ 00000010 → 11111101
- 11111101 + 1 → 11111110 (−2 en complemento a dos)
Binario de compensación
Valor binario | Exceso de interpretación 128 | Interpretación sin firmar |
---|---|---|
00000000 | −128 | 0 |
00000001 | −127 | 1 |
⋮ | ⋮ | ⋮ |
01111111 | −1 | 127 |
10000000 | 0 | 128 |
10000001 | 1 | 129 |
⋮ | ⋮ | ⋮ |
11111111 | +127 | 255 |
El binario de compensación , también llamado exceso de K o representación sesgada, utiliza un número K preespecificado como valor de sesgo. Un valor está representado por el número sin signo que es K mayor que el valor deseado. Por tanto, 0 está representado por K y - K está representado por el patrón de bits de todos 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 ahora se utilizan principalmente para el exponente de números de punto flotante . El estándar de punto flotante IEEE 754 define el campo exponente de un número de precisión simple (32 bits) como un campo de exceso de 127 de 8 bits . El campo de exponente de doble precisión (64 bits) es un campo de exceso de 1023 de 11 bits ; ver sesgo de exponente . También tenía uso para números decimales codificados en binario como exceso-3 .
Base -2
En los sistemas numéricos binarios convencionales, la base o raíz es 2; por 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 alterno. Los números que se pueden representar con cuatro bits se muestran en la tabla de comparación a continuació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 número negativo más grande que se puede representar es dos veces mayor que el número positivo más grande que se puede representar, y viceversa si la palabra tiene un número impar de bits.
Tabla de comparación
La siguiente tabla muestra los números enteros positivos y negativos que se pueden representar con cuatro bits.
Decimal | No firmado | Signo y magnitud | Complemento de unos | Complemento a dos | Exceso-8 (sesgado) | Base -2 |
---|---|---|---|---|---|---|
+16 | N / A | N / A | N / A | N / A | N / A | N / A |
+15 | 1111 | N / A | N / A | N / A | N / A | N / A |
+14 | 1110 | N / A | N / A | N / A | N / A | N / A |
+13 | 1101 | N / A | N / A | N / A | N / A | N / A |
+12 | 1100 | N / A | N / A | N / A | N / A | N / A |
+11 | 1011 | N / A | N / A | N / A | N / A | N / A |
+10 | 1010 | N / A | N / A | N / A | N / A | N / A |
+9 | 1001 | N / A | N / A | N / A | N / A | N / A |
+8 | 1000 | N / A | N / A | N / A | N / A | N / A |
+7 | 0111 | 0111 | 0111 | 0111 | 1111 | N / A |
+6 | 0110 | 0110 | 0110 | 0110 | 1110 | N / A |
+5 | 0101 | 0101 | 0101 | 0101 | 1101 | 0101 |
+4 | 0100 | 0100 | 0100 | 0100 | 1100 | 0100 |
+3 | 0011 | 0011 | 0011 | 0011 | 1011 | 0111 |
+2 | 0010 | 0010 | 0010 | 0010 | 1010 | 0110 |
+1 | 0001 | 0001 | 0001 | 0001 | 1001 | 0001 |
+0 | 0000 | 0000 | 0000 | 0000 | 1000 | 0000 |
−0 | 1000 | 1111 | ||||
−1 | N / A | 1001 | 1110 | 1111 | 0111 | 0011 |
−2 | N / A | 1010 | 1101 | 1110 | 0110 | 0010 |
−3 | N / A | 1011 | 1100 | 1101 | 0101 | 1101 |
−4 | N / A | 1100 | 1011 | 1100 | 0100 | 1100 |
−5 | N / A | 1101 | 1010 | 1011 | 0011 | 1111 |
−6 | N / A | 1110 | 1001 | 1010 | 0010 | 1110 |
−7 | N / A | 1111 | 1000 | 1001 | 0001 | 1001 |
−8 | N / A | N / A | N / A | 1000 | 0000 | 1000 |
−9 | N / A | N / A | N / A | N / A | N / A | 1011 |
−10 | N / A | N / A | N / A | N / A | N / A | 1010 |
−11 | N / A | N / A | N / A | N / A | N / A | N / A |
Misma tabla, vista desde "dados estos bits binarios, cuál es el número interpretado por el sistema de representación":
Binario | No firmado | Signo y magnitud | Complemento de unos | Complemento a dos | Exceso-8 | Base -2 |
---|---|---|---|---|---|---|
0000 | 0 | 0 | 0 | 0 | −8 | 0 |
0001 | 1 | 1 | 1 | 1 | −7 | 1 |
0010 | 2 | 2 | 2 | 2 | −6 | −2 |
0011 | 3 | 3 | 3 | 3 | −5 | −1 |
0100 | 4 | 4 | 4 | 4 | −4 | 4 |
0101 | 5 | 5 | 5 | 5 | −3 | 5 |
0110 | 6 | 6 | 6 | 6 | −2 | 2 |
0111 | 7 | 7 | 7 | 7 | −1 | 3 |
1000 | 8 | −0 | −7 | −8 | 0 | −8 |
1001 | 9 | −1 | −6 | −7 | 1 | −7 |
1010 | 10 | −2 | −5 | −6 | 2 | −10 |
1011 | 11 | −3 | −4 | −5 | 3 | −9 |
1100 | 12 | −4 | −3 | −4 | 4 | −4 |
1101 | 13 | −5 | −2 | −3 | 5 | −3 |
1110 | 14 | −6 | −1 | −2 | 6 | −6 |
1111 | 15 | −7 | −0 | −1 | 7 | −5 |
Otros sistemas
La "codificación en zig-zag" de Protocol Buffers de Google es un sistema similar al de signo y 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 enteros no negativos (sin signo) se use de manera eficiente para enteros con signo. [11]
Otro enfoque consiste en asignar un signo a cada dígito , lo que produce la representación del dígito con signo . Por ejemplo, en 1726, John Colson abogó por reducir las expresiones a "números pequeños", números 1, 2, 3, 4 y 5. En 1840, Augustin Cauchy también expresó su preferencia por tales números decimales modificados para reducir errores en el cálculo.
Ver también
- Ternario equilibrado
- Decimal codificado en binario
- Formato de número de computadora
- Método de complementos
- Firma
Referencias
- ^ Choo, Hunsoo; Muhammad, K .; Roy, K. (febrero de 2003). "Multiplicador de intercambio de cómputo en complemento a dos y sus aplicaciones para DFE de alto rendimiento" . Transacciones IEEE sobre procesamiento de señales . 51 (2): 458–469. doi : 10.1109 / TSP.2002.806984 .
- ^ Manual de referencia de programación GE-625/635 . General Electric . Enero de 1966 . Consultado el 15 de agosto de 2013 .
- ^ 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 .
- ^ Power ISA versión 2.07 . Power.org . Sección 1.4 . Consultado el 6 de agosto de 2013 .,
- ^ Bacon, Jason W. (2010-2011). "Apuntes de clase 315 de informática" . Consultado el 21 de febrero de 2020 .
- ^ US 4484301 , "Multiplicador de matriz que funciona en formato de complemento a uno", publicado el 10 de marzo de 1981
- ^ US 6760440 , "Combinador criptográfico de complemento de uno", publicado el 11 de diciembre de 1999
- ^ Shedletsky, John J. (1977). "Comentario sobre el comportamiento secuencial e indeterminado de una víbora End-Around-Carry" . Transacciones IEEE en computadoras . 26 (3): 271-272. doi : 10.1109 / TC.1977.1674817 .
- ^ Donald Knuth: El arte de la programación informática , Volumen 2: Algoritmos seminuméricos, capítulo 4.1
- ^ Thomas Finley (abril de 2000). "Complemento a dos" . Universidad de Cornell . Consultado el 15 de septiembre de 2015 .
- ^ Búferes de protocolo: enteros firmados
- Ivan Flores, La lógica de la aritmética informática , Prentice-Hall (1963)
- Israel Koren, Algoritmos aritméticos informáticos , AK Peters (2002), ISBN 1-56881-160-8