Esse código sempre é avaliado como falso? Ambas as variáveis são entradas assinadas do complemento de duas.
~x + ~y == ~(x + y)
Sinto que deve haver um número que satisfaça as condições. Tentei testar os números entre -5000
e 5000
nunca alcançou a igualdade. Existe uma maneira de configurar uma equação para encontrar as soluções para a condição?
Trocar um pelo outro causará um erro insidioso no meu programa?
true
mesmo que nunca possam assumir o complemento estrito de dois.Respostas:
Suponha, por uma questão de contradição, que existem alguns
x
e algunsy
(mod 2 n ) tais quePelo complemento de dois *, sabemos que,
Observando esse resultado, temos,
Portanto, uma contradição. Portanto,
~(x+y) != ~x + ~y
para todosx
ey
(mod 2 n ).* É interessante notar que em uma máquina com aritmética de complemento, a igualdade é verdadeira para todos
x
ey
. Isto é porque sob o complemento de alguém~x = -x
. Assim~x + ~y == -x + -y == -(x+y) == ~(x+y)
,.fonte
~x == -(x+1)
, então~(x+y) == ~x + ~y
implica-(x+y+1) == -(x+1) + -(y+1)
implica-1 == -2
Complemento Dois
Na grande maioria dos computadores, se
x
for um número inteiro,-x
é representado como~x + 1
. Equivalentemente~x == -(x + 1)
. Fazer esta subestação em sua equação fornece:o que é uma contradição, por isso
~x + ~y == ~(x + y)
é sempre falso .Dito isto, os pedantes apontam que C não requer complemento de dois, por isso devemos considerar também ...
Um complemento
No complemento de alguém ,
-x
é simplesmente representado como~x
. Zero é um caso especial, com as representações all-0 (+0
) e all-1 (-0
), mas o IIRC, C exige+0 == -0
mesmo que tenham padrões de bits diferentes, portanto, isso não deve ser um problema. Apenas substitua~
por-
.o que é verdade para todos
x
ey
.fonte
+0 == -0
,. Finalmente algo que faz sentido no C. :)Considere apenas o bit mais à direita de ambos
x
ey
(oux == 13
seja, se estiver1101
na base 2, veremos apenas o último bit1
): a ) Existem quatro casos possíveis:x = 0, y = 0:
x = 0, y = 1:
x = 1, y = 0:
x = 1, y = 1:
Você pode mostrar que o bit mais à direita sempre será diferente no lado esquerdo e no lado direito da equação, considerando qualquer entrada possível; portanto, você provou que ambos os lados não são iguais, pois têm pelo menos aquele bit que é invertido de um para o outro.
fonte
Se o número de bits for n
Agora,
Portanto, eles sempre serão desiguais, com uma diferença de 1.
fonte
~
operação em números de largura não fixa?Dica:
x + ~x = -1
(mod 2 n )Supondo que o objetivo da pergunta seja testar sua matemática (em vez de suas habilidades de ler as especificações C), isso deve levá-lo à resposta.
fonte
No complemento de um e de dois (e até de 42), isso pode ser provado:
Agora vamos
a = y
e temos:ou:
Portanto, no complemento de dois
~0 = -1
, a proposição é falsa.No complemento de alguém
~0 = 0
, a proposição é verdadeira.fonte
De acordo com o livro de Dennis Ritchie, C não implementa o complemento de dois por padrão. Portanto, sua pergunta nem sempre pode ser verdadeira.
fonte
Letting
MAX_INT
seja o int representado por011111...111
(por quantos bits houver). Então você sabe disso~x + x = MAX_INT
e~y + y = MAX_INT
, portanto, saberá com certeza que a diferença entre~x + ~y
e~(x + y)
é1
.fonte
C não exige que o complemento de dois seja o que é implementado. No entanto, para números inteiros não assinados, lógicas semelhantes são aplicadas. As diferenças sempre serão 1 sob essa lógica!
fonte
Obviamente, C não exige esse comportamento porque não requer representação de complemento de dois. Por exemplo,
~x = (2^n - 1) - x
e~y = (2^n - 1) - y
irá obter este resultado.fonte
Ah, matemática discreta fundamental!
Confira a Lei de De Morgan
Muito importante para provas booleanas!
fonte