~ x + ~ y == ~ (x + y) é sempre falso?

153

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 -5000e 5000nunca 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?

Steve
fonte
6
Você quer uma prova ou algo assim?
Alvin Wong
26
Esteja ciente de que, nos casos de estouro de número inteiro assinado, é um comportamento tecnicamente indefinido. Portanto, é possível retornar truemesmo que nunca possam assumir o complemento estrito de dois.
Mysticial
1
@AlvinWong sim uma explicação seria bom
Steve
1
@ Steve: você pode demonstrar que tentou todos os suspeitos comuns (-1, 0, 1, 2 e assim por diante) em todas as combinações, bem como suas tentativas de "resolver" o problema para tamanhos de palavras pequenos ( três bits? quatro bits?). Definitivamente, isso nos ajudaria a nos convencer de que não estamos apenas ajudando alguém a conseguir algo que não tentou ganhar primeiro. :)
sarnold
4
@AlexLockwood Quando publiquei a pergunta pela primeira vez, presumi que a marcação da pergunta como "lição de casa" pede às pessoas que forneçam pistas para me ajudar a resolver o problema (conforme a descrição da tag "lição de casa") e não apenas dê respostas. É por isso que apenas claramente a pergunta do problema :)
Steve

Respostas:

237

Suponha, por uma questão de contradição, que existem alguns xe alguns y(mod 2 n ) tais que

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

Pelo complemento de dois *, sabemos que,

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

Observando esse resultado, temos,

      ~(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

Portanto, uma contradição. Portanto, ~(x+y) != ~x + ~ypara todos xe y(mod 2 n ).


* É interessante notar que em uma máquina com aritmética de complemento, a igualdade é verdadeira para todos xe y. Isto é porque sob o complemento de alguém ~x = -x. Assim ~x + ~y == -x + -y == -(x+y) == ~(x+y),.

Alex Lockwood
fonte
47
É claro que C não exige esse comportamento; pois não requer representação de complemento de dois.
Billy ONeal
12
Aliás, a igualdade é verdadeira para o complemento de alguém. A operação NOT não é realmente definida para o número em geral, portanto, misturar NOT com adição resulta em um comportamento diferente, dependendo da representação do número.
N
9
Pode-se apenas reafirmar o problema para números inteiros não assinados e, em seguida, dois complementos não entram em jogo.
R .. GitHub Pare de ajudar o gelo
5
Ainda mais simples, IMHO: ~x == -(x+1), então ~(x+y) == ~x + ~yimplica -(x+y+1) == -(x+1) + -(y+1)implica-1 == -2
BlueRaja - Danny Pflughoeft
7
@ BillyONeal, não se preocupe, eu estava apenas brincando e agradeço que você tenha mencionado isso :). Vou comprar uma bebida para você no dia em que encontrar uma máquina que faça a aritmética de complemento ... como isso soa? haha
Alex Lockwood
113

Complemento Dois

Na grande maioria dos computadores, se xfor um número inteiro, -xé representado como ~x + 1. Equivalentemente ~x == -(x + 1). Fazer esta subestação em sua equação fornece:

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

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 == -0mesmo que tenham padrões de bits diferentes, portanto, isso não deve ser um problema. Apenas substitua ~por -.

  • (x + y) = x + y
  • Dê sua nota! Dê sua nota!

o que é verdade para todos xe y.

dan04
fonte
13
+1 para uma resposta que realmente considere o complemento de dois e o complemento de um em igualdade de condições.
um CVn
13
@ dan04 +0 == -0,. Finalmente algo que faz sentido no C. :)
Alex Lockwood
32

Considere apenas o bit mais à direita de ambos xe y(ou x == 13seja, se estiver 1101na base 2, veremos apenas o último bit 1): a ) Existem quatro casos possíveis:

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:

Vou deixar isso para você, já que este é um dever de casa (dica: é o mesmo que o anterior, com x e y trocados).

x = 1, y = 1:

Vou deixar este com você também.

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.

Paulo
fonte
27

Se o número de bits for 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.

Agora,

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

Portanto, eles sempre serão desiguais, com uma diferença de 1.

Karthik Kumar Viswanathan
fonte
4
@nhahtdh e como você define a ~operação em números de largura não fixa?
hamstergene
1
Dei essa resposta com esse número de bits para facilitar a correlação com o que é ensinado nas aulas. Observe que ~ x é altamente dependente do número de bits, n, usado para representar o número. Portanto, é sensato manter um, ao tentar verificar isso experimentalmente.
Karthik Kumar Viswanathan
1
@ hamstergene: Eu sei que o número de bits é fixo, mas o que quero dizer é que ele não precisa ser esse valor (8, 16, etc.).
N
1
Esses são valores para os quais é fácil escrever um programa para verificar a resposta. Funciona para qualquer n, desde que ~ x e ~ y sejam escritos para corresponder ao dado.
Karthik Kumar Viswanathan
1
@ hamstergene: Não tenho problemas com a prova, apenas que os números dão a falsa implicação de que só funciona para esses casos.
N
27

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.

user541686
fonte
2
Somente em máquinas completas para dois. (O padrão C não requer que)
Billy ONeal
12
@ Billy: Isso é como dizer "apenas para pessoas com dois braços".
dan04
2
@ dan04: Não, não é. Eu adoraria dizer que toda a magnitude assinada e as representações complementares se foram do mundo. Mas eu estaria errado em dizer isso. O padrão C não permite que você faça essa suposição; portanto, eu diria que o código que faz essa suposição é um código incorreto na maioria das vezes. (Especialmente quando geralmente há melhores maneiras de brincar com números assinados que pouco twiddling, e particularmente quando os números não assinados são provavelmente a melhor escolha na maioria das vezes de qualquer maneira)
Billy ONeal
10

No complemento de um e de dois (e até de 42), isso pode ser provado:

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

Agora vamos a = ye temos:

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

ou:

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

Portanto, no complemento de dois ~0 = -1, a proposição é falsa.

No complemento de alguém ~0 = 0, a proposição é verdadeira.

ypercubeᵀᴹ
fonte
7

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.

user1457474
fonte
5

Letting MAX_INTseja o int representado por 011111...111(por quantos bits houver). Então você sabe disso ~x + x = MAX_INTe ~y + y = MAX_INT, portanto, saberá com certeza que a diferença entre ~x + ~ye ~(x + y)é 1.

Adrian Monk
fonte
5

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!

user1422551
fonte
3

Obviamente, C não exige esse comportamento porque não requer representação de complemento de dois. Por exemplo, ~x = (2^n - 1) - xe ~y = (2^n - 1) - yirá obter este resultado.

user1472392
fonte
0

Ah, matemática discreta fundamental!

Confira a Lei de De Morgan

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

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

Muito importante para provas booleanas!

David Kaczynski
fonte
Simplesmente errado. Em C + é adição, * multiplicação e não booleano ou ou e.
nalply
Obrigado por apontar os operadores incorretos, nalply. Agora ele foi atualizado com os operadores corretos, embora você esteja certo, pois não se aplica à pergunta original.
David Kaczynski
1
Bem, se verdadeiro é um e falso é zero, + e * se comportam exatamente como ou e, além disso, o complemento de dois se comporta como não, portanto a lei se aplica.
a1an
Obrigado por apontar isso, a1an. Eu estava tentando pensar em como as leis de De Morgan ainda poderiam ser aplicáveis ​​à questão original, mas já faz vários anos desde que estudei programação C ou Matemática Discreta.
David Kaczynski