El complemento a dos es el método más común para representar números enteros con signo (positivo, negativo y cero) en las computadoras [1] y, de manera más general, valores binarios de punto fijo . El complemento a dos utiliza el dígito binario con el valor más alto como signo para indicar si el número binario es positivo o negativo; cuando el bit más significativo es 1 , el número se representa como negativo y cuando el bit más significativo es 0 , el número se representa como positivo. Como resultado, los números no negativos se representan como ellos mismos: 6 es 0110, cero es 0000 y -6 es 1010 (~6 + 1). Tenga en cuenta que, si bien la cantidad de bits binarios es fija durante todo el cálculo, por lo demás es arbitraria.
A diferencia del esquema de complemento a uno , el esquema de complemento a dos tiene solo una representación para el cero. Además, las implementaciones aritméticas se pueden utilizar tanto en números enteros con signo como sin signo [2] y difieren solo en las situaciones de desbordamiento de números enteros.
El siguiente es el procedimiento para obtener el complemento a dos de un número negativo dado en dígitos binarios:
Por ejemplo, para calcular el número decimal −6 en binario a partir del número 6 :
Para verificar que 1010 tiene efectivamente un valor de −6 , suma los valores de posición, pero resta el valor del signo del cálculo final. Debido a que el valor más significativo es el valor del signo, se debe restar para producir el resultado correcto: 1010 = − ( 1 ×2 3 ) + ( 0 ×2 2 ) + ( 1 ×2 1 ) + ( 0 ×2 0 ) = 1 ×−8 + 0 + 1 ×2 + 0 = −6.
Tenga en cuenta que los pasos 2 y 3 juntos son un método válido para calcular el inverso aditivo de cualquier número entero (positivo o negativo) donde tanto la entrada como la salida están en formato de complemento a dos. Una alternativa para calcular es usar la resta . Vea a continuación la resta de números enteros en formato de complemento a dos.
El complemento a dos es un ejemplo de complemento de base . El 'dos' en el nombre se refiere al término que, expandido completamente en un sistema de N bits, es en realidad "dos elevado a N" - 2 N (el único caso en el que se produciría exactamente 'dos' en este término es N = 1 , por lo que para un sistema de 1 bit, pero estos no tienen capacidad para un signo y un cero), y es solo este término completo con respecto al cual se calcula el complemento . Como tal, 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 N.
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, utilizando binario con números de hasta tres bits (por lo que N = 3 y 2 N = 2 3 = 8 = 1000 2 , donde ' 2 ' indica una representación binaria), un complemento a dos para el número 3 ( 011 2 ) es 5 ( 101 2 ), porque sumado al original da 2 3 = 1000 2 = 011 2 + 101 2 . Cuando se emplea esta correspondencia para representar números negativos, significa efectivamente, utilizando una analogía con los dígitos decimales y un espacio numérico que solo permite ocho números no negativos del 0 al 7, dividir el espacio numérico en dos conjuntos: los primeros cuatro de los números 0 1 2 3 permanecen iguales, mientras que los cuatro restantes codifican números negativos, manteniendo su orden creciente, por lo que 4 codifica -4, 5 codifica -3, 6 codifica -2 y 7 codifica -1. Sin embargo, una representación binaria tiene una utilidad adicional, porque 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 a la derecha ilustran esta propiedad.
El cálculo del complemento binario a dos de un número positivo significa esencialmente restar el número de 2 N . Pero como se puede ver para el ejemplo de tres bits y el 1000 2 ( 2 3 ) de cuatro bits, el número 2 N no será representable en un sistema limitado a N bits, ya que está justo fuera del espacio de N bits (el número es, sin embargo, 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, 2 N -1 (este término en binario es en realidad un número simple que consiste en "todos 1", y se puede restar de él simplemente invirtiendo todos los bits en el número, también conocida como la operación NOT bit a bit ) y luego sumar el uno. Por coincidencia, ese número intermedio antes de sumar el uno también se utiliza en informática como otro método de representación de números con signo y se llama complemento de unos (llamado así porque al sumar ese número con el original se obtienen "todos 1").
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 en el mismo número de bits que la salida y cualquier desbordamiento más allá de esos bits se descarte del resultado). Esta propiedad hace que el sistema sea más simple de implementar, especialmente para aritmética de mayor 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 sus dificultades asociadas. De lo contrario, ambos esquemas tienen la propiedad deseada de que el signo de los números 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 bajo, como se puede ver en las tablas. [4]
El método de complementos se ha 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 de complemento a dos en su Primer borrador de un informe de 1945 sobre la propuesta EDVAC para una computadora digital electrónica con programa almacenado. [5] El EDSAC de 1949 , que se inspiró en el Primer borrador , utilizó la representación de complemento a dos de números 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. Las máquinas científicas de la serie IBM 700/7000 utilizan la notación de signo/magnitud, excepto los registros de índice que son complemento a dos. Los primeros ordenadores comerciales que almacenaban valores negativos en forma de complemento a dos incluyen el English Electric DEUCE (1955) y los Digital Equipment Corporation PDP-5 (1963) y PDP-6 (1964). El System/360 , presentado en 1964 por IBM , entonces el actor dominante en la industria informática, hizo del complemento a dos la representación binaria más utilizada en la industria informática. La primera minicomputadora, la PDP-8 introducida en 1965, utiliza aritmética de 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.
Un sistema numérico en complemento a dos codifica números positivos y negativos en una representación numérica 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 viene dado por la siguiente fórmula:
El bit más significativo determina el signo del número y a veces se lo denomina bit de signo . A diferencia de la representación por signo y magnitud , el bit de signo también tiene el peso −(2 N − 1 ) que se muestra arriba. Con N bits, se pueden representar todos los números 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). Sin embargo, un número de 8 bits de complemento a dos solo puede representar números enteros no negativos de 0 a 127 (01111111), porque el resto de las combinaciones de bits con el bit más significativo como '1' representan los números 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 .
Para obtener el complemento a dos de un número binario negativo, todos los bits se invierten, o se "voltean", utilizando la operación NOT bit a bit ; luego, el valor de 1 se suma al valor resultante, ignorando el desbordamiento que ocurre cuando se toma el complemento a dos de 0.
Por ejemplo, utilizando 1 byte (=8 bits), el número decimal 5 se representa mediante
El bit más significativo (el bit más a la izquierda en este caso) es 0, por lo que el patrón representa un valor no negativo. Para convertir a −5 en notación de complemento a dos, primero se invierten todos los bits, es decir: 0 se convierte en 1 y 1 se convierte en 0:
En este punto, la representación es el complemento a uno del valor decimal −5. Para obtener el complemento a dos, se suma 1 al resultado, obteniéndose:
El resultado es un número binario con signo que representa el valor decimal −5 en forma de complemento a dos. El bit más significativo es 1, por lo que el valor representado es negativo.
El complemento a dos de un número negativo es el valor positivo correspondiente, excepto en el caso especial del número más negativo . Por ejemplo, al invertir los bits de −5 (arriba) se obtiene:
Y sumando uno obtenemos el valor final:
De la misma manera, el complemento a dos de cero es cero: al invertir, todos los unos se convierten en ceros y al sumar uno, los unos vuelven a ser ceros (ya que se ignora el desbordamiento).
El complemento a dos del número más negativo representable (por ejemplo, un uno como bit más significativo y todos los demás bits cero) es él mismo. Por lo tanto, hay un número negativo "adicional" para el cual el complemento a dos no da la negación, consulte el § Número más negativo a continuación.
La suma de un número y su complemento a uno es una palabra de N bits con todos los bits 1, que es (leyendo como un número binario sin signo) 2 N − 1 . Luego, sumar un número a su complemento a dos da como resultado que los N bits más bajos se establezcan en 0 y el bit de acarreo en 1, donde este último tiene el peso (leyendo como un número binario sin signo) de 2 N . Por lo tanto, en la aritmética binaria sin signo, el valor del número negativo en complemento a dos x * de un x positivo satisface la igualdad x * = 2 N − x . [a]
Por ejemplo, para encontrar la representación de cuatro bits de −5 (los subíndices indican la base de la representación ):
Por lo tanto, con N = 4 :
El cálculo se puede realizar íntegramente en base 10, convirtiendo al final a base 2:
Un atajo para convertir manualmente un número binario en su complemento a dos es empezar por el bit menos significativo (LSB) y copiar todos los ceros, trabajando desde el LSB hacia el bit más significativo (MSB) hasta llegar al primer 1; luego, copiar ese 1 e invertir todos los bits restantes (dejar el MSB como 1 si el número inicial estaba en representación de signo y magnitud). Este atajo permite a una persona convertir un número en su complemento a dos sin formar primero su complemento a uno. Por ejemplo: en la representación del complemento a dos, la negación de "0011 1100" es "1100 0 100 ", donde los dígitos subrayados no se modificaron con la operación de copia (mientras que el resto de los dígitos se invirtieron).
En los circuitos informáticos, este método no es más rápido que el método de "complementar y sumar uno"; ambos métodos requieren trabajar secuencialmente de derecha a izquierda, propagando los cambios lógicos. El método de complementar y sumar uno se puede acelerar con un circuito sumador estándar de acarreo anticipado ; el método de LSB a MSB se puede acelerar con una transformación lógica similar.
Al convertir un número en complemento a dos con una cierta cantidad de bits en uno con más bits (por ejemplo, al copiar de una variable de un byte a una variable de dos bytes), el bit más significativo debe repetirse en todos los bits adicionales. Algunos procesadores hacen esto en una sola instrucción; en otros procesadores, se debe utilizar un condicional seguido de un código para establecer los bits o bytes relevantes.
De manera similar, cuando un número se desplaza hacia la derecha, se debe mantener el bit más significativo, que contiene la información del signo. Sin embargo, cuando se desplaza hacia la izquierda, se desplaza un bit hacia afuera. Estas reglas conservan la semántica común de que los desplazamientos hacia la izquierda multiplican el número por dos y los desplazamientos hacia la derecha lo dividen por dos. Sin embargo, si el bit más significativo cambia de 0 a 1 (y viceversa), se dice que se produce un desbordamiento en el caso de que el valor represente un entero con signo.
Tanto el desplazamiento como la duplicación de la precisión son importantes para algunos algoritmos de multiplicación. Tenga en cuenta que, a diferencia de la suma y la resta, la extensión del ancho y el desplazamiento a la derecha se realizan de manera diferente para números con y sin signo.
Con una sola excepción, comenzando con 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 de complemento a dos del negativo de ese número. 12 positivo se convierte en 12 negativo, 5 positivo se convierte en 5 negativo, cero se convierte en cero (+ desbordamiento), etc.
Tomar el complemento a dos (negación) del número mínimo en el rango no tendrá el efecto deseado de negar el número. 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 de negar −128 es +128, no hay representación de +128 con un sistema de complemento a dos de ocho bits y, por lo tanto, de hecho es imposible representar la negación. Tenga en cuenta que el complemento a dos es el mismo número que se detecta como una condición de desbordamiento, ya que hubo un acarreo hacia dentro, pero no hacia fuera, del bit más significativo.
El hecho de que un número distinto de cero sea igual a su propia negación es forzado por el hecho de que cero es su propia negación y que el número total de números es par. Demostración: hay 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 que el conjunto de números distintos de cero tuviera 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 en los que el resultado tenga un signo inesperado, o provoque una excepción de desbordamiento inesperada, o provoque comportamientos completamente extraños. Por ejemplo,
En los lenguajes de programación C y C++ , los comportamientos anteriores no están definidos y no solo pueden devolver resultados extraños, sino que el compilador tiene la libertad de asumir que el programador se ha asegurado de que nunca ocurran operaciones numéricas indefinidas y hacer inferencias a partir de esa suposición. [8] Esto permite una serie de optimizaciones, pero también conduce a una serie de errores extraños en programas con estos cálculos indefinidos.
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. [9] [10] 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 y (a menos que haya un desbordamiento) como resultado.
Dado un conjunto de todos los valores posibles de N bits, podemos asignar la mitad inferior (por el valor binario) a los números enteros de 0 a (2 N − 1 − 1) inclusive y la mitad superior a −2 N − 1 a −1 inclusive. La mitad superior (de nuevo, por el valor binario) se puede utilizar para representar números enteros negativos de −2 N − 1 a −1 porque, bajo la adición módulo 2 N se comportan de la misma manera que esos números enteros negativos. Es decir que, debido a que i + j mod 2 N = i + ( j + 2 N ) mod 2 N , cualquier valor en el conjunto { j + k 2 N | k es un número entero } se puede utilizar en lugar de j . [11]
Por ejemplo, con ocho bits, los bytes sin signo son de 0 a 255. Restar 256 de la mitad superior (128 a 255) da como resultado los bytes con signo de −128 a −1.
La relación con el complemento a dos se realiza observando que 256 = 255 + 1 , y (255 − x ) es el complemento a uno de x .
Por ejemplo, un número de 8 bits solo puede representar cada entero desde −128. hasta 127., inclusive, ya que (2 8 − 1 = 128.) . −95. módulo 256. es equivalente a 161. ya que
1111 1111 255. − 0101 1111 − 95. =========== ===== 1010 0000 (complemento a uno) 160. + 1 + 1 =========== ===== 1010 0001 (complemento a dos) 161.
Básicamente, el sistema representa los números enteros negativos contando hacia atrás y dando la vuelta a . El límite entre números positivos y negativos es arbitrario, pero por convención todos los números negativos tienen un bit más a la izquierda ( bit más significativo ) de uno. Por lo tanto, el número de cuatro bits más positivo es 0111 (7.) y el más negativo es 1000 (−8.). Debido al uso del bit más a la izquierda como bit de signo, el valor absoluto del número más negativo (|−8.| = 8.) es demasiado grande para representarlo. Negar un número en complemento a dos es simple: invierte todos los bits y suma uno al resultado. Por ejemplo, al negar 1111, obtenemos 0000 + 1 = 1 . Por lo tanto, 1111 en binario debe representar −1 en decimal. [12]
El sistema es útil para simplificar la implementación de operaciones aritméticas en hardware informático. Sumar 0011 (3.) a 1111 (−1.) parece dar en un primer momento la respuesta incorrecta de 10010. Sin embargo, el hardware puede simplemente ignorar el bit más a la izquierda para dar la respuesta correcta de 0010 (2.). Deben seguir existiendo comprobaciones de desbordamiento para detectar operaciones como la suma de 0100 y 0100.
Por lo tanto, el sistema permite la suma de operandos negativos sin un circuito de resta o un circuito que detecte el signo de un número. Además, ese circuito de suma también puede realizar la resta tomando el complemento a dos de un número (ver más abajo), lo que solo requiere un ciclo adicional o su propio circuito sumador. Para realizar esto, el circuito simplemente funciona como si hubiera un bit adicional de 1 en el extremo izquierdo.
La suma de números en complemento a dos no requiere un procesamiento especial, incluso si los operandos tienen signos opuestos; el signo del resultado se determina automáticamente. Por ejemplo, sumar 15 y −5:
0000 1111 (15) + 1111 1011 (−5) =========== 0000 1010 (10)
O el cálculo de 5 − 15 = 5 + (−15):
0000 0101 ( 5) + 1111 0001 (−15) =========== 1111 0110 (−10)
Este proceso depende de la restricción a 8 bits de precisión; se ignora un acarreo al noveno bit más significativo (inexistente), lo que da como resultado un resultado aritméticamente correcto de 10 10 .
Los dos últimos bits de la fila de acarreo (que se leen de derecha a izquierda) contienen información vital: si el cálculo resultó en un desbordamiento aritmético , un número demasiado grande para que el sistema binario lo represente (en este caso, mayor que 8 bits). Existe una condición de desbordamiento cuando estos dos últimos bits son diferentes entre sí. Como se mencionó anteriormente, el signo del número está codificado en el MSB del resultado.
En otras palabras, si los dos bits de acarreo de la izquierda (los que están en el extremo izquierdo de la fila superior en estos ejemplos) son ambos 1 o ambos 0, el resultado es válido; si los dos bits de acarreo de la izquierda son "1 0" o "0 1", se ha producido un desbordamiento de signo. Convenientemente, una operación XOR en estos dos bits puede determinar rápidamente si existe una condición de desbordamiento. Como ejemplo, considere la suma de 4 bits con signo de 7 y 3:
0111 (llevar) 0111 (7) + 0011 (3) ====== 1010 (−6) ¡no válido!
En este caso, los dos bits de acarreo más a la izquierda (MSB) son "01", lo que significa que hubo un desbordamiento de la suma en complemento a dos. Es decir, 1010 2 = 10 10 está fuera del rango permitido de −8 a 7. El resultado sería correcto si se tratara como un entero sin signo.
En general, se pueden sumar dos números cualesquiera de N bits sin que se produzca un desbordamiento, extendiendo primero ambos signos a N + 1 bits y, a continuación, sumándolos como se indicó anteriormente. El resultado de N + 1 bits es lo suficientemente grande como para representar cualquier suma posible ( el complemento a dos de N = 5 puede representar valores en el rango de −16 a 15), por lo que nunca se producirá un desbordamiento. Entonces es posible, si se desea, "truncar" el resultado de nuevo a N bits mientras se conserva el valor si y solo si el bit descartado es una extensión de signo adecuada de los bits de resultado retenidos. Esto proporciona otro método para detectar el desbordamiento (que es equivalente al método de comparar los bits de acarreo), pero que puede ser más fácil de implementar en algunas situaciones, porque no requiere acceso a los elementos internos de la suma.
Las computadoras suelen utilizar el método de complementos para implementar la resta. El uso de complementos para la resta está estrechamente relacionado con el uso de complementos para representar números negativos, ya que la combinación permite todos los signos de operandos y resultados; la resta directa también funciona con números en complemento a dos. Al igual que la suma, la ventaja de utilizar el complemento a dos es la eliminación de examinar los signos de los operandos para determinar si se necesita una suma o una resta. Por ejemplo, restar −5 de 15 es en realidad sumar 5 a 15, pero esto queda oculto por la representación en complemento a dos:
11110 000 (préstamo) 0000 1111 (15) − 1111 1011 (−5) =========== 0001 0100 (20)
El desbordamiento se detecta de la misma manera que la suma, examinando los dos bits más a la izquierda (los más significativos) de los préstamos; se ha producido un desbordamiento si son diferentes.
Otro ejemplo es una operación de resta donde el resultado es negativo: 15 − 35 = −20:
11100 000 (préstamo) 0000 1111 (15) − 0010 0011 (35) =========== 1110 1100 (−20)
En cuanto a la suma, el desbordamiento en la resta se puede evitar (o detectar después de la operación) ampliando primero el signo de ambas entradas con un bit adicional.
El producto de dos números de N bits requiere 2 N bits para contener todos los valores posibles. [13]
Si la precisión de los dos operandos que utilizan el complemento a dos se duplica antes de la multiplicación, la multiplicación directa (descartando cualquier bit sobrante más allá de esa precisión) proporcionará el resultado correcto. [14] Por ejemplo, tomemos 6 × (−5) = −30 . Primero, la precisión se extiende de cuatro bits a ocho. Luego, los números se multiplican, descartando los bits más allá del octavo bit (como se muestra con " x "):
00000110 (6) * 11111011 (−5) ============ 110 1100 00000 110000 1100000 11000000 x10000000 + xx00000000 ============ xx11100010
Esto es muy ineficiente; al duplicar la precisión de antemano, todas las sumas deben ser de doble precisión y se necesitan al menos el doble de productos parciales que para los algoritmos más eficientes implementados en la actualidad en las computadoras. Algunos algoritmos de multiplicación están diseñados para el complemento a dos, en particular el algoritmo de multiplicación de Booth . Los métodos para multiplicar números con signo-magnitud no funcionan con números en complemento a dos sin adaptación. Por lo general, no hay un problema cuando el multiplicando (el que se suma repetidamente para formar el producto) es negativo; el problema es configurar correctamente los bits iniciales del producto cuando el multiplicador es negativo. Son comunes dos métodos para adaptar algoritmos para manejar números en complemento a dos:
Como ejemplo del segundo método, tomemos el algoritmo común de suma y desplazamiento para la multiplicación. En lugar de desplazar los productos parciales hacia la izquierda como se hace con lápiz y papel, el producto acumulado se desplaza hacia la derecha, hacia un segundo registro que contendrá la mitad menos significativa del producto. Como los bits menos significativos no se modifican una vez que se calculan, las sumas pueden ser de precisión simple, acumulándose en el registro que contendrá la mitad más significativa del producto. En el siguiente ejemplo, al multiplicar nuevamente 6 por −5, los dos registros y el bit de signo extendido están separados por "|":
0 0110 (6) (multiplicando con bit de signo extendido) × 1011 (−5) (multiplicador) =|====|==== 0|0110|0000 (primer producto parcial (el bit más a la derecha es 1)) 0|0011|0000 (desplazamiento a la derecha, conservando el bit de signo extendido) 0|1001|0000 (agrega el segundo producto parcial (el siguiente bit es 1)) 0|0100|1000 (desplazamiento a la derecha, conservando el bit de signo extendido) 0|0100|1000 (agrega el tercer producto parcial: 0, por lo que no hay cambios) 0|0010|0100 (desplazamiento a la derecha, conservando el bit de signo extendido) 1|1100|0100 (restar el último producto parcial ya que es del bit de signo) 1|1110|0010 (desplazamiento a la derecha, conservando el bit de signo extendido) |1110|0010 (descarta el bit de signo extendido, lo que da la respuesta final, −30)
La comparación se implementa a menudo con una resta ficticia, donde se verifican los indicadores en el registro de estado de la computadora , pero se ignora el resultado principal. El indicador cero indica si dos valores comparados son iguales. Si el o exclusivo de los indicadores de signo y desbordamiento es 1, el resultado de la resta fue menor que cero; de lo contrario, el resultado fue cero o mayor. Estas verificaciones se implementan a menudo en las computadoras en instrucciones de bifurcación condicional .
Los números binarios sin signo se pueden ordenar mediante un orden lexicográfico simple , donde el valor de bit 0 se define como menor que el valor de bit 1. Para los valores de complemento a dos, el significado del bit más significativo se invierte (es decir, 1 es menor que 0).
El siguiente algoritmo (para una arquitectura de complemento a dos de n bits) establece el registro de resultados R en −1 si A < B, en +1 si A > B y en 0 si A y B son iguales:
// comparación inversa del bit de signosi A ( n - 1 ) == 0 y B ( n - 1 ) == 1 entonces devuelve + 1 de lo contrario si A ( n - 1 ) == 1 y B ( n - 1 ) == 0 entonces devuelve - 1 fin // comparación de los bits restantes para i = n - 2 ... 0 hacer si A ( i ) == 0 y B ( i ) == 1 entonces devolver - 1 de lo contrario si A ( i ) == 1 y B ( i ) == 0 entonces devolver + 1 fin fin devolver 0 En un HAKMEM clásico publicado por el Laboratorio de IA del MIT en 1972, Bill Gosper señaló que si la representación interna de una máquina era o no complemento a dos se podía determinar sumando las potencias sucesivas de dos. En un vuelo de su imaginación, señaló que el resultado de hacer esto algebraicamente indicaba que "el álgebra se ejecuta en una máquina (el universo) que es complemento a dos". [16]
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 1 se considera un número, lo que requiere una extensión de los conceptos de valor posicional finito en aritmética elemental. Tiene sentido ya sea como parte de una notación de complemento a dos para todos los números 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 + ··· . [17] Los circuitos aritméticos digitales, idealizados para operar con cadenas de bits infinitas (que se extienden a potencias positivas de 2), producen sumas y multiplicaciones 2-ádicas compatibles con la representación de complemento a dos. [18] La continuidad de las operaciones aritméticas binarias y bit a bit en la métrica 2-ádica también tiene algún uso en criptografía. [19]
Para convertir un número con una parte fraccionaria, como .0101, se deben convertir los 1 comenzando de derecha a izquierda a decimal como en una conversión normal. En este ejemplo, 0101 es igual a 5 en decimal. Cada dígito después del punto flotante representa una fracción donde el denominador es un múltiplo de 2. Por lo tanto, el primero es 1/2, el segundo es 1/4 y así sucesivamente. Habiendo calculado ya el valor decimal como se mencionó anteriormente, solo se utiliza el denominador del LSB (LSB = comenzando desde la derecha). El resultado final de esta conversión es 5/16.
Por ejemplo, si se tiene el valor flotante de 0,0110 para que este método funcione, 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 (al dejar el 0 al final, el resultado hubiera sido 6, junto con el denominador 2 4 = 16, que se reduce a 3/8). El denominador es 8, lo que da un resultado final de 3/8.