~ x + ~ y == ~ (x + y) siempre es falso?

153

¿Este código siempre se evalúa como falso? Ambas variables son complementos firmados por dos.

~x + ~y == ~(x + y)

Siento que debería haber algún número que satisfaga las condiciones. Traté de probar los números entre -5000y 5000nunca logré la igualdad. ¿Hay alguna manera de establecer una ecuación para encontrar las soluciones a la condición?

¿Cambiar uno por el otro causará un error insidioso en mi programa?

Steve
fuente
66
¿Quieres una prueba o algo?
Alvin Wong
26
Tenga en cuenta que en los casos de desbordamiento de enteros con signo, es un comportamiento técnicamente indefinido. Por lo tanto, es posible que regrese trueincluso si nunca pueden asumir un complemento estricto de dos.
Mysticial
1
@AlvinWong sí, una explicación sería buena
Steve
1
@Steve: Podrías demostrar que has intentado con todos los sospechosos habituales (-1, 0, 1, 2, etc.) en todas las combinaciones, así como tus intentos de "resolver" el problema para palabras pequeñas ( ¿Tres bits? ¿Cuatro bits?). Eso definitivamente ayudaría a convencernos de que no solo estamos ayudando a alguien a obtener algo que no intentaron ganar para sí mismos primero. :)
sarnold
44
@AlexLockwood Cuando publiqué la pregunta por primera vez, asumí que etiquetar la pregunta como "tarea" pide a las personas que me den pistas para ayudarme a resolver el problema (como dice la descripción de la etiqueta "tarea") y no solo dar respuestas. Es por eso que simplemente hice la pregunta del problema :)
Steve

Respuestas:

237

Supongamos, en aras de la contradicción, que existe algo xy algo y(mod 2 n ) tal que

~(x+y) == ~x + ~y

Por el complemento a dos *, sabemos que,

      -x == ~x + 1
<==>  -1 == ~x + x

Observando este resultado, tenemos,

      ~(x+y) == ~x + ~y
<==>  ~(x+y) + (x+y) == ~x + ~y + (x+y)
<==>  ~(x+y) + (x+y) == (~x + x) + (~y + y)
<==>  ~(x+y) + (x+y) == -1 + -1
<==>  ~(x+y) + (x+y) == -2
<==>  -1 == -2

Por lo tanto, una contradicción. Por lo tanto, ~(x+y) != ~x + ~ypara todos xy y(mod 2 n ).


* Es interesante notar que en una máquina con aritmética complementaria, la igualdad es válida para todos xy y. Esto es debido a que bajo de un complemento, ~x = -x. Por lo tanto, ~x + ~y == -x + -y == -(x+y) == ~(x+y).

Alex Lockwood
fuente
47
Por supuesto, C no requiere este comportamiento; ya que no requiere la representación del complemento a dos.
Billy ONeal
12
Por cierto , la igualdad es verdadera para el complemento de uno. La operación NOT no está realmente definida para el número en general, por lo que mezclar NOT con la suma da como resultado un comportamiento diferente dependiendo de la representación del número.
nhahtdh
9
Uno podría reafirmar que el problema es para enteros sin signo y luego dos complementos no entran en juego en absoluto.
R .. GitHub DEJA DE AYUDAR A HIELO
55
Aún más simple, en mi humilde opinión ~x == -(x+1), así ~(x+y) == ~x + ~yimplica -(x+y+1) == -(x+1) + -(y+1)implica-1 == -2
BlueRaja - Danny Pflughoeft
77
@BillyONeal, no te preocupes, solo bromeaba y agradezco que lo hayas mencionado :). Te compraré una bebida el día que me encuentre con una máquina que realice la aritmética complementaria ... ¿cómo suena eso? jaja
Alex Lockwood
113

Complemento de dos

En la gran mayoría de las computadoras, si xes un número entero, entonces -xse representa como ~x + 1. De manera equivalente, ~x == -(x + 1). Hacer esta sustitución en su ecuación da:

  • ~ x + ~ y == ~ (x + y)
  • - (x + 1) + - (y + 1) = - ((x + y) + 1)
  • -x - y - 2 = -x - y - 1
  • -2 = -1

lo cual es una contradicción, por ~x + ~y == ~(x + y)lo que siempre es falso .


Dicho esto, los pedantes señalarán que C no requiere el complemento de dos, por lo que también debemos considerar ...

Complemento de uno

En el complemento de uno , -xsimplemente se representa como ~x. Cero es un caso especial, que tiene representaciones de todo-0 ( +0) y todo-1 ( -0), pero IIRC, C requiere +0 == -0incluso si tienen patrones de bits diferentes, por lo que esto no debería ser un problema. Solo sustitúyalo ~por -.

  • ~ x + ~ y == ~ (x + y)
  • -x + (-y) = - (x + y)

lo cual es cierto para todos xy y.

dan04
fuente
13
+1 para una respuesta que realmente considera el complemento de dos y el complemento de uno en igualdad de condiciones.
un CVn
13
@ dan04, +0 == -0. Finalmente algo que tiene sentido en C. :)
Alex Lockwood
32

Considere solo el bit más a la derecha de ambos xy y(IE. Si x == 13está 1101en la base 2, solo veremos el último bit, a 1) Luego hay cuatro casos posibles:

x = 0, y = 0:

LHS: ~ 0 + ~ 0 => 1 + 1 => 10
RHS: ~ (0 + 0) => ~ 0 => 1

x = 0, y = 1:

LHS: ~ 0 + ~ 1 => 1 + 0 => 1
RHS: ~ (0 + 1) => ~ 1 => 0

x = 1, y = 0:

Voy a dejar esto en manos de usted ya que esto es tarea (pista: es lo mismo que el anterior con x e y intercambiados).

x = 1, y = 1:

Te dejaré esto a ti también.

Puede mostrar que el bit más a la derecha siempre será diferente en el lado izquierdo y en el lado derecho de la ecuación dada cualquier entrada posible, por lo que ha demostrado que ambos lados no son iguales, ya que tienen al menos ese bit invertido de cada uno.

Pablo
fuente
27

Si el número de bits es n

~x = (2^n - 1) - x
~y = (2^n - 1) - y


~x + ~y = (2^n - 1) +(2^n - 1) - x - y =>  (2^n + (2^n - 1) - x - y ) - 1 => modulo: (2^n - 1) - x - y - 1.

Ahora,

 ~(x + y) = (2^n - 1) - (x + y) = (2^n - 1) - x - y.

Por lo tanto, siempre serán desiguales, con una diferencia de 1.

Karthik Kumar Viswanathan
fuente
44
@nhahtdh y ¿cómo define la ~operación en números de ancho no fijo?
hamstergene
1
Di esta respuesta con este número de bits para que sea fácil de correlacionar con lo que se enseña en las clases. Tenga en cuenta que ~ x depende en gran medida del número de bits, n, que se utiliza para representar el número. Por lo tanto, es sensato apegarse a uno cuando se intenta verificar esto experimentalmente.
Karthik Kumar Viswanathan
1
@hamstergene: Sé que el número de bits es fijo, pero mi punto es que no tiene que ser esa cantidad (8, 16, etc.).
nhahtdh
1
Esos son valores para los cuales es fácil escribir un programa para verificar la respuesta. Funciona para cualquier n, siempre que ~ x y ~ y se escriban para que coincidan con lo dado.
Karthik Kumar Viswanathan
1
@hamstergene: No tengo problemas con la prueba, solo que los números dan la falsa implicación de que solo funciona para esos casos.
nhahtdh
27

Insinuación:

x + ~x = -1(mod 2 n )

Asumiendo que el objetivo de la pregunta es probar sus matemáticas (en lugar de sus habilidades de leer las especificaciones C), esto debería llevarlo a la respuesta.

usuario541686
fuente
2
Solo en máquinas complementarias de dos. (El estándar C no requiere eso)
Billy ONeal
12
@Billy: Eso es como decir "solo para personas con dos brazos".
dan04
2
@ dan04: No, no lo es. Me encantaría decir que toda la magnitud firmada y las representaciones complementarias desaparecieron del mundo. Pero me equivocaría al decir eso. El estándar C no le permite hacer esa suposición; por lo tanto, diría que el código que hace esa suposición es un código incorrecto la mayor parte del tiempo (Particularmente cuando generalmente hay mejores formas de jugar con números con signo que un poco de giro; y particularmente cuando los números sin signo son probablemente una mejor opción la mayor parte del tiempo de todos modos)
Billy ONeal
10

En el complemento de uno y dos (e incluso en 42), esto se puede probar:

~x + ~y == ~(x + a) + ~(y - a)

Ahora deja a = yy tenemos:

~x + ~y == ~(x + y) + ~(y - y)

o:

~x + ~y == ~(x + y) + ~0

Por lo tanto, en el complemento a dos ~0 = -1, la proposición es falsa.

En complemento a eso ~0 = 0, la proposición es verdadera.

ypercubeᵀᴹ
fuente
7

Según el libro de Dennis Ritchie, C no implementa el complemento de dos por defecto. Por lo tanto, su pregunta puede no ser siempre cierta.

usuario1457474
fuente
5

Dejar MAX_INTser el int representado por 011111...111(por muchos bits que haya). Entonces lo sabrás ~x + x = MAX_INTy ~y + y = MAX_INT, por lo tanto, sabrás con certeza que la diferencia entre ~x + ~yy ~(x + y)es 1.

Adrian Monk
fuente
5

C no requiere que el complemento a dos sea lo que se implementa. Sin embargo, para enteros sin signo se aplican lógicas similares. ¡Las diferencias siempre serán 1 bajo esta lógica!

usuario1422551
fuente
3

Por supuesto, C no requiere este comportamiento porque no requiere la representación del complemento de dos. Por ejemplo, ~x = (2^n - 1) - x& ~y = (2^n - 1) - yobtendrá este resultado.

usuario1472392
fuente
0

¡Ah, matemática discreta fundamental!

Echa un vistazo a la ley de De Morgan

~x & ~y == ~(x | y)

~x | ~y == ~(x & y)

¡Muy importante para las pruebas booleanas!

David Kaczynski
fuente
Simplemente mal. En C + es suma, * multiplicación y no booleana o o y.
nalply
Gracias por señalar los operadores incorrectos, finalmente. Ahora se ha actualizado con los operadores correctos, aunque tiene razón en que no se aplica a la pregunta original.
David Kaczynski
1
Bueno, si verdadero es uno y falso es cero, entonces + y * se comportan exactamente como o y y, además, el complemento de dos se comporta como no, por lo tanto, la ley se aplica de todos modos.
a1an
Gracias por señalar eso, a1an. Estaba tratando de pensar en cómo las Leyes de De Morgan podrían seguir siendo aplicables a la pregunta original, pero han pasado varios años desde que estudié programación en C o Matemática discreta.
David Kaczynski