second - signed binary to decimal

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

Question

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

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

Siento que debería haber un número que satisfaga las condiciones. -5000 probando los números entre -5000 y 5000 pero nunca -5000 igualdad. ¿Hay alguna manera de configurar una ecuación para encontrar las soluciones a la condición?

¿Intercambiar uno por el otro causa un error insidioso en mi programa?

Answer 1

Complemento de dos

En la gran mayoría de las computadoras, si x es un número entero, entonces -x se representa como ~x + 1 . Equivalentemente, ~x == -(x + 1) . Hacer esta substución en tu ecuación te 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, entonces ~x + ~y == ~(x + y) siempre es falso .

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

El complemento de uno

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

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

que es cierto para todo x y y .

Answer 2

¡Ah, matemáticas discretas fundamentales!

Echa un vistazo a la Ley de Morgan

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

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

¡Muy importante para las pruebas booleanas!

Answer 3

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

Answer 4

Considere solo el bit más a la derecha tanto de x como de y (es decir, si x == 13 que es 1101 en base 2, solo veremos el último bit, a 1 ) Entonces 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 a usted, ya que esta es la tarea (sugerencia: es lo mismo que el anterior con xy y intercambiado).

x = 1, y = 1:

También te dejaré esto a ti.

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

Answer 5

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

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

Ahora deje a = y y tenemos:

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

o:

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

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

En un complemento que ~0 = 0 , la proposición es verdadera.

Answer 6

Permitir que MAX_INT sea ​​el int representado por 011111...111 (para todos los bits que haya). Entonces sabrá que, ~x + x = MAX_INT y ~y + y = MAX_INT , por lo tanto, sabrá con certeza que la diferencia entre ~x + ~y y ~(x + y) es 1 .

Answer 7

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

Answer 8

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.

Answer 9

Si la cantidad 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.

Answer 10

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

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

Para 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 + ~y para todo x e y (mod 2 ⁿ ).

^{* Es interesante observar que en una máquina con la aritmética de un complemento, la igualdad en realidad es válida para todos los x e y . Esto es porque bajo el complemento de uno, ~x = -x . Por lo tanto, ~x + ~y == -x + -y == -(x+y) == ~(x+y) .}

Answer 11

Insinuación:

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

Suponiendo que el objetivo de la pregunta es poner a prueba tus conocimientos matemáticos (en lugar de tus habilidades de lectura con especificaciones C), esto debería llevarte a la respuesta.