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

En una representación binaria sin signo, 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 (bytes),

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

El complemento a dos, que se utiliza para la notación binaria con signo, codifica números positivos y negativos en una representación de números binarios. 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.

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 complemento de dos representarán -1. Entonces, si el tamaño de la palabra es de solo dos bits, 11 es -1. Pero si el tamaño de la palabra es de 8 bits (un byte), entonces 11 es simplemente 3 y 11111111 es -1.

Esto se debe a que el complemento a 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 complemento a 2, la MSb se define como -(2 ⁿ ) donde n es la posición del bit de la MSb. Debido a cómo funcionan los números, todos los bits que no sean MSb suman (2 ⁿ )-1. Sumándolos juntos da como resultado -1.

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

Pregúntate cuántas veces necesitarás sumar 1 hasta llegar a 0.

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

Otra forma de ver esto (que puede verse como una expansión de las dos respuestas anteriores, o copiando mi propia respuesta a una pregunta similar ) es esta: para cada n, los enteros sin signo de n bits (palabras de n bits que representan un intervalo de los números naturales que comienza 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); entonces, en lugar de estar dispuestas en una línea como las naturales, las palabras de n bits están dispuestas en un círculo. Esta estructura se conoce como grupo cíclico Z _{2 ⁿ} .

Ahora la pregunta es: ¿cómo podemos usar la misma estructura cíclica para representar un intervalo de 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 del intervalo, es decir, -2 ⁿ , y 111...1 representaría el número más grande, es decir, 2 ⁿ - 1; 0 estaría representado por 100...0 en algún lugar en el medio. Eso realmente podría funcionar, pero implementar la lógica aritmética sería muy feo. :)

En cambio, aprovechamos la estructura cíclica. Dejamos las palabras 000...0 a 011...1 representando el lado no negativo de nuestro intervalo, a saber 0 a 2 ⁿ -1, y "movemos" las palabras 100...0 a 111...1 al lado negativo, representando -2 ⁿ a -1. Esto funciona muy 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 suma sin cambios desde la aritmética sin signo, y otras operaciones también son fáciles de adaptar.

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

Podría ser más fácil entender esto en decimal. Imagina que estamos haciendo aritmética con números de base 10 de tres dígitos: 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 \to 032$

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

$042 + 999 = 1041 \to 041$

$041 + 999 = 1040 \to 040$

$040 + 999 = 1039 \to 039$

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

Binario funciona de la misma manera. Con números de cuatro bits, sumar el número de cuatro bits más grande posible funciona como restar 1. Una vez más, esto se debe a que estamos eliminando el acarreo del bit más alto.

$0110 + 1111 = 10101 \to 0101$

$0101 + 1111 = 10100 \to 0100$

$0100 + 1111 = 10011 \to 0011$

$0011 + 1111 = 10010 \to 0010$

Esto se llama aritmética en complemento a dos . Con 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, sumar 1011 a un número de cuatro bits es como restar 5, siempre y cuando elimines el último acarreo.

Hay una forma más rápida y común de calcular el complemento a dos: invertir todos los bits y luego agregar uno. Esto le permite calcular un negativo de cuatro bits mediante inversión y suma, en lugar de necesitar una resta de cinco bits. Aquí se explica 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 aluden a la aritmética modular sin discutirla realmente. Creo que esta es una perspectiva valiosa y hace que el complemento a dos sea mucho más fácil de comprender.

Tanto la aritmética sin signo como la aritmética en complemento a dos en números de n 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 que terminas de vuelta donde empezaste.

Tomemos un ejemplo. Si estamos trabajando con números de 2 bits, tomamos$m=2^2 = 4$. Decimos que estamos trabajando "módulo 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 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 con 0). Considere que con un número de 2 bits, 2 + 2 se desborda a 0, ¡así que esto no es tan extraño como podría pensar inicialmente!

Tenga en cuenta también que sumar 1 lo lleva una fila hacia abajo, y restar uno lo lleva una fila hacia arriba, a menos que esté en el borde, en cuyo caso se envuelve.

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

Aritmética sin signo

Con la 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 puede ver, ¡esto es solo una aritmética familiar sin signo!$2+2$se desbordará (envolverá) a 0.$0-1$se desbordará a 3.

Aritmética en complemento a dos

Con la aritmética del 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, lo que ocurrirá exactamente a la mitad.

Así que ahora, para ilustrar por qué el complemento a dos 11111111b = -1, tenga en cuenta que el número de todos los 1 tiene un valor "sin signo".$2^n - 1$(ver abajo para la prueba), pero en la notación de complemento a dos necesitamos 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 restar 1 de 0 (fila superior) provoca un retorno a la fila inferior, y la fila inferior es todo-1 en binario, por lo que esa es la representación de -1.

Apéndice

Esta prueba es bastante fácil.

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

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

Tenga en cuenta que:

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

Cancelando, obtenemos$v = 2^n-1$, ¡y listo!

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