¿Por qué son 11, 111, 1111, ... equivalentes a -1 en el complemento de dos? [duplicar]

En una representación binaria sin firma, solo se pueden representar números positivos, y el peso de cada bit, incluido el bit más significativo, es una potencia de dos.

Entonces, con un tamaño de palabra de 8 (byte),

00000000 => 0
01111111 => 127
10000000 => 128
11111111 => 255

El complemento de dos, que se usa para la notación binaria firmada, codifica números positivos y negativos en una representación de número binario. El peso de cada bit es una potencia de dos, excepto el bit más significativo , cuyo peso es el negativo de la potencia correspondiente de dos.

00000000 => 0
01111111 => 127
10000000 => -128    (in unsigned notation, this bit was 128, now its -128)
11111111 => -1

Para un tamaño de palabra N dado, todos los 1 en el complemento de dos representarán -1. Entonces, si el tamaño de la palabra es solo de dos bits, 11 es -1. Pero si el tamaño de la palabra es 8 bits (un byte), entonces 11 es simplemente 3 y 11111111 es -1.

Esto se debe a que el complemento de dos de un número de n bits se define como el complemento con respecto a 2 \ $ ^ {N} \ $; es decir, es el resultado de restar el número de 2 \ $ ^ {N} \ $, que en binario es uno seguido de N ceros.

Entonces, si N = 2 (primer ejemplo), entonces 2 \ $ ^ {2} \ $ = 4,

 100
  -1
 011

truncar a dos bits da 11. ( -2 + 1 = -1)

Para N = 8 (primer ejemplo), entonces 2 \ $ ^ {8} \ $ = 256,

 100000000
        -1
 011111111

truncar a ocho bits da 11111111. ( -128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -1)

En el complemento a 2, el MSb se define como - (2 ⁿ ) donde n es la posición de bit del MSb. Debido a cómo funcionan los números, todos los bits distintos del MSb se suman a (2 ⁿ ) -1. Sumando esos resultados juntos en -1.

Esta es una explicación no matemática, solo intuitiva.

Pregúntate a ti mismo cuántas veces necesitarás agregar 1 hasta llegar a 0.

En todos sus ejemplos, la respuesta para esa pregunta es 1. Y porque eso también es cierto para -1, estos números son iguales a -1.

Otra forma de ver esto (que puede verse expandiéndose en las dos respuestas anteriores, o eliminando mi propia respuesta para una pregunta similar ) es esto: para cada n, los enteros sin signo de n bits (las palabras de n bits que representan un intervalo de los números naturales que comienzan en 0) forman una estructura cíclica con 2 ⁿ miembros: debido al desbordamiento, el sucesor de 111 ... 1 (que representa 2 ⁿ -1) es 000 ... 0 (que representa 0); así que en lugar de estar dispuestos en una línea como los naturales, las palabras de n bits se organizan en un círculo. Esta estructura se conoce como el grupo cíclico Z _{2 ⁿ} .

Ahora la pregunta es: ¿cómo podemos usar la misma estructura cíclica para representar un intervalo de los números enteros que contienen números negativos y positivos? Una posible respuesta sería "desplazar" todo hacia la izquierda: 000 ... 0 representaría el número más pequeño en el intervalo, es decir, -2 ⁿ , y 111 ... 1 representaría el más grande, a saber 2 ⁿ -1; 0 estaría representado por 100 ... 0 en algún lugar en el medio. Eso realmente podría funcionar, pero la implementación de la lógica aritmética sería muy fea. :)

En cambio, aprovechamos la estructura cíclica. Dejamos las palabras 000 ... 0 a 011 ... 1 que representan el lado no negativo de nuestro intervalo, es decir, 0 a 2 ⁿ -1, y "movemos" las palabras 100 ... 0 a 111 ... 1 al lado negativo, que representa -2 ⁿ a -1. Esto funciona bien: el sucesor de 111 ... 1 es de hecho 000 ... 0 (en otras palabras, -1 + 1 = 0). Ahora podemos dejar toda la lógica de adición sin cambios de la aritmética no firmada, y otras operaciones también son fáciles de adaptar.

Este tipo de pregunta ha sido respondida anteriormente, pero parece que esta redacción particular de la pregunta aparece en muchos resultados de búsqueda, así que volveré a publicar mi respuesta desde here .

Podría ser más fácil entender esto en decimal. Imagine que estamos haciendo aritmética en números de base de tres dígitos 10: 445, 900, 132, 042, 007, etc. Podemos sumar los números, pero el resultado siempre se trunca a tres dígitos. Aquí hay un ejemplo:

  

\ $ 900 + 132 = 1032 \ a 032 \ $

Ahora, mira lo que sucede cuando agregamos 999 a un número:

  

\ $ 042 + 999 = 1041 \ a 041 \ $

     

\ $ 041 + 999 = 1040 \ a 040 \ $

     

\ $ 040 + 999 = 1039 \ a 039 \ $

¡Mientras eliminemos el cuarto dígito, agregar 999 (el número de tres dígitos más grande posible) funciona igual que restar 1!

El binario funciona de la misma manera. Con los números de cuatro bits, agregar el mayor número posible de cuatro bits funciona igual que restar 1. Nuevamente, esto se debe a que estamos eliminando el límite máximo.

  

\ $ 0110 + 1111 = 10101 \ a 0101 \ $

     

\ $ 0101 + 1111 = 10100 \ a 0100 \ $

     

\ $ 0100 + 1111 = 10011 \ a 0011 \ $

     

\ $ 0011 + 1111 = 10010 \ a 0010 \ $

Esto se llama aritmética de complemento de dos . Usando este sistema, puede calcular el "negativo" de cualquier número binario de n bits restándolo de \ $ 2 ^ n \ $. Para números de cuatro bits, funciona así:

  

\ $ - 1 = 2 ^ 4 - 1 = 10000 - 0001 = 1111 \ $

     

\ $ - 5 = 2 ^ 4 - 5 = 10000 - 0101 = 1011 \ $

Por lo tanto, agregar 1011 a un número de cuatro bits es como restar 5, siempre que sueltes el último acarreo.

Hay una forma más rápida y más común de calcular el complemento de los dos: invertir todos los bits y luego agregar uno. Esto le permite calcular un negativo de cuatro bits utilizando inversión y suma, en lugar de necesitar una resta de cinco bits. Aquí es cómo calcular -1 y -5 usando este método:

  

\ $ - 1 = \ lnot 0001 + 1 = 1110 + 1 = 1111 \ $

     

\ $ - 5 = \ lnot 0101 + 1 = 1010 + 1 = 1011 \ $

Varias respuestas se refieren a aritmética modular sin realmente discutirlo. Creo que esta es una perspectiva valiosa y hace que el complemento de dos sea mucho más fácil de entender.

Tanto la aritmética complementaria de dos y sin signo en n -números de bits pueden considerarse naturalmente como operaciones módulo 2 ⁿ .

Aritmética modular

Para aquellos que no están familiarizados con la aritmética modular, es un sistema de números donde sumar o restar \ $ m \ $ no cambia el valor de un número. Esto significa que el sistema es "circular" y una vez que pasa por \ $ m \ $ pasos, vuelve a comenzar donde comenzó.

Tomemos un ejemplo. Si estamos trabajando con números de 2 bits, tomamos \ $ m = 2 ^ 2 = 4 \ $. Decimos que estamos trabajando "modulo 4". En este sistema, sumar o restar 4 no cambia el valor de un número.

Esto significa 5 = 1, 6 = 2, y así sucesivamente. De hecho tenemos:

... = -8 = -4 = 0 = 4 =  8 = 12 = ...
... = -7 = -3 = 1 = 5 =  9 = 13 = ...
... = -6 = -2 = 2 = 6 = 10 = 14 = ...
... = -5 = -1 = 3 = 7 = 11 = 15 = ...

Esto crea cuatro "clases" de números: las únicas posibilidades que "existen" en el universo de módulo-4. ¡Esto encaja, porque solo hay 4 posibilidades que puede asumir un número de 2 bits!

Aparte de la división, es como la aritmética ordinaria. 1 + 2 = 3, 2 + 2 = 4 (pero podemos reemplazar 4 por 0). Considera que con un número de 2 bits, 2 + 2 se desborda a 0, ¡así que esto no es tan raro como puedes pensar inicialmente!

Tenga en cuenta también que agregar 1 le lleva a una fila, y restar una le lleva a una fila, a menos que esté en el borde, en cuyo caso se ajusta.

(Sí, usar el signo = es un poco de un abuso de notación pero es una forma rápida de transmitir el punto.)

Aritmética no firmada

Con una aritmética sin signo, elegimos la representación en negrita cada vez que imprimimos o comparamos números.

... = -8 = -4 = 0 = 4 =  8 = 12 = ... [00b]
... = -7 = -3 = 1 = 5 =  9 = 13 = ... [01b]
... = -6 = -2 = 2 = 6 = 10 = 14 = ... [10b]
... = -5 = -1 = 3 = 7 = 11 = 15 = ... [11b]

¡Como pueden ver, esto es simplemente una aritmética sin firmar! \ $ 2 + 2 \ $ se desbordará (envolver alrededor) a 0. \ $ 0-1 \ $ se desbordará a 3.

Aritmética del complemento de dos

Con la aritmética de complemento a dos, elegimos esta representación en negrita cada vez que imprimimos o comparamos números.

... = -8 = -4 = 0 = 4 =  8 = 12 = ... [00b]
... = -7 = -3 = 1 = 5 =  9 = 13 = ... [01b]
... = -6 = -2 = 2 = 6 = 10 = 14 = ... [10b]
... = -5 = -1 = 3 = 7 = 11 = 15 = ... [11b]

Tenga en cuenta que cambiamos a la representación negativa cuando el bit más a la izquierda del número es un 1, que se producirá exactamente hasta la mitad.

Así que ahora, para ilustrar por qué el complemento de dos 11111111b = -1, tenga en cuenta que el número de todos los 1s tiene un valor "sin signo" \ $ 2 ^ n - 1 \ $ (ver prueba de abajo), pero en la notación de complemento de dos necesitamos para restar \ $ 2 ^ n \ $ porque el bit de signo está establecido, lo que da \ $ - 1 \ $.

Quizás una forma más sencilla de verlo es que al restar 1 de 0 (fila superior) se genera un wraparound en la fila inferior, y la fila inferior es all-1s en binario, por lo que es la representación de -1.

Apéndice

Esta prueba es bastante fácil.

Teorema: un n -bit número binario que es todo 1s tiene un valor \ $ v = 2 ^ n - 1 \ $.

Prueba: Al agregar los valores de posición de todos los bits, tenemos: \ $ v = 2 ^ {n-1} + 2 ^ {n-2} + \ ldots + 2 ^ {1} + 2 ^ 0 \ $.

Tenga en cuenta que:

\ $ 2vv = (2 ^ {n} + 2 ^ {n-1} + \ ldots + 2 ^ {2} + 2 ^ 1) - (2 ^ {n-1} + 2 ^ {n- 2} + \ ldots + 2 ^ {1} + 2 ^ 0) \ $.

Al cancelar, obtenemos \ $ v = 2 ^ n-1 \ $, ¡y hemos terminado!

Para averiguar cuál es el negativo de un número en dos complementa "invertir y agregar uno". entonces -1 significa invertir el valor 0000 ... 000001 dando 11111 .... 11110 luego agregar uno dando 1111 ... 1111. por lo tanto, por definición, dos o más números de bits, el valor de -1 es todos unos.