¿Cómo demostrar que la declaración C-X, ~ x + 1, y ~ (x-1) dan el mismo resultado?

Question

Quiero saber la lógica detrás de esta afirmación, la prueba. La expresión C -x, ~ x + 1, y ~ (x-1) todos dan el mismo resultado para cualquier x. Puedo demostrar que esto es cierto para los ejemplos específicos. Creo que la manera de demostrar que esto tiene algo que ver con las propiedades de complemento a dos. ¿Algunas ideas?

Answer 1

Tenga en cuenta lo que se obtiene cuando se agrega un número a su complemento bit a bit. El complemento bit a bit de un número entero de n bits x tiene un 1 en todas partes que x tiene un 0, y viceversa. Por lo tanto, es claro ver:

+ x ~ x = 0b11 ... (valor de n bits de todos unos) 11

Independientemente del número de bits en x. Además, tenga en cuenta que la adición de uno a un número de n-bits con todo los hará envolver a cero. Así vemos:

+ x ~ x + 1 = 0b11 ... 11 + 1 = 0 y ~ x + 1 = -x.

Del mismo modo, la nota (x - 1) + ~ (x - 1) = 0b11 ... 11. Entonces (x - 1) + ~ (x - 1) + 1 = 0, y ~ (x - 1). = -X

Answer 2

No estoy seguro de que puede probar esto de cualquier especie de axioma de utilidad que no sea la reducción bastante trivial nuevo al hecho de que hemos definido los números negativos en número entero moderna ALU estar en complemento a dos.

Los ordenadores no Tienes para implementar con complemento a dos de hardware binario, es sólo que hay varias propiedades atractivas y casi todo está construido de esa manera en estos días. (Pero no coma flotante! Esos son de un complemento!)

Así se construye una máquina que le pasa a representar números negativos en complemento a 2. Expresiones que muestran los números negativos para ser representados en complemento a dos son exactos, pero sólo porque ellos han definido de esa manera. Esa es la base axiomática de los números enteros negativos en las máquinas modernas.

Desde definimos la negación en términos de complemento a dos, usted se refiere esencialmente a los axiomas, aunque supongo que eso es lo que en última instancia todas las pruebas hacen.

Tal vez por eso no estoy realmente un tipo teoría. : -)

Answer 3

~ x + 1 es equivalente a complemento a 2 + 1 (es decir, número negativo) representaciones de -x, ~ (x-1) también representa el mismo (considerar el caso en que el último bit es 1, ~ (x-1) = ~ (b1b2.b (n-1) 1 - 0 a) = b1'b2' ... b (n-1) '1 = b1'b2' ... b (n-1) '0 + 1 = . ~ x + 1 bodega caso similar para el último bit es 0. ~ (x-1) = ~ (b1b2..bi100..00 - 1) = ~ = b1b2..bi011..11 b1'b2' bi .. '100..00 = b1'b2' .. bi'011..11 + 1 = ~ x + 1.

Answer 4

Voy a tratar de presentar una explicación intuitiva de que todo el mundo debería resultarle útiles. Si insiste podemos probar un enfoque más formal.

En la representación de complemento a dos, con el fin de tener una representación única del elemento cero, sacrificamos un elemento positivo. Como resultado, hay un número extra negativa que tiene espejo positivo.

Así que, dados 2 bits, obtenemos: {+1, 0, -1, -2} que se representa en binario como:

-2    10
-1    11
 0    00
+1    01

Así, podemos pensar en el cero como un espejo. Ahora, dado un entero x, si queremos invertir su signo, podemos empezar invirtiendo todos los bits. Esto habría sido suficiente si no había cero entre los aspectos positivos y negativos. Pero ya que el cero hace un cambio, en los aspectos positivos, hemos compensar eso.

Las dos expresiones mencionadas en la pregunta hacen esta compensación antes y después de ~(x-1) ~x+1 invirtiendo los bits. Se puede comprobar fácilmente que el uso de +1 y -1 en nuestro ejemplo de 2 bits.

Answer 5

En general esto no es cierto, ya que el estándar de C no requiere el uso de complemento a dos para representar números negativos.

En particular, no se define el resultado de aplicar a un tipo ~ firmado.

Sin embargo, por lo que yo sé todas las máquinas modernas utilizan complemento a dos para los números enteros.