El complemento a dos es el método más común para representar números enteros con signo (positivos, negativos y cero) en computadoras, [1] y, más generalmente, valores binarios de punto fijo . El complemento a dos utiliza el dígito binario con el mayor valor posicional como signo para indicar si el número binario es positivo o negativo. Cuando el bit más significativo es 1 , el número tiene signo negativo; y cuando el bit más significativo es 0 el número tiene signo positivo.
A diferencia del esquema de complemento a uno , el esquema de complemento a dos tiene una sola representación para el cero. Además, las implementaciones aritméticas se pueden utilizar tanto en enteros con signo como sin signo [2] y difieren sólo en las situaciones de desbordamiento de enteros.
El complemento a dos de un número entero se calcula mediante:
Por ejemplo, para calcular el número decimal −6 en binario a partir del número 6 :
Para verificar que 1010 efectivamente tiene un valor de −6 , suma los valores posicionales, 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 utilizar la resta . Consulte 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 [ cita necesaria ] que, expandido completamente en un sistema de N bits, en realidad es "dos elevado a N" - 2 N (el único caso en el que exactamente 'dos' sería producido 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 sólo este término completo respecto del 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 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 (entonces 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 esta correspondencia se emplea para representar números negativos, significa efectivamente, usando una analogía con dígitos decimales y un espacio numérico que solo permite ocho números no negativos del 0 al 7, dividiendo el espacio numérico en dos conjuntos: los primeros cuatro de los 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 de la derecha ilustran esta propiedad.
El cálculo del complemento binario a dos de un número positivo significa esencialmente restar el número del 2 N. Pero como se puede ver en el ejemplo de tres bits y el 1000 2 ( 2 3 ) de cuatro bits , el número 2 N en sí mismo no será representable en un sistema limitado a N bits, ya que está justo fuera del espacio de N bits ( el número es, no obstante, 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 consta de ' todos los unos', y se puede restar simplemente invirtiendo todos los bits en el número (también conocida como operación NOT bit a bit ) y luego sumando el uno. Casualmente, ese número intermedio antes de sumar el uno también se usa en informática como otro método de representación de números con signo y se llama complemento a unos (llamado así porque al sumar dicho número con el original se obtienen "todos unos").
En comparación con otros sistemas para representar números con signo ( por ejemplo, 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 estén representadas en el mismo número de bits que la salida, y cualquier desbordamiento más allá de esos bits se descarta del resultado). Esta propiedad hace que el sistema sea más sencillo 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 las dificultades asociadas. Por lo demás, 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 mínimo negativo, como se puede ver en las tablas. [3]
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 con programa almacenado. [4] El EDSAC de 1949 , que se inspiró en el Primer Borrador , utilizó la representación en complemento a dos de enteros binarios negativos.
Muchas de las primeras computadoras, incluidas la CDC 6600 , la LINC , la PDP-1 y la UNIVAC 1107, usaban notación en complemento de unos ; 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 notación de signos/magnitud, excepto los registros de índice que son complemento a dos. Las primeras computadoras comerciales que almacenan valores negativos en forma de complemento a dos incluyen la English Electric DEUCE (1955) y la Digital Equipment Corporation PDP-5 (1963) y PDP-6 (1964). El System/360 , introducido 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 introducida 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.
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 correspondiente potencia de dos.
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 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 números enteros desde −(2 N − 1 ) hasta 2 N − 1 − 1 .
En notación en 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 del 0 al 255 (11111111). Sin embargo, un número de 8 bits en complemento a dos solo puede representar números enteros no negativos del 0 al 127 (01111111), porque el resto de las combinaciones de bits con el bit más significativo como '1' representan los números enteros negativos −1 a −128.
La operación en 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 "invierten" utilizando la operación NOT bit a bit ; Luego, el valor de 1 se suma al valor resultante, ignorando el desbordamiento que se produce al tomar el complemento a dos de 0.
Por ejemplo, usando 1 byte (=8 bits), el número decimal 5 se representa por
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 en 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 unos del valor decimal −5. Para obtener el complemento a dos, se suma 1 al resultado, dando:
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 da el valor final:
Del mismo modo, el complemento a dos de cero es cero: la inversión da todos unos y la suma de uno cambia los unos de nuevo a 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 "extra" para el cual el complemento a dos no da la negación, consulte la sección Número más negativo a continuación.
La suma de un número y su complemento a unos es una palabra de N bits con todos los bits 1, que es (leído como un número binario sin signo) 2 N − 1 . Luego, agregar un número a su complemento a dos da como resultado los N bits más bajos establecidos en 0 y el bit de acarreo 1, donde este último tiene el peso (leído 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 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 comenzar en el bit menos significativo (LSB) y copiar todos los ceros, trabajando desde LSB hacia el bit más significativo (MSB) hasta alcanzar el primer 1; luego copie ese 1 y voltee todos los bits restantes (deje 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 complemento a dos sin formar primero el complemento a uno. Por ejemplo: en la representación en complemento a dos, la negación de "0011 1100" es "1100 0 100 ", donde los dígitos subrayados no se modificaron mediante 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 agregar uno"; Ambos métodos requieren trabajar secuencialmente de derecha a izquierda, propagando cambios lógicos. El método de complementar y agregar uno puede acelerarse mediante un circuito sumador de anticipación de acarreo estándar; El método LSB hacia MSB se puede acelerar mediante una transformación lógica similar.
Al convertir un número en complemento a dos con un cierto número 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 poco hacia afuera. 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 dividen el número 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 cambiar como duplicar 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 la representación en 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 12 negativo, el 5 positivo se convierte en 5 negativo, el 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 al negar −128 es +128, no hay representación de +128 con un sistema de complemento a dos de ocho bits y, por lo tanto, es imposible representar la negación. Tenga en cuenta que 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.
Tener un número distinto de cero igual a su propia negación se ve obligado por el hecho de que el cero es su propia negación y que el número total de números es par. Prueba: 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. Entonces 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 tiene un signo inesperado, una excepción de desbordamiento inesperada o comportamientos completamente extraños. Por ejemplo,
En los lenguajes de programación C y C++ , los comportamientos anteriores no están definidos y no sólo pueden arrojar resultados extraños, sino que el compilador es libre 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. [7] 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 llama "el número extraño" , porque es la única excepción. [8] [9] Aunque el número es una excepción, es un número válido en sistemas regulares en complemento a dos. Todas las operaciones aritméticas funcionan con él 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) como los números enteros de 0 a (2 N − 1 − 1) inclusive y la mitad superior como −2 N − 1. a −1 inclusive. La mitad superior (nuevamente, por el valor binario) se puede usar para representar números enteros negativos de −2 N − 1 a −1 porque, bajo la suma 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 . [10]
Por ejemplo, con ocho bits, los bytes sin signo son de 0 a 255. Restando 256 de la mitad superior (128 a 255) se obtienen 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 número entero a partir de −128. a 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.
Fundamentalmente, el sistema representa números enteros negativos contando hacia atrás y girando alrededor . 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. [11]
El sistema es útil para simplificar la implementación de la aritmética en el hardware de una computadora. Agregar 0011 (3.) a 1111 (−1.) al principio parece dar 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.). Aún deben existir comprobaciones de desbordamiento para detectar operaciones como la suma de 0100 y 0100.
Por 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 restas 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 1 adicional en el extremo izquierdo.
Sumar números en complemento a dos no requiere ningún procesamiento especial incluso si los operandos tienen signos opuestos; el signo del resultado se determina automáticamente. Por ejemplo, sumando 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 restringir a 8 bits de precisión; se ignora un acarreo al (inexistente) noveno bit más significativo, lo que da como resultado el 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 otros términos, 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 (MSB) del extremo izquierdo son "01", lo que significa que hubo un desbordamiento de 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, dos números cualesquiera de N bits se pueden sumar sin desbordamiento, extendiendo primero ambos con signo a N + 1 bits y luego sumando como se indicó anteriormente. El resultado de N + 1 bits es lo suficientemente grande como para representar cualquier suma posible ( N = 5 el complemento a dos 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 a N bits conservando el valor si y sólo 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 las partes internas 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 es necesaria la suma o la 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 (pedir prestado) 0000 1111 (15) − 1111 1011 (−5) ============ 0001 0100 (20)
El desbordamiento se detecta de la misma manera que para la suma, examinando los dos bits más a la izquierda (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 (pedir prestado) 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) extendiendo primero el signo ambas entradas en un bit adicional.
El producto de dos números de N bits requiere 2 N bits para contener todos los valores posibles. [12]
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 exceso de bits más allá de esa precisión) proporcionará el resultado correcto. [13] Por ejemplo, tome 6 × (−5) = −30 . En primer lugar, la precisión se amplía de cuatro bits a ocho. Luego se multiplican los números, descartando los bits más allá del octavo bit (como lo muestra " 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 adiciones deben ser de doble precisión y se necesitan al menos el doble de productos parciales que para los algoritmos más eficientes realmente implementados 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 de signo y magnitud no funcionan con números en complemento a dos sin adaptación. Generalmente no hay 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 productos parciales hacia la izquierda como se hace con lápiz y papel, el producto acumulado se desplaza hacia la derecha, a un segundo registro que eventualmente contendrá la mitad menos significativa del producto. Dado que los bits menos significativos no se modifican una vez calculados, las sumas pueden ser de precisión simple, acumulándose en el registro que eventualmente contendrá la mitad más significativa del producto. En el siguiente ejemplo, multiplicando 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 (agregue 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 (agregar 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 (resta 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, dando la respuesta final, −30)
La comparación a menudo se implementa con una resta ficticia, donde se verifican las banderas en el registro de estado de la computadora, pero se ignora el resultado principal. La bandera 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 comprobaciones a menudo se implementan en computadoras en instrucciones de rama condicional .
Los números binarios sin signo se pueden ordenar mediante un orden lexicográfico simple , donde el valor del bit 0 se define como menor que el valor del bit 1. Para los valores en 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 resultado R en −1 si A < B, en +1 si A > B y en 0 si A y B son iguales:
// comparación invertida del bit de signosi A ( n - 1 ) == 0 y B ( n - 1 ) == 1 entonces regresa + 1 si no, si A ( n - 1 ) == 1 y B ( n - 1 ) == 0 luego regresa - 1 final // comparación de bits restantes para i = n - 2 ... 0 , haga si A ( i ) == 0 y B ( i ) == 1 , luego devuelva - 1 ; de lo contrario , si A ( i ) == 1 y B ( i ) == 0 , luego devuelva + 1 fin fin retorno 0 En un HAKMEM clásico publicado por el MIT AI Lab en 1972, Bill Gosper señaló que si la representación interna de una máquina era complemento a dos se podía determinar sumando las potencias sucesivas de dos. En un vuelo de fantasía, observó que el resultado de hacer esto algebraicamente indicaba que "el álgebra se ejecuta en una máquina (el universo) que es complemento a dos". [15]
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 tanto X = ...111 = −1. Esto presupone un método mediante el cual una cadena infinita de unos se considera un número, lo que requiere una extensión de los conceptos de valor posicional finito en la aritmética elemental. Tiene significado como parte de una notación en 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 + ·· · . [16] 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 en complemento a dos. [17] La continuidad de las operaciones aritméticas binarias y bit a bit en métrica 2-ádica también tiene algún uso en criptografía. [18]
Para convertir un número con una parte fraccionaria, como .0101, se deben convertir comenzando de derecha a izquierda las unidades 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 multiplicador de 2. Entonces, 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, teniendo el valor flotante de .0110 para que este método funcione, no se debe considerar el último 0 desde la derecha. Así, en lugar de calcular el valor decimal de 0110, calculamos el valor 011, que es 3 en decimal (dejando 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, dando un resultado final de 3/8.