Complemento de dos

El complemento a dos es el método más común para representar enteros con signo (positivos, negativos y cero) en computadoras, ^{[ 1 ]} y, en general, valores binarios de punto fijo . Al igual que con los sistemas de complemento a uno y signo-magnitud , el complemento a dos utiliza el bit más significativo como signo para indicar números positivos (0) o negativos (1), y a los números no negativos se les da su representación sin signo (6 es 0110, cero es 0000); sin embargo, en complemento a dos, los números negativos se representan tomando el complemento de bits de su magnitud y luego sumando uno (−6 es 1010). El número de bits en la representación se puede aumentar rellenando todos los bits superiores adicionales de los números negativos o positivos con 1 o 0, respectivamente, o disminuir eliminando 1 o 0 iniciales adicionales.

A diferencia del esquema de complemento a uno , el esquema de complemento a dos solo tiene una representación para el cero, con espacio para un número negativo adicional (el rango de un número de 4 bits es de -8 a +7). Además, las mismas implementaciones aritméticas se pueden usar tanto en enteros con signo como sin signo ^{[ 2 ]} y difieren solo en las situaciones de desbordamiento de enteros , ya que la suma de las representaciones de un número positivo y su negativo es 0 (con el bit de acarreo activado).

A continuación se describe el procedimiento para obtener la representación en complemento a dos de un número negativo dado en dígitos binarios:

• Paso 1: comenzando con la representación binaria absoluta del número, siendo el bit principal un bit de signo; ^{[ 3 ]}
• Paso 2: invertir (o voltear) todos los bits, cambiando cada 0 a 1 y cada 1 a 0;
• Paso 3: sumar 1 al número invertido completo, ignorando cualquier desbordamiento . Si se tiene en cuenta el desbordamiento, el resultado será incorrecto.

Por ejemplo, para calcular el número decimal −6 en binario a partir del número 6 :

• Paso 1: +6 en decimal es 0110 en binario; el bit más significativo de la izquierda (el primer 0) es el signo (solo 110 en binario sería −2 en decimal).
• Paso 2: invierte todos los bits en 0110 , dando como resultado 1001 .
• Paso 3: suma el valor posicional 1 al número invertido 1001 , obteniendo 1010 .

Para verificar que 1010 efectivamente tiene un valor de −6 , sume los valores posicionales, pero reste el valor del signo del cálculo final. Como el valor más significativo es el valor del signo, debe restarse para producir el resultado correcto: 1010 = − ( 1 ×2 ³ ) + ( 0 ×2 ² ) + ( 1 ×2 ¹ ) + ( 0 ×2 ⁰ ) = 1 ×−8 + 0 + 1 ×2 + 0 = −6.

Los pasos 2 y 3 juntos constituyen un método válido para calcular el inverso aditivo.${\displaystyle -n}$de cualquier número entero (positivo o negativo)${\displaystyle n}$donde tanto la entrada como la salida están en complemento a dos. Una alternativa para calcular${\displaystyle -n}$es usar la resta${\displaystyle 0-n}$A continuación se muestra la resta de números enteros en complemento a dos.

El complemento a dos es un ejemplo de complemento a la base . El "dos" en el nombre se refiere al número 2ⁿ ^, "dos elevado a la potencia de N", que es el valor con respecto al cual se calcula el complemento en un sistema de N bits (el único caso en el que se produciría exactamente "dos" en este término es N = 1 , es decir, para un sistema de 1 bit, pero estos no tienen capacidad para un signo y un cero simultáneamente ) . Por lo tanto, la definición precisa del complemento a dos de un número de N bits es el complemento de ese número con respecto a 2ⁿ ^.

La propiedad definitoria de ser un complemento de un número con respecto a 2 ^N es simplemente que la suma de este número con el original produce 2 ^N . Por ejemplo, usando binario con números de hasta tres bits (de modo que N = 3 y 2 ^N = 2 ³ = 8 = 1000 ₂ , donde ' ₂ ' indica una representación binaria), un complemento a dos para el número 3 ( 011 ₂ ) es 5 ( 101 ₂ ), porque sumado al original da 2 ³ = 1000 ₂ = 011 ₂ + 101 ₂ . Cuando esta correspondencia se emplea para representar números negativos, implica, por analogía con los dígitos decimales y un espacio numérico que solo admite ocho números no negativos (del 0 al 7), dividir dicho espacio en dos conjuntos: los cuatro primeros (0, 1, 2, 3) permanecen invariables, mientras que los cuatro restantes codifican números negativos, manteniendo su orden creciente; así, el 4 codifica -4, el 5 codifica -3, el 6 codifica -2 y el 7 codifica -1. Sin embargo, la representación binaria ofrece una utilidad adicional, ya que el bit más significativo también indica el grupo (y el signo): es 0 para el primer grupo de no negativos y 1 para el segundo grupo de negativos. Las tablas de la derecha ilustran esta propiedad.

^El cálculo del complemento a dos binario de un número positivo consiste esencialmente en restar el número de ^2N . Pero como se puede ver en el ejemplo de tres bits y en el de cuatro bits ¹⁰⁰⁰² ( 23 ₎ , el número 2N no se puede representar en un sistema limitado a N bits, ya que está justo fuera del espacio de N bits (sin embargo , el número es el punto de referencia del "complemento a dos" en un sistema de N bits). Debido a esto, los sistemas con un máximo de N bits deben dividir la resta en dos operaciones: primero restar del número máximo en el sistema de N bits, es decir, 2N ^- 1 (este término en binario es en realidad un número simple que consta de 'todos unos', y se puede restar de él simplemente invirtiendo todos los bits del número, también conocido como la operación NOT bit a bit ) y luego sumar uno. Casualmente, ese número intermedio antes de sumarle uno también se utiliza en informática como otro método de representación de números con signo y se denomina complemento a uno (llamado así porque al sumar dicho número con el original se obtiene un total de unos).

En comparación con otros sistemas para representar números con signo (por ejemplo, el complemento a uno ), el complemento a dos tiene la ventaja de que las operaciones aritméticas fundamentales de suma , resta y multiplicación son idénticas a las de los números binarios sin signo (siempre que las entradas se representen con el mismo número de bits que la salida, y cualquier desbordamiento más allá de esos bits se descarte del resultado). Esta propiedad simplifica la implementación del sistema, especialmente para aritmética de alta precisión. Además, a diferencia de los sistemas de complemento a uno, el complemento a dos no tiene representación para el cero negativo y, por lo tanto, no sufre las dificultades asociadas. Por lo demás, ambos esquemas tienen la propiedad deseada de que el signo de los enteros se puede invertir tomando el complemento de su representación binaria, pero el complemento a dos tiene una excepción: el negativo más pequeño, como se puede ver en las tablas. ^{[ 4 ]}

El método de complementos se había utilizado durante mucho tiempo para realizar restas en máquinas sumadoras decimales y calculadoras mecánicas . John von Neumann sugirió el uso de la representación binaria en complemento a dos en su Primer Borrador de un Informe de 1945 sobre la propuesta EDVAC para una computadora digital electrónica de programa almacenado. ^{[ 5 ]} La EDSAC de 1949 , que se inspiró en el Primer Borrador , utilizó la representación en complemento a dos de enteros binarios negativos.

Muchos de los primeros ordenadores, incluidos el CDC 6600 , el LINC , el PDP-1 y el UNIVAC 1107, utilizan la notación de complemento a uno ; los descendientes del UNIVAC 1107, la serie UNIVAC 1100/2200 , continuaron haciéndolo. (Posteriormente, las máquinas DEC de 18 bits admitían tanto la suma en complemento a uno con la instrucción ADD como la aritmética en complemento a dos con la instrucción TAD). Las máquinas científicas de la serie IBM 700/7000 utilizan la notación de signo/magnitud, excepto para los registros de índice que están en complemento a dos. Entre los primeros ordenadores comerciales que almacenaban valores negativos en forma de complemento a dos se incluyen el English Electric DEUCE (1955) y el Digital Equipment Corporation PDP-5 (1963) y PDP-6 (1964). (Las computadoras de la familia PDP-5 y PDP-8 continuaron usando el mnemónico de ensamblador TAD para la suma en complemento a dos, aunque no existía la instrucción ADD en complemento a uno en esas computadoras). El System/360 , presentado en 1964 por IBM , entonces el actor dominante en la industria informática, convirtió el complemento a dos en la representación binaria más utilizada en la industria informática. La primera minicomputadora , la PDP-8 presentada en 1965, utiliza aritmética en complemento a dos, al igual que la Data General Nova de 1969 , la PDP-11 de 1970 y casi todas las minicomputadoras y microcomputadoras posteriores.

El sistema numérico de complemento a dos codifica los números positivos y negativos en una representación binaria. El peso de cada bit es una potencia de dos , excepto el bit más significativo , cuyo peso es el negativo de la potencia de dos correspondiente.

El valor w de un entero de N bits ${\displaystyle a_{N-1}a_{N-2}\dots a_{0}}$viene dada por la siguiente fórmula:

$${\displaystyle w=-a_{N-1}2^{N-1}+\sum _{i=0}^{N-2}a_{i}2^{i}}$$

El bit más significativo determina el signo del número y a veces se le llama bit de signo . A diferencia de la representación de signo y magnitud , el bit de signo también tiene el peso −(2 ^{N − 1} ) que se muestra arriba. Usando N bits, se pueden representar todos los enteros desde −(2 ^{N − 1} ) hasta 2 ^{N − 1} − 1 .

En la notación de complemento a dos, un número no negativo se representa mediante su representación binaria ordinaria ; en este caso, el bit más significativo es 0. Sin embargo, el rango de números representados no es el mismo que con los números binarios sin signo. Por ejemplo, un número sin signo de 8 bits puede representar los valores de 0 a 255 (11111111). En cambio, un número de 8 bits en complemento a dos solo puede representar enteros no negativos de 0 a 127 (01111111), ya que el resto de las combinaciones de bits con el bit más significativo como '1' representan los enteros negativos de -1 a -128.

La operación de complemento a dos es la operación inversa aditiva , por lo que los números negativos se representan mediante el complemento a dos del valor absoluto .

Al convertir un número en complemento a dos con una cantidad determinada de bits en uno con más bits (por ejemplo, al copiar de una variable de un byte a una de dos bytes), el bit más significativo debe repetirse en todos los bits adicionales. Algunos procesadores realizan esta operación con una sola instrucción; en otros, se debe usar una condición seguida de código para establecer los bits o bytes correspondientes.

De forma similar, al desplazar un número a la derecha, se debe conservar el bit más significativo, que contiene la información de signo. Sin embargo, al desplazarlo a la izquierda, se elimina un bit. Estas reglas preservan la semántica común de que los desplazamientos a la izquierda multiplican el número por dos y los desplazamientos a la derecha lo dividen por dos. No obstante, si el bit más significativo cambia de 0 a 1 (y viceversa), se produce un desbordamiento si el valor representa un entero con signo.

Tanto el desplazamiento como la duplicación de la precisión son importantes para algunos algoritmos de multiplicación. A diferencia de la suma y la resta, la extensión del ancho y el desplazamiento a la derecha se realizan de forma diferente para números con signo y sin signo.

Con una sola excepción, partiendo de cualquier número en representación de complemento a dos, si se invierten todos los bits y se suma 1, se obtiene la representación en complemento a dos del negativo de ese número.  El 12 positivo se convierte en el 12 negativo  ,  el 5 positivo en el  5 negativo, el cero en el cero (+ desbordamiento), etc.

Calcular el complemento a dos (negación) del número mínimo del rango no produce el efecto deseado de negarlo. Por ejemplo, el complemento a dos de −128 en un sistema de ocho bits es −128  , como se muestra en la tabla de la derecha . Aunque el resultado esperado al negar −128 es +128  , no existe una representación de +128 en un sistema de complemento a dos de ocho bits, por lo que resulta imposible representar la negación. El hecho de que el complemento a dos sea el mismo número se detecta como una condición de desbordamiento, ya que hubo un acarreo de entrada, pero no de salida, del bit más significativo.

Que un número distinto de cero sea igual a su propia negación se debe a que el cero es su propia negación y a que el número total de números es par. Prueba: existen 2^n − 1 números distintos de cero (un número impar). La negación dividiría los números distintos de cero en conjuntos de tamaño 2, pero esto daría como resultado un conjunto de números distintos de cero con cardinalidad par. Por lo tanto, al menos uno de los conjuntos tiene tamaño 1, es decir, un número distinto de cero es su propia negación.

La presencia del número más negativo puede provocar errores de programación inesperados, como que el resultado tenga un signo inesperado, o que genere una excepción de desbordamiento inesperada, o que provoque comportamientos completamente extraños. Por ejemplo,

• El operador de negación unaria no puede cambiar el signo de un número distinto de cero. Por ejemplo, −(−128)  ⟼  −128  (donde " ⟼ " se lee como "se convierte").
• una implementación de valor absoluto puede devolver un número negativo; ^{[ 8 ]} p. ej.,  abs(−128)  ⟼  −128  .

• Del mismo modo, la multiplicación por −1 puede no funcionar como se espera; por ejemplo, (−128) × (−1) ⟼ −128 .    
• La división por −1 puede provocar una excepción (como la que se produce al dividir por 0 ); ^{[ 9 ]} incluso calcular el resto (o módulo ) por −1 puede desencadenar esta excepción; ^{[ 10 ]} p. ej., (−128) ÷ (−1)  ⟼ [ crash ] ,   (−128) % (−1) ⟼ [ crash ] .     

En los lenguajes de programación C y C++ , los comportamientos mencionados anteriormente no están definidos y no solo pueden generar resultados extraños, sino que el compilador puede asumir que el programador se ha asegurado de que nunca se produzcan operaciones numéricas no definidas, y realizar inferencias a partir de esa suposición. ^{[ 10 ]} Esto permite varias optimizaciones, pero también da lugar a varios errores extraños en los programas que utilizan estos cálculos no definidos.

Este número más negativo en complemento a dos  a veces se denomina "el número extraño", porque es la única excepción. ^{[ 11 ] [ 12 ]} Aunque el número es una excepción, es un número válido en  los sistemas de complemento a dos regulares. Todas las operaciones aritméticas funcionan con él tanto como operando como (a menos que haya un desbordamiento) como resultado.

Dado un conjunto de todos los posibles valores de N bits, podemos asignar a la mitad inferior (por su valor binario) los enteros desde 0 hasta ( ^{2N − 1} − 1) inclusive ^, y a la mitad superior desde −2N ^{− 1 hasta} −1 inclusive. La mitad superior (de nuevo, por su valor binario) puede usarse para representar enteros negativos desde −2N ^{− 1} hasta −1 porque, bajo la suma módulo 2N ^, se comportan de la misma manera que esos enteros negativos. Es decir, como i + j mod 2N ⁼ i + ( j + ^2N ) mod ^2N , cualquier valor del conjunto { j + k 2N ^| k es ^un entero} puede usarse en lugar de j . ^{[ 13} ] 

Por ejemplo, con ocho bits, los bytes sin signo son del 0 al 255. Restando 256 de la mitad superior (del 128 al 255) se obtienen los bytes con signo del -128 al -1.

La relación con el complemento a dos se realiza al observar que 256 = 255 + 1 y (255 − x ) es el complemento a uno de x . 

 1111 1111 255. − 0101 1111 − 95. =========== ===== 1010 0000 (complemento a uno) 160. + 1 + 1 =========== ===== 1010 0001 (complemento a dos) 161. 

En un artículo clásico de HAKMEM publicado por el Laboratorio de IA del MIT en 1972, Bill Gosper señaló que la representación interna de una máquina, ya sea en complemento a dos o no, podía determinarse sumando las potencias sucesivas de dos. En un arrebato de imaginación, señaló que el resultado de realizar esto algebraicamente indicaba que "el álgebra se ejecuta en una máquina (el universo) que está en complemento a dos". ^{[ 18 ]}

La conclusión final de Gosper no necesariamente debe tomarse en serio, y es similar a una broma matemática . El paso crítico es "...110 = ...111  −  1", es decir, "2 X = X  −  1", y por lo tanto X  =  ...111  =  −1. Esto presupone un método por el cual una cadena infinita de 1s se considera un número, lo que requiere una extensión de los conceptos finitos de valor posicional en aritmética elemental . Es significativo ya sea como parte de una notación de complemento a dos para todos los enteros, como un número 2-ádico típico , o incluso como una de las sumas generalizadas definidas para la serie divergente de números reales 1 + 2 + 4 + 8 + ⋯ . ^{[ 19 ]} Los circuitos aritméticos digitales, idealizados para operar con cadenas de bits infinitas (que se extienden a potencias positivas de 2), producen suma y multiplicación 2-ádicas compatibles con la representación de complemento a dos. ^{[ 20 ]} La continuidad de las operaciones aritméticas binarias y bit a bit en la métrica 2-ádica también tiene cierta utilidad en criptografía. ^{[ 21 ]}

Para convertir un número con parte fraccionaria , como 0.0101, se deben convertir las unidades a decimal, comenzando de derecha a izquierda, como en una conversión normal. En este ejemplo, 0.0101 equivale a 5 en decimal. Cada dígito después de la coma decimal representa una fracción cuyo denominador es un múltiplo de 2. Así, el primero es 1/2, el segundo 1/4, y así sucesivamente. Habiendo calculado ya el valor decimal como se mencionó anteriormente, solo se utiliza el denominador del LSB (LSB = comenzando de derecha a izquierda). El resultado final de esta conversión es 5/16.

Por ejemplo, para que este método funcione, con el valor decimal 0.0110, no se debe considerar el último 0 desde la derecha. Por lo tanto, en lugar de calcular el valor decimal de 0110, calculamos el valor 011, que es 3 en decimal (si dejamos el 0 al final, el resultado habría sido 6, junto con el denominador 2 ⁴  =  16, que se reduce a 3/8). El denominador es 8, lo que da un resultado final de 3/8.

• Algoritmo de división , incluyendo la división restaurativa y no restaurativa en representaciones de complemento a dos.
• Desplazamiento binario

• Explicación del complemento a dos (Thomas Finley, 2000)
• Koren, Israel (2002). Algoritmos aritméticos informáticos . AK Peters. ISBN 1-56881-160-8.
• Flores, Ivan (1963). La lógica de la aritmética computacional . Prentice-Hall.

• Simulador JavaScript para multiplicador de matrices en complemento a dos