¿Por qué funciona la resta del$2$ y$1$?

Question

El algoritmo para $2$'s de complementar y $1$'s de complementar la resta es algo simple:

$1.$ $1$'S o $2$'s complemento del sustraendo.

$2.$ Agregar con minuendo.

$3.$ Si no se lleve a continuación, la respuesta está en que el complemento del formulario tenemos que tomar la $1$'s o $2$'s complemento del resultado y asignar un signo negativo para el final respuesta.

$4.$ Si hay un acarreo, a continuación, agregarlo a el resultado en caso de $1$'s de complementar o negligencia en el caso de $2$'s del complemento.

Esto es lo que me enseñaron en la licenciatura, pero nunca he entendido por qué este método de trabajo. Más en general , ¿por qué el radix complementar o la disminución de la base complementar la resta funciona? Estoy más interesado en la comprensión de la matemática el razonamiento detrás de este algoritmo.

Answer 1

Para darle la intuición me centraré en la no-números negativos $x,y\ge 0$ y que los números son $k$bits enteros.

1-complenet

Para obtener el 1-complemento de un número $x$ le da la vuelta cada poco en $x$s de la representación binaria $\text{bin}(x)$, 1 $\Leftrightarrow$ 0. Usted puede hacer lo mismo, restando $x$ desde el número binario que contiene sólo 1s y es tan largo como $\text{bin}(x)$. Por ejemplo,

  111111
 -010111
 -------
  101000

Esto funciona para todos los bits, y no se lleva, por lo que funciona para el conjunto de la representación binaria.

Así se puede describir el 1-complemento de $x$ $c_1(x):=(2^{k+1}-1)-x$ donde $k$ es el número de bits que tiene cada número. Por definición de la 1-complemento hemos $c_1(c_1(x))=x$.

Suponga que $x>y$ (regla 4), por lo tanto, cuando resta, vamos a tener un desbordamiento. Por lo tanto, vamos a añadir $+1$ al resultado, que los rendimientos de $$ x+c_1(y)+1=x+(2^{k+1}-1)-y+1=(2^{k+1})+(x-y),$$ ya que sólo tenemos en cuenta la primera $k$ bits, 1 en representación $2^{k+1}$ desaparecerá, y llegamos $x-y$.

Supongamos ahora que $x\ge y$ (regla 3). Entonces no hay desbordamiento y $$ c_1(x+c_1(y))=c_1 (x+(2^{k+1}-1)-y)=c_1(c_1(y-x))=y-x=|x-y|.$$

2-complement

To get the 2-complement of an number $x$ we flip the bits, starting after the right most 1. This can be interpreted as subtracting $x$ from $2^{k+1}$. Again we look at an example

  1000000
 -0010100
 --------
   101100

Until the first 1 we don't have carries, so the bits are just taken from $x$, after the first 1, we have always a carry, and hence the bits get flipped.

Similarly to the 1-complement let $c_2(x):=2^{k+1}-x$, and again $c_2(c_2(x))=x$.

Assume that $x>y$ (regla 4), esto le da $$ x+c_2(y)=2^{k+1}-y+x=2^{k+1}+(x-y).$$ De nuevo, el $2^{k+1}$ se desvanece ya que sólo tenemos en cuenta la primera $k$ bits.

Suponga que $x<y$ (regla 3), entonces $$ c_2(x+c_2(y))=c_2 (x+2^{k+1}-y)=c_2(c_2(y-x))=y-x=|x-y|.$$

Ambos conceptos pueden ser extendidos (en una forma muy natural) para trabajar con números negativos.

Answer 2

Consideramos $k$bits enteros con un $k+1$ bits, que está asociado con el signo. Si el "signo bits" 0 , a continuación, tratamos este número como de costumbre, como un número positivo en representación binaria. De lo contrario, este número es negativo (detalle).

Vamos a empezar con el 2-complemento. Para el cálculo de la 2-complemento de un número $x$ lanzamos los bits, a partir del derecho de la mayoría de 1. He aquí un ejemplo:

 0010100 -> 1101100

Definimos para cada número positivo $a$, el inverso del elemento $-a$ como el 2-complemento de $a$. Cuando la adición de dos números, vamos a olvidar el desbordamiento de bits (después de que el bit de signo), si ocurre un desbordamiento. Esta adición con el conjunto de los números positivos y negativos de las formas de un número finito de Abelian grupo. Aviso de que tenemos un solo cero, que es 00000000. La representación 10000000 no codificar un número. Para comprobar las propiedades del grupo, se observa que la

• $a + (-a) = 0$,
• $a+0=a$,
• $-(-a)=a$,
• $(a+b)=(b+a)$,
• $(a+b)+c= a+ (b+c)$.

Como consecuencia, se puede calcular con la 2-complemento como con números enteros. Para restar $a$ $b$ calculamos el $a+(-b)$. Si queremos recuperar el valor absoluto de un número negativo tenemos que tomar sus 2-complemento (esto explica el paso 3 en la pregunta del algoritmo).

Ahora el 1-complemento. Este es más complicado, porque tenemos dos ceros (000000 y 111111). Creo que es más fácil considerar la 1-complemento de $a$ como 2-complemento de menos 1. Entonces lo primero que se puede reducir la 1-complemento a los 2 del complemento y, a continuación, argumentar sobre la 2-complementos.