¿Qué es el “Complemento 2”?

Estoy en un curso de sistemas informáticos y he estado luchando , en parte, con Two’s Complement . Quiero entenderlo, pero todo lo que he leído no ha traído la imagen para mí. He leído el artículo de Wikipedia y varios otros artículos, incluido mi libro de texto .

Por lo tanto, quería comenzar esta publicación wiki de la comunidad para definir qué es Complemento de dos, cómo usarlo y cómo puede afectar los números durante operaciones como conversiones (de firmado a no firmado y viceversa), operaciones de bits y operaciones de cambio de bits .

Lo que espero es una definición clara y concisa que sea fácil de entender para un progtwigdor.

El complemento a dos es una forma inteligente de almacenar enteros para que los problemas matemáticos comunes sean muy simples de implementar.

Para entender, debes pensar en los números en binario.

Básicamente dice,

  • para cero, use todos los 0.
  • para enteros positivos, comience a contar, con un máximo de 2 (número de bits – 1) -1.
  • para enteros negativos, haz exactamente lo mismo, pero cambia el rol de los 0 y los 1 (así que en vez de comenzar con 0000, comienza con 1111 – esa es la parte del “complemento”).

Probémoslo con un mini byte de 4 bits (lo llamaremos un mordisco – 1/2 byte).

  • 0000 – cero
  • 0001 – uno
  • 0010 – dos
  • 0011 – tres
  • 0100 a 0111 – de cuatro a siete

Eso es todo lo que podemos llegar en positivo. 2 3 -1 = 7.

Para negativos:

  • 1111 – negativo
  • 1110 – dos negativos
  • 1101 – tres negativos
  • 1100 a 1000 – negativo de cuatro a ocho negativos

Tenga en cuenta que obtiene un valor adicional para los negativos ( 1000 = -8) que no tiene para los positivos. Esto es porque 0000 se usa para cero. Esto se puede considerar como una línea numérica de computadoras.

Distinguir entre números positivos y negativos

Al hacer esto, el primer bit adquiere el papel del bit “signo”, ya que se puede usar para distinguir entre valores decimales positivos y negativos. Si el bit más significativo es 1 , entonces se puede decir que el binario es negativo, mientras que si el bit más significativo (el más a la izquierda) es 0 , puede decir discernir que el valor decimal es positivo.

Me pregunto si podría explicarse mejor que el artículo de Wikipedia.

El problema básico que intentas resolver con la representación del complemento de dos es el problema de almacenar enteros negativos.

Primero considere un entero sin signo almacenado en 4 bits. Puedes tener lo siguiente

 0000 = 0 0001 = 1 0010 = 2 ... 1111 = 15 

No están firmados porque no hay indicación de si son negativos o positivos.

Magnitud de signo y notación de exceso

Para almacenar números negativos, puede probar varias cosas. En primer lugar, puede usar la notación de magnitud de signo que asigna el primer bit como un bit de signo para representar +/- y los bits restantes para representar la magnitud. Entonces, usando 4 bits nuevamente y asumiendo que 1 significa – y 0 significa + entonces usted tiene

 0000 = +0 0001 = +1 0010 = +2 ... 1000 = -0 1001 = -1 1111 = -7 

Entonces, ¿ves el problema allí? Tenemos 0. positivo y negativo. El mayor problema es sumr y restar números binarios. Los circuitos para sumr y restar utilizando la magnitud del signo serán muy complejos.

Que es

 0010 1001 + ---- 

?

Otro sistema es la notación excesiva . Puede almacenar números negativos, se deshace del problema de los dos ceros, pero la sum y la resta siguen siendo difíciles.

Entonces viene el complemento a dos. Ahora puede almacenar enteros positivos y negativos y realizar operaciones aritméticas con relativa facilidad. Hay una serie de métodos para convertir un número en complemento a dos. Aquí hay uno.

Convertir decimal a complemento de dos

  1. Convierta el número en binario (ignore el signo por ahora), por ejemplo, 5 es 0101 y -5 es 0101.

  2. Si el número es positivo, entonces has terminado. por ejemplo, 5 es 0101 en binario usando la notación de complemento a dos.

  3. Si el número es negativo, entonces

    3.1 encuentra el complemento (invertir 0’s y 1’s) ej. -5 es 0101 por lo que encontrar el complemento es 1010

    3.2 Agregue 1 al complemento 1010 + 1 = 1011. Por lo tanto, -5 en el complemento a dos es 1011.

Entonces, ¿y si quisieras hacer 2 + (-3) en binario? 2 + (-3) es -1. ¿Qué tendrías que hacer si estuvieras usando la magnitud del signo para agregar estos números? 0010 + 1101 =?

Usando el complemento de dos considere lo fácil que sería.

  2 = 0010 -3 = 1101 + ------------- -1 = 1111 

Convirtiendo Complemento Dos a Decimal

Convirtiendo 1111 a decimal:

  1. El número comienza con 1, por lo que es negativo, por lo que encontramos el complemento de 1111, que es 0000.

  2. Agregue 1 a 0000, y obtenemos 0001.

  3. Convierte 0001 a decimal, que es 1.

  4. Aplicar el signo = -1.

Tada!

Al igual que la mayoría de las explicaciones que he visto, las anteriores son claras acerca de cómo trabajar con el complemento 2, pero realmente no explican qué son matemáticamente. Intentaré hacer eso, al menos para enteros, y cubriré algunos antecedentes que probablemente sean familiares primero.

Recuerde cómo funciona para decimal:
2345
es una forma de escribir
2 × 10 3 + 3 × 10 2 + 4 × 10 1 + 5 × 10 0 .

De la misma manera, el binario es una forma de escribir números usando solo 0 y 1 siguiendo la misma idea general, pero reemplazando esos 10s anteriores con 2s. Luego en binario,
1111
es una forma de escribir
1 × 2 3 + 1 × 2 2 + 1 × 2 1 + 1 × 2 0
y si lo resuelves, resulta igual a 15 (base 10). Eso es porque es
8 + 4 + 2 + 1 = 15.

Esto está muy bien para números positivos. Incluso funciona para números negativos si estás dispuesto a poner un signo menos delante de ellos, como lo hacen los humanos con los números decimales. Eso incluso se puede hacer en computadoras, más o menos, pero no he visto una computadora desde principios de los 70. Dejaré las razones para una discusión diferente.

Para las computadoras, resulta más eficiente usar una representación de complemento para números negativos. Y aquí hay algo que a menudo se pasa por alto. Las anotaciones de complemento implican algún tipo de inversión de los dígitos del número, incluso los ceros implicados que aparecen antes de un número positivo normal. Eso es incómodo, porque surge la pregunta: ¿todos? Eso podría ser una cantidad infinita de dígitos para ser considerados.

Afortunadamente, las computadoras no representan infinitos. Los números están restringidos a una determinada longitud (o ancho, si lo prefiere). Volvamos a los números binarios positivos, pero con un tamaño particular. Usaré 8 dígitos (“bits”) para estos ejemplos. Entonces nuestro número binario sería realmente
00001111
o
0 × 2 7 + 0 × 2 6 + 0 × 2 5 + 0 × 2 4 + 1 × 2 3 + 1 × 2 2 + 1 × 2 1 + 1 × 2 0

Para formar el complemento de 2 negativo, primero complementamos todos los dígitos (binarios) para formar
11110000
y agregue 1 a la forma
11110001
pero, ¿cómo vamos a entender eso para decir -15?

La respuesta es que cambiamos el significado del bit de orden superior (el más a la izquierda). Este bit será un 1 para todos los números negativos. El cambio consistirá en cambiar el signo de su contribución al valor del número en el que aparece. Así que ahora se entiende que nuestro 11110001 representa
1 × 2 7 + 1 × 2 6 + 1 × 2 5 + 1 × 2 4 + 0 × 2 3 + 0 × 2 2 + 0 × 2 1 + 1 × 2 0
Tenga en cuenta que “-” delante de esa expresión? Significa que el bit de signo tiene el peso -2 7 , es decir -128 (base 10). Todas las demás posiciones conservan el mismo peso que tenían en números binarios sin signo.

Trabajando nuestro -15, es
-128 + 64 + 32 + 16 + 1
Pruébalo en tu calculadora. es -15.

De las tres formas principales en que he visto los números negativos representados en las computadoras, el complemento 2 gana indiscutiblemente para mayor comodidad en el uso general. Sin embargo, tiene una rareza. Como es binario, tiene que haber un número par de posibles combinaciones de bits. Cada número positivo se puede emparejar con su negativo, pero solo hay un cero. Negar un cero te pone a cero. Entonces hay una combinación más, el número con 1 en el bit de signo y 0 en cualquier otro lado. El número positivo correspondiente no cabría en la cantidad de bits que se utilizan.

Lo que es aún más extraño de este número es que si tratas de formar su parte positiva complementando y agregando uno, obtienes el mismo número negativo. Parece natural que el cero hiciera esto, pero esto es inesperado y para nada el comportamiento al que estamos acostumbrados, porque las computadoras a un lado, generalmente pensamos en un suministro ilimitado de dígitos, no en esta aritmética de longitud fija.

Esto es como la punta de un iceberg de rarezas. Hay más al acecho debajo de la superficie, pero eso es suficiente para esta discusión. Probablemente pueda encontrar más si investiga el “desbordamiento” para la aritmética de punto fijo. Si realmente quieres adentrarte en él, también puedes buscar “aritmética modular”.

El complemento de 2 es muy útil para encontrar el valor de un binario, sin embargo, pensé en una forma mucho más concisa de resolver ese problema (nunca visto nadie más publicarlo):

tomar un binario, por ejemplo: 1101 que es [suponiendo que el espacio “1” es el signo] igual a -3 .

usando el complemento de 2, haríamos esto … voltear 1101 a 0010 … agregar 0001 + 0010 ===> nos da 0011. 0011 en positivo binario = 3. por lo tanto, 1101 = -3 !

De lo que me di cuenta

en lugar de todos los volteos y agregar, puedes hacer el método básico para resolver un binario positivo (digamos 0101) es (2 3 * 0) + (2 2 * 1) + (2 1 * 0) + (2 0 * 1) = 5.

Haz exactamente el mismo concepto con un negativo (con un pequeño giro)

tomar 1101, por ejemplo:

para el primer número en lugar de 2 3 * 1 = 8 , do – (2 3 * 1) = -8 .

luego continúe como de costumbre, haciendo -8 + (2 2 * 1) + (2 1 * 0) + (2 0 * 1) = -3

Imagine que tiene un número finito de bits / trits / dígitos / lo que sea. Usted define 0 como todos los dígitos que son 0, y cuenta hacia arriba naturalmente:

 00 01 02 .. 

Eventualmente se desbordará.

 98 99 00 

Tenemos dos dígitos y podemos representar todos los números del 0 al 100. ¡Todos esos números son positivos! ¿Supongamos que queremos representar números negativos también?

Lo que realmente tenemos es un ciclo. El número anterior a 2 es 1. El número anterior a 1 es 0. El número anterior a 0 es … 99 .

Entonces, para simplificar, digamos que cualquier número mayor de 50 es negativo. “0” a “49” representan de 0 a 49. “99” es -1, “98” es -2, … “50” es -50.

Esta representación es un complemento de diez . Las computadoras generalmente usan dos complementos , que es lo mismo, excepto que usan bits en lugar de dígitos.

Lo bueno del complemento de diez es que la adición simplemente funciona . ¡No necesita hacer nada especial para agregar números positivos y negativos!

Se encuentra dos complementos al agregar de uno a 1 complemento del número dado. Digamos que tenemos que encontrar el complemento a dos de 10101 luego encontrar su complemento, es decir, 01010 sumr 1 a este resultado, es decir, 01010+1=01011 , que es la respuesta final.

Permite obtener la respuesta 10 – 12 en forma binaria usando 8 bits: lo que realmente haremos es 10 + (-12)

Necesitamos obtener el complemento de 12 para restarlo de 10. 12 en binario es 00001100. 10 en binario es 00001010.

Para obtener el complemento de 12, simplemente invertimos todos los bits y luego agregamos 1. 12 en binario invertido es 11110011. Este es también el código inverso (complemento de uno). Ahora tenemos que agregar uno, que ahora es 11110100.

¡Así que 11110100 es el cumplido de 12! Fácil cuando lo piensas de esta manera.

Ahora puedes resolver la pregunta anterior de 10 a 12 en forma binaria.

 00001010 11110100 ----------------- 11111110 

Ver el sistema de complemento de los dos desde el punto de vista matemático realmente tiene sentido. En el complemento de diez, la idea es esencialmente “aislar” la diferencia.

Ejemplo: 63 – 24 = x

Añadimos el complemento de 24 que es realmente justo (100 – 24). Entonces, realmente, todo lo que estamos haciendo es agregar 100 en ambos lados de la ecuación.

Ahora la ecuación es: 100 + 63 – 24 = x + 100, es por eso que eliminamos los 100 (o 10 o 1000 o lo que sea).

Debido a la inconveniente situación de tener que restar un número de una larga cadena de ceros, usamos un sistema de ‘complemento de radix disminuido’, en el sistema decimal, complemento de nueve.

Cuando se nos presenta un número restado de una gran cadena de nueves, solo necesitamos invertir los números.

Ejemplo: 99999 – 03275 = 96724

Esa es la razón, después del complemento de nueve, agregamos 1. Como probablemente sabrá de matemáticas infantiles, 9 se convierte en 10 por “robo” 1. Así que, básicamente, es solo un complemento de diez que toma 1 de la diferencia.

En Binario, el complemento de dos es equivalente al complemento de diez, mientras que el complemento de uno al complemento de nueve. La principal diferencia es que en vez de tratar de aislar la diferencia con potencias de diez (sumndo 10, 100, etc. en la ecuación) intentamos aislar la diferencia con potencias de dos.

Es por esta razón que invertimos los bits. Al igual que nuestro minuendo es una cadena de nueves en decimales, nuestro minuendo es una cadena de números en binario.

Ejemplo: 111111 – 101001 = 010110

Debido a que las cadenas de unos son 1 por debajo de una buena potencia de dos, ‘roban’ 1 de la diferencia como lo hacen los nueve en decimal.

Cuando estamos usando números binarios negativos, realmente estamos diciendo:

0000 – 0101 = x

1111 – 0101 = 1010

1111 + 0000 – 0101 = x + 1111

Para ‘aislar’ x, necesitamos agregar 1 porque 1111 está uno lejos de 10000 y eliminamos el 1 principal porque lo agregamos a la diferencia original.

1111 + 1 + 0000 – 0101 = x + 1111 + 1

10000 + 0000 – 0101 = x + 10000

Simplemente elimine 10000 de ambos lados para obtener x, es álgebra básica.

Muchas de las respuestas hasta ahora bien explican por qué el complemento de dos se usa para representar un número negativo, pero no nos dicen cuál es el número de complemento de dos, particularmente no por qué se agrega un ‘1’, y de hecho a menudo se agrega de manera incorrecta.

La confusión proviene de una comprensión pobre de la definición de un número de complemento. Un complemento es la parte faltante que haría que algo se complete.

El complemento de radix de un n número de dígito x en la raíz b es, por definición, b ^ nx. En binario 4 se representa por 100, que tiene 3 dígitos (n = 3) y una base de 2 (b = 2). Entonces su complemento radix es b ^ nx = 2 ^ 3-4 = 8-4 = 4 (o 100 en binario).

Sin embargo, obtener un complemento de radix en binario no es tan fácil como obtener su complemento de radix disminuido, que se define como (b ^ n-1) -y, solo 1 menos que el complemento de radix. Para obtener un complemento de radix disminuido, simplemente voltea todos los dígitos.

100 -> 011 (complemento de radix disminuido)

para obtener el complemento de radix (dos), simplemente agregamos 1, como definición definida.

011 +1 -> 100 (complemento de dos).

Ahora con este nuevo entendimiento, echemos un vistazo al ejemplo dado por Vincent Ramdhanie (ver la segunda respuesta más arriba)

/ * inicio de Vincent

Convirtiendo 1111 a decimal:

El número comienza con 1, entonces es negativo, entonces encontramos el complemento de 1111, que es 0000. Agregue 1 a 0000, y obtenemos 0001. Convierta 0001 a decimal, que es 1. Aplique el signo = -1. Tada!

fin de Vincent * /

Debe ser entendido como

El número comienza con 1, por lo que es negativo. Entonces sabemos que es un complemento a dos de algún valor x. Para encontrar la x representada por su complemento de dos, primero necesitamos encontrar su complemento de 1.

complemento de dos de x: 1111 complemento de uno de x: 1111-1 -> 1110; x = 0001, (voltear todos los dígitos)

aplicar el signo -, y la respuesta = -x = -1.

Es un medio inteligente de codificar enteros negativos de tal manera que aproximadamente la mitad de la combinación de bits de un tipo de datos se reserva para enteros negativos, y la sum de la mayoría de los enteros negativos con sus enteros positivos correspondientes resulta en un desbordamiento eso deja el resultado como cero binario.

Entonces, en el complemento 2 si uno es 0x0001, entonces -1 es 0x1111, porque eso dará como resultado una sum combinada de 0x0000 (con un desbordamiento de 1).

Complementos de 2: cuando agreguemos uno adicional con los complementos de 1 de un número obtendremos los complementos de 2. Por ejemplo: 100101 es el complemento de 1 es 011010 y el complemento de 2 es 011010 + 1 = 011011 (al agregar uno con el complemento de 1) Para obtener más información, este artículo lo explica gráficamente.

Me gustó la respuesta de Lavinio, pero el cambio de bits agrega cierta complejidad. A menudo hay una opción de mover bits respetando el bit de signo o sin respetar el bit de signo. Esta es la opción entre tratar los números como firmados (-8 a 7 para un nibble, -128 a 127 para bytes) o números sin registro de rango completo (0 a 15 para nibbles, 0 a 255 para bytes).

Tuve el mismo problema hace un par de semanas. Terminé leyendo sobre el tema en línea de varias fonts, tratando de juntar las piezas, y escribir sobre ello solo para asegurarme de haberlo entendido correctamente. Usamos el complemento de dos principalmente por dos razones:

  1. Para evitar representaciones múltiples de 0
  2. Para evitar el seguimiento del bit de acarreo (como en el complemento de uno) en caso de un desbordamiento.
  3. Llevar a cabo operaciones simples como la sum y la resta se vuelve fácil.

Si desea una explicación más detallada del asunto en cuestión, pruebe el artículo escrito por mí aquí . ¡Espero eso ayude!

Leí una explicación fantástica en Reddit por jng, usando el odómetro como una analogía.

enter image description here

Es una convención útil. Los mismos circuitos y operaciones lógicas que agregan / restan números positivos en binario aún funcionan tanto en números positivos como negativos si se usa la convención, por eso es tan útil y omnipresente.

Imagine el odómetro de un automóvil, gira alrededor (digamos) 99999. Si incrementa 00000, obtiene 00001. Si disminuye 00000, obtiene 99999 (debido a la rotación). Si agrega uno de nuevo a 99999, vuelve a 00000. Por lo tanto, es útil decidir que 99999 representa -1. Del mismo modo, es muy útil decidir que 99998 representa -2, y así sucesivamente. Tienes que parar en alguna parte, y también por convención, la mitad superior de los números se considera negativa (50000-99999), y la mitad positiva es solo por sí misma (00000-49999). Como resultado, el dígito superior que es 5-9 significa que el número representado es negativo, y siendo 0-4 significa que el representado es positivo, exactamente lo mismo que el signo que representa el bit superior en un número binario de complemento de dos.

Entender esto fue difícil para mí también. Una vez que lo obtuve y volví a volver a leer los artículos de los libros y las explicaciones (no había internet en ese momento), resultó que muchos de los que lo describieron realmente no lo entendieron. Escribí un libro que enseñaba el lenguaje ensamblador después de eso (que se vendió bastante bien durante 10 años).

REFERENCIA: https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html

Invierte todos los bits y agrego 1. Programáticamente:

  // in C++11 int _powers[] = { 1, 2, 4, 8, 16, 32, 64, 128 }; int value=3; int n_bits=4; int twos_complement = (value ^ ( _powers[n_bits]-1)) + 1; 

También puede usar una calculadora en línea para calcular la representación binaria del complemento a dos de un número decimal: http://www.convertforfree.com/twos-complement-calculator/

La respuesta más simple:

1111 + 1 = (1) 0000. Entonces 1111 debe ser -1. Entonces -1 + 1 = 0.

Es perfecto para entender todo esto por mí.