¿Por qué funciona el complemento a dos?

Question

A punto de leer informática, me encontré recientemente con el concepto de "complemento a dos". Entiendo cómo aplicar el "algoritmo" para calcular esto en papel, pero aún no he obtenido una comprensión de por qué funciona. Creo que este sitio: https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html proporciona una explicación de por qué "invertir los dígitos" y sumar uno produce el complemento. Lo que no entiendo es por qué sumar el complemento es equivalente a restar el número original. ¿Podría alguien por favor darme una explicación (quizás con un ejemplo decimal del mismo concepto también)?

¡Muchas gracias!

Answer 1

Me quedaré con cantidades de 8 bits, pero lo mismo se aplica en general.

La clave para entender el complemento a dos es notar que tenemos un conjunto de valores finitos (en particular, $2^8$) en los que hay una noción sensata de adición por $1$ que nos permite recorrer todos los números. En particular, tenemos un sistema de aritmética modular, en este caso módulo $2^8 = 256$.

---

De manera intuitiva, la aritmética módulo $n$ es un sistema de adición (y sustracción) en el que el desbordamiento y subdesbordamiento te hacen "reciclar" a un valor de $0$ a $n-1$. Un ejemplo clásico es la "aritmética de reloj" usual, es decir aritmética módulo $12$.

Por ejemplo, si ahora son las $11\!:\!00$, entonces tres horas después serán las $2\!:\!00$, ya que $$ 11 + 3 = 14 \equiv 2 \pmod {12} $$ y de manera similar, si son la $1\!:\!00$, entonces $4$ horas antes eran las $9$ ya que $$ 1 - 4 = -3 \equiv 9 \pmod{12} $$ Observa que restar $4$ horas en el reloj es lo mismo que sumar $12 - 4 = 8$ horas. En particular, podríamos haber calculado lo anterior de la siguiente manera: $$ 1 - 4 \equiv 1 + 8 = 9 \pmod{12} $$ Es decir: al realizar aritmética módulo $n$, podemos restar $x$ sumando $n-x$.

---

Ahora, apliquemos esta idea módulo $256$. ¿Cómo restar $3$? Bueno, por la lógica anterior, esto es lo mismo que sumar $256 - 3 = 253$. En notación binaria, podríamos decir que restar $00000011$ es lo mismo que sumar $$ 1\overbrace{00000000}^8 - 00000011 = 1 + \overbrace{11111111}^8 - 00000011 = 11111101 $$ y ahí tienes tu complemento a dos: el cálculo $(11111111 - 00000011)$ "invierte los bits" de $00000011$, y sumamos $1$ a este resultado.

---

Nota 1: En el contexto de la aritmética con enteros con signo, no pensamos en $11111101$ como siendo $253$ en nuestro sistema de $8$ bits, en cambio lo consideramos para representar el número $-3$. En lugar de que nuestros números vayan de $0$ a $255$ alrededor de un reloj, los hacemos ir de $-128$ a $127$, donde $-x$ ocupa el mismo lugar que $n - x$ ocuparía para valores de $x$ de $1$ a $128$.

Concisa, esto equivale a decir que un número con 8 dígitos binarios se considera negativo si y solo si su dígito principal (su dígito "más significativo") es un $1$. Por esta razón, el dígito principal se denomina el "bit de signo" en este contexto.

Nota 2: Un interesante análogo infinito al sistema de complemento a dos de sustracción es el de los números 2-ádicos infinitos. En particular, podemos decir algo extraño como $$ \dots 11111 = -1 $$ ya que $\dots 11111$ es el "complemento a dos infinito" de $1$.

Answer 2

Veamos un ejemplo decimal. Quieres hacer $735-78$.

Pide prestado 1000 al Banco de Números; el préstamo no tiene intereses, pero debes devolver lo que recibiste tan pronto como lo uses.

Ahora considera que $$ 735-78=735+(1000-78)-1000 $$ La resta $1000-78$ es muy fácil de hacer: simplemente haz el complemento a 9 en los tres dígitos más a la derecha (el que falta a la izquierda es, por supuesto, $0$), obteniendo $921+1$, entonces nuestra operación ahora es $$ 735-78=735+921+1-1000 $$ Dado que \begin{array}{rr} 735 & + \\ 921 & = \\ \hline 1656 \end{array} podemos devolverle 1000 al banco y sumar 1: $$ 735-78=656+1=657 $$

En base dos es exactamente lo mismo, con la única diferencia de que el complemento a 1 (en lugar del complemento a 9) es muy fácil, porque consiste en invertir los dígitos. Tampoco necesitas el préstamo porque trabajas con un número fijo de bits, y los números que desbordan simplemente se reducen olvidando el dígito más a la izquierda. Entonces si tienes que hacer

00101001 - 00001110

puedes invertir los dígitos en el segundo número y sumar, olvidando el bit más a la izquierda que puede convertirse en 1:

00101001 +
11110001 =
----------
00011010 +
       1 =
----------
00011011

Answer 3

La suposición básica es que estamos haciendo aritmética de módulo sobre algún $2^{n+1}$. es decir $x \equiv x + 2^{n+1}$ para todos los $x$. (Supongo que debería escribir $x \equiv x + 2^{n+1} \pmod{2^{n+1}}$ pero no voy a escribir la parte $(\operatorname{mod}{2^{n+1}})$.) Especialmente $0 \equiv 2^{n+1}$.

Entonces lo que queremos demostrar es que $-x \equiv 2^{n+1} - x$ es el "complemento de dos". Si $x = \sum_{i=0}^{n} a_i 2^i; a_i = \{0,1\}$, el "complemento de dos" es $\overline x = (\sum_{i=0}^{n} b_i 2^i) + 1$ donde $a_i + b_i = 1$. Así que $$\begin{align} x + \overline x &= ( \sum_{i=0}^{n} a_i 2^i) + (\sum_{i=0}^{n} b_i 2^i) + 1 \\ &= (\sum_{i=0}^{n}(a_i + b_i)*2^i) + 1 \\ &= (\sum_{i=0}^{n} 1*2^i) +1 \\ &= 11\ldots11_2 + 1 &&\text{(el subíndice $2$ denota binario)} \\ &\equiv 00\ldots00_2 \\ &\equiv (2^{n+1} - 1) + 1 \\ &= 2^{n+1} \\ &\equiv 0 \end{align}$$

Entonces $\overline x = 2^{n+1} -x \equiv 0 - x = -x$

Ejemplo: Deja $n = 8$ entonces tenemos los números $0, \ldots, 255$ con $256 \equiv 0$, establece $x = 100 = 64 + 32 + 4 = 01100100_2$ y $y = 10011011_2 = 155$. Entonces $$x + y = 11111111_2 = 255 = 256 - 1 \equiv -1$$ y $$z = y + 1 = 10011011_2 + 1 = 10011100_2 = 156$$ Sin embargo $z = y+ 1 = (x+y) +1 - x = (256 -1) +1 - x = 256 -x \equiv -x \equiv -100$.

Y si realmente lo hacemos: $y = 10011011_2=128 + 16 + 8 + 2 + 1 = 155$

$z = 10011100_2 = 128 + 16 + 8 + 4 = 156$.

Y, de hecho, $156 + 100 = 256 \equiv 0$ así que $156 \equiv -100 \pmod{256}$.

---

Otra forma de pensarlo es si hiciéramos "complemento de 10:

Para encontrar $-15,890,256 \bmod 1{,}000{,}000{,}000$ haríamos el "complemento de 10" de $015,890,256$ que tiene la expansión decimal $$(9-0)(9-1)(9-5)(9-8)(9-9)(9-0)(9-2)(9-5)(9-6) = 984{,}109{,}743.$$ [Nota: $984{,}109{,}743 + 15{,}890{,}256=999{,}999{,}999$.]

Agregamos $1$ para obtener $984{,}109{,}744$ y, de hecho, $984,109,744 \equiv -15,890,256 \pmod {1{,}000{,}000{,}000}$.

Pero "$2$" solo tiene dos valores, $0$ y $1$, así que es más fácil.

Answer 4

La forma en que lo representamos es ambigua. Si eres explícito acerca de todos los bits no declarados, entonces simplemente cambiar todos los bits niega el número. Pero necesitas tener una representación con un punto decimal y bits que indiquen cuáles son todos los bits no declarados. Por ejemplo, digamos que somos explícitos acerca de cuáles son los bits no declarados para que podamos combinar números con signo, sin signo y sin acarreo explícitamente:

Esto es cero: 0..0000.0000..0

Usa "..1" para representar que no hay ceros a la derecha: 0..0000.1111..1

Si realizas el acarreo, obtienes ceros a la derecha y se convierte en 1. Esta es una definición mecánica que se puede verificar y hacer en una máquina (finita) real. Entonces -1 es:

1..1111.0000..0

Suma 1 + -1:

0..0000.1111..1 + 1.1111.0000..0

Eso te da: 1..1111.1111..1, lo cual requiere un acarreo debido a los "..1". Así que después del acarreo, es 0..0000.0000..0.

Por lo tanto, ahora negamos un entero. Tiene todos los bits cero a la derecha. Por lo tanto, activa un acarreo, que es lo mismo que sumar 1.

0..010.000..0

1..101.111..1

1..110.000..0

Así que el hecho de que "inviertes los bits y sumas 1" es un poco una ilusión creada por ser ambiguo acerca de cuáles son todos los bits. Es una optimización emergente para las representaciones finitas de enteros declararlo de esa manera.

Negar 1/2:

0..000.100..0

1..111.011..1

1..111.100..0

Eso es -1 + 1/2.

Answer 5

Con la ayuda de las otras respuestas en esta publicación (especialmente la de Ben Grossmann), logré entender el complemento a dos y por qué funciona por mí mismo, pero quería agregar otra respuesta completa y básica para cualquier persona que aún no lo entienda. Esta es mi primera publicación, así que gracias por leer de antemano. Además, es probable que gran parte de mi notación matemática sea incorrecta, así que por favor consulte otras respuestas para explicaciones matemáticamente más precisas.

Como señaló Ben Grossmann, comprender que la suma binaria es un módulo es la clave para entender cómo funciona el complemento a dos. Lo que eso significa en un sentido binario es que el último acarreo no se utiliza, por lo tanto: 1111 1111 + 1 = 0000 0000, no 1 0000 0000.

En decimal, esto se ve así: $(255+1)\bmod{2^8}$. Un ejemplo similar que puede resultar más fácil de entender es $(a+b)\bmod{12}$, que debería resultar familiar.

Esto funciona para la suma, ¿pero qué hay de la resta de módulo? Bueno, continuando con el ejemplo del reloj, si queremos restar usando la suma de módulo, hay una solución fácil: $a+(12-b) \pmod{12}$, o en binario: $a+(2^8-b)\bmod{2^8}$. El $12$ y el $2^8$ se cancelan por su módulo correspondiente, dejándonos con $a-b$. El truco ahora es obtener $2^8-b$, y ese truco radica en el complemento a dos.

Para derivar $2^8-b$, o $1\ 0000\ 0000 - b$ usando solo 8 bits, primero tenemos que convertir eso en un formato familiar:

$1\ 0000\ 0000-b=1111\ 1111-b+1$

Esto es equivalente a $11-b+1$ usando 12 como nuestro módulo. Restar un número de $1111\ 1111$ es lo mismo que invertirlo. Si esto es confuso, entonces considera la ecuación

$1111\ 1111-1101\ 1001$

Como habrás notado, no hay acarreos porque no hay $0$s en $2^8-1$. Esto significa efectivamente que cada bit de b está invertido. Por lo tanto, $INV(b)$ se puede sustituir por $1111\ 1111 - b$.

Inserta eso en nuestra ecuación anterior, y ahora tenemos $a-b=a+INV(b)+1$. Ahí tienes el complemento a dos.

Lo que esto significa para los números negativos es que $1111\ 1111=-1$ (como se explicó anteriormente en más detalle por Ben Grossmann) y $1000\ 0000=-128$, mientras que $0000\ 0000=0$ y $0111\ 1111=127$. El sistema cicla primero por los positivos, y una vez que se alcanza 128 ($1000\ 0000$) cambia de signo y cicla en sentido contrario por los negativos. El séptimo bit actúa como ese signo, y no se necesita ningún cambio de signo real. Sin necesidad de hacer ninguna provisión adicional, ahora podemos sumar tanto números negativos como positivos.