Como provar que a instrução C -x, ~ x+1 e ~ (x -1) produzem os mesmos resultados?

Question

Quero saber a lógica por trás dessa afirmação, a prova. A expressão c -x, ~ x+1 e ~ (x -1) produzem os mesmos resultados para qualquer x. Eu posso mostrar que isso é verdade para exemplos específicos. Eu acho que a maneira de provar isso tem algo a ver com as propriedades do complemento de dois. Alguma ideia?

Answer 1

Considere o que você obtém ao adicionar um número ao seu complemento bit. O complemento bitweep de um número inteiro N de N tem 1 em todos os lugares X tem um 0 e vice-versa. Então está claro para ver:

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

Independentemente do número de bits em x. Além disso, observe que adicionar um a um número de N bits preenchido com todos os fará de zero. Assim vemos:

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

Da mesma forma, note (x - 1) + ~ (x - 1) = 0b11 ... 11. Então (x - 1) + ~ (x - 1) + 1 = 0 e ~ (x - 1) = -x.

Answer 2

Não tenho certeza de que você possa provar isso de qualquer tipo de axioma útil que não seja a redução trivial de volta ao fato de termos definido números negativos no número inteiro moderno de estar em dois complementos.

Computadores não tenho Para ser implementado com o hardware binário complementar dois, é apenas que existem várias propriedades atraentes e quase tudo é construído dessa maneira hoje em dia. (Mas não ponto flutuante! Esses são o complemento de alguém!)

Portanto, construímos uma máquina que representa números negativos no complemento de 2. Expressões que mostram números negativos a serem representados no complemento de dois são precisos, mas apenas porque os definimos dessa maneira. Essa é a base axiomática para números inteiros negativos nas máquinas modernas.

Como definimos a negação em termos do complemento de dois, você está se referindo essencialmente aos axiomas, embora eu suponha que seja isso que todas as provas finalmente fazem.

Talvez seja por isso que eu não sou realmente um cara da teoria. :-)

Answer 3

~ x + 1 é equivalente ao complemento de 2 + 1 (ou seja, número negativo) representações de -x, ~ (x-1) também representa o mesmo (considere o caso em que o último bit é 1, ~ (x-1) = ~ ((~ ( b1b2.b (n-1) 1-0) = b1'b2 '... b (n-1)' 1 = b1'b2 '... b (n-1)' 0 + 1 = ~ x + 1. A retenção de caso semelhante para o último bit é 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

Vou tentar apresentar uma explicação intuitiva que todos devem encontrar. Se você insistir, podemos tentar uma abordagem mais formal.

Na representação do complemento de dois, para ter uma representação única do elemento zero, sacrificamos um elemento positivo. Como resultado, há um número extra negativo que não tem espelho positivo.

Então, com 2 bits, obtemos: {+1, 0, -1, -2} que seria representado em binário como:

-2    10
-1    11
 0    00
+1    01

Então, podemos pensar no zero como um espelho. Agora, dado um número inteiro X, se quisermos inverter seu sinal, podemos começar invertendo todos os bits. Isso seria suficiente se não houvesse zero entre os pontos positivos e negativos. Mas como o zero faz uma mudança, em positivos, temos compensado por isso.

As duas expressões mencionadas na questão fazem desta compensação antes ~(x-1) e depois ~x+1 invertendo os bits. Você pode verificar facilmente que usando +1 e -1 em nosso exemplo de 2 bits.

Answer 5

Em geral, isso não é verdadeiro, pois o padrão C não requer o uso de dois complemento para representar números negativos.

Em particular, o resultado da aplicação ~ a um tipo assinado não está definido.

No entanto, até onde eu conheço, todas as máquinas modernas usam dois complementares para números inteiros.