Czy ten kod zawsze daje wynik fałszywy? Obie zmienne są liczbami int ze znakiem uzupełnienia do dwóch.

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

Wydaje mi się, że powinna istnieć liczba spełniająca warunki. Próbowałem sprawdzić liczby pomiędzy -5000i, 5000ale nigdy nie osiągnąłem równości. Czy istnieje sposób na utworzenie równania, aby znaleźć rozwiązania warunku?

Czy zamiana jednego na drugi spowoduje podstępny błąd w moim programie?

Załóżmy dla sprzeczności, że istnieją takie, xa niektóre y(mod 2 ⁿ ) takie

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

Dzięki dopełnieniu do dwóch * wiemy, że

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

Uwzględniając ten wynik,

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

Stąd sprzeczność. Dlatego ~(x+y) != ~x + ~ydla wszystkich xi y(mod 2 ⁿ ).

^{* Warto zauważyć, że na maszynie z własną arytmetyką dopełnień równość faktycznie obowiązuje dla wszystkich xi y. To dlatego, że pod jednym z dopełnieniem, ~x = -x. Zatem ~x + ~y == -x + -y == -(x+y) == ~(x+y).}

Dopełnienie do dwóch

W zdecydowanej większości komputerów, jeśli xjest liczbą całkowitą, to -xjest reprezentowane ~x + 1. Równoważnie ~x == -(x + 1). Dokonanie tego podstawienia w swoim równaniu daje:

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

co jest sprzecznością, więc ~x + ~y == ~(x + y)zawsze jest fałszywe .

To powiedziawszy, pedanci zwrócą uwagę, że C nie wymaga uzupełnienia do dwóch, więc musimy również rozważyć ...

Dopełnienie

W kod uzupełnień do jedności , -xjest po prostu reprezentowane ~x. Zero jest przypadkiem specjalnym, mając zarówno reprezentacje all-0 ( +0), jak i all-1 ( -0), ale IIRC, C wymaga, +0 == -0nawet jeśli mają różne wzorce bitowe, więc nie powinno to stanowić problemu. Wystarczy podstawić ~z -.

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

co jest prawdą dla wszystkich xi y.

Rozważmy tylko skrajny prawy bit z obu xi y(tj. Jeśli x == 13który jest 1101w bazie 2, przyjrzymy się tylko ostatniemu bitowi, a 1) Istnieją cztery możliwe przypadki:

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:

Zostawię to tobie, ponieważ jest to praca domowa (wskazówka: jest taka sama jak poprzednia z zamienionymi x i y).

x = 1, y = 1:

To również zostawię tobie.

Możesz pokazać, że najbardziej prawy bit będzie zawsze różny po lewej i prawej stronie równania, biorąc pod uwagę wszelkie możliwe dane wejściowe, więc udowodniłeś, że obie strony nie są równe, ponieważ mają co najmniej ten jeden odwrócony bit od siebie nawzajem.

Jeśli liczba bitów wynosi 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.

Teraz,

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

Dlatego zawsze będą nierówne, z różnicą 1.

Wskazówka:

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

Zakładając, że celem pytania jest sprawdzenie Twojej matematyki (a nie umiejętności czytania specyfikacji C), powinno to doprowadzić Cię do odpowiedzi.

W dopełnieniu zarówno jednym, jak i dwóch (a nawet w 42-ach) można to udowodnić:

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

Teraz pozwól a = yi mamy:

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

lub:

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

Dlatego w uzupełnieniu do dwóch ~0 = -1, to zdanie jest fałszywe.

W uzupełnieniu ~0 = 0, twierdzenie to jest prawdziwe.

Według książki Dennisa Ritchiego, C nie implementuje domyślnie dopełnienia do dwóch. Dlatego twoje pytanie może nie zawsze być prawdziwe.

Niech MAX_INTbędzie wartością int reprezentowaną przez 011111...111(dla dowolnej liczby bitów). Wtedy to wiesz ~x + x = MAX_INTi ~y + y = MAX_INTdlatego będziesz wiedział na pewno, że różnica między ~x + ~ya ~(x + y)jest 1.

C nie wymaga implementacji dopełnienia do dwóch. Jednak w przypadku liczb całkowitych bez znaku stosowane są podobne logiki. W tej logice różnice zawsze będą wynosić 1!

Oczywiście C nie wymaga takiego zachowania, ponieważ nie wymaga reprezentacji dopełnienia do dwóch. Na przykład ~x = (2^n - 1) - x& ~y = (2^n - 1) - yotrzyma ten wynik.

Ach, podstawowa matematyka dyskretna!

Sprawdź prawo De Morgana

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

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

Bardzo ważne dla dowodów logicznych!