Co to jest „Uzupełnienie 2”?

434

Jestem na kursie systemów komputerowych i częściowo zmagam się z Two's Complement . Chcę to zrozumieć, ale wszystko, co przeczytałem, nie przyniosło mi tego obrazu. Przeczytałem artykuł w Wikipedii i różne inne artykuły, w tym moją książkę .

Dlatego chciałem rozpocząć ten post na wiki społeczności, aby zdefiniować, czym jest Uzupełnienie Two, jak go używać i jak może wpływać na liczby podczas operacji takich jak rzutowania (od podpisanego do niepodpisanego i odwrotnie), operacji bitowych i operacji przesunięcia bitowego .

Mam nadzieję na jasną i zwięzłą definicję, którą programista z łatwością zrozumie.

Frank V.
źródło

Odpowiedzi:

627

Uzupełnienie dwóch to sprytny sposób przechowywania liczb całkowitych, dzięki czemu typowe problemy matematyczne są bardzo łatwe do wdrożenia.

Aby zrozumieć, musisz pomyśleć o liczbach binarnych.

Zasadniczo mówi:

  • dla zera użyj wszystkich zer.
  • dla dodatnich liczb całkowitych zacznij odliczanie, maksymalnie 2 (liczba bitów - 1) -1.
  • dla liczb całkowitych ujemnych wykonaj dokładnie to samo, ale zmień rolę zer i jedynek (więc zamiast zaczynać od 0000, zacznij od 1111 - to jest część „uzupełniająca”).

Spróbujmy z minibajtem 4 bitów (nazwiemy to skubaniem - 1/2 bajtu).

  • 0000 - zero
  • 0001 - jeden
  • 0010 - dwa
  • 0011 - trzy
  • 0100do 0111- od czterech do siedmiu

To, o ile możemy posunąć się w pozytywach. 2 3 -1 = 7.

W przypadku negatywów:

  • 1111 - negatywny
  • 1110 - dwa ujemne
  • 1101 - trzy negatywne
  • 1100do 1000- ujemna cztery do ujemnej osiem

Zauważ, że dostajesz jedną dodatkową wartość dla negatywów ( 1000= -8), której nie dla pozytywów. Dzieje się tak, ponieważ 0000stosuje się zero. Można to uznać za linię liczbową komputerów.

Rozróżnianie liczb dodatnich i ujemnych

W ten sposób pierwszy bit otrzymuje rolę „znaku”, ponieważ można go użyć do odróżnienia nieujemnych i ujemnych wartości dziesiętnych. Jeśli najbardziej znaczącym bitem jest 1, to binarny można powiedzieć, że jest ujemny, a jeśli tak, jak gdyby najbardziej znaczący bit (skrajnie lewy) 0, można powiedzieć, że wartość dziesiętna jest nieujemna.

Liczby ujemne „uzupełnienia” po prostu odwracają bit znaku, a następnie liczą od 0. Ale to podejście musi zajmować się interpretowaniem 1000jako „zero ujemne”, co jest mylące. Zasadniczo musisz się tym martwić, gdy pracujesz blisko sprzętu.

lavinio
źródło
146
Prawdopodobnie najlepszą częścią uzupełnienia dwóch jest to, jak upraszcza matematykę. Spróbuj dodać 2 (0010) i -2 (1110), a dostaniesz 10000. Najbardziej znaczącym bitem jest przepełnienie, więc wynik jest w rzeczywistości 0000. Prawie jak magia, 2 + -2 = 0.
Naaff
96
Kolejną zaletą oprócz łatwego dodawania i odejmowania jest to, że uzupełnienie 2s ma tylko jedno zero. Jeśli używasz prostego bitu znakowego, powiedzmy, używając 0001 do reprezentowania +1 i 1001 do reprezentowania -1, masz dwa zera: 0000 („+0”) i 1000 („-0”). To prawdziwy ból z tyłu.
Jörg W Mittag
26
Głosujcie za tym, aby do rzeczy, a także za wyjaśnienie, dlaczego wartości ujemne mają większy zakres wartości dodatnie. Przyszedłem szukać przyczyny różnicy zasięgu.
Ashwin
2
Czy nie powinieneś powiedzieć „dla liczb całkowitych ujemnych, zrób dokładnie to samo, ale odlicz i zmień rolę
Koray Tugay
1
Niesamowite. Dodano dodatkowe części konwersji bitów na ujemną liczbę całkowitą.
Suraj Jain
339

Zastanawiam się, czy można to wyjaśnić lepiej niż artykuł w Wikipedii.

Podstawowym problemem, który próbujesz rozwiązać za pomocą reprezentacji uzupełnienia do dwóch, jest przechowywanie ujemnych liczb całkowitych.

Najpierw rozważ liczbę całkowitą bez znaku przechowywaną w 4 bitach. Możesz mieć następujące

0000 = 0
0001 = 1
0010 = 2
...
1111 = 15

Są niepodpisane, ponieważ nie ma wskazania, czy są negatywne, czy pozytywne.

Znak wielkości i notacja przekroczenia

Aby przechowywać liczby ujemne, możesz wypróbować wiele rzeczy. Po pierwsze, można użyć notacji wielkości znaku, która przypisuje pierwszy bit jako bit znaku reprezentujący +/-, a pozostałe bity reprezentują wielkość. Więc używając ponownie 4 bity i zakładając, że 1 oznacza - a 0 oznacza +, to masz

0000 = +0
0001 = +1
0010 = +2
...
1000 = -0
1001 = -1
1111 = -7

Widzisz tam problem? Mamy dodatnie i ujemne 0. Większy problem polega na dodawaniu i odejmowaniu liczb binarnych. Obwody do dodawania i odejmowania za pomocą wielkości znaku będą bardzo złożone.

Co jest

0010
1001 +
----

?

Innym systemem jest nadmiar notacji . Możesz przechowywać liczby ujemne, pozbywasz się problemu dwóch zer, ale dodawanie i odejmowanie pozostaje trudne.

Więc pojawia się uzupełnienie dwóch. Teraz możesz przechowywać dodatnie i ujemne liczby całkowite oraz wykonywać arytmetykę ze względną łatwością. Istnieje wiele metod konwersji liczby na uzupełnienie dwóch. Tutaj jest jeden.

Konwertuj Dziesiętny na Uzupełnienie dwójkowe

  1. Konwertuj liczbę na binarną (na razie zignoruj ​​znak), np. 5 to 0101, a -5 to 0101

  2. Jeśli liczba jest liczbą dodatnią, to koniec. np. 5 oznacza binarnie 0101 przy użyciu notacji uzupełniającej dwójki.

  3. Jeśli liczba jest ujemna, to

    3.1 znajdź dopełniacz (odwróć 0 i 1), np. -5 to 0101, więc znalezienie dopełniacza to 1010

    3.2 Dodaj 1 do dopełniacza 1010 + 1 = 1011. Dlatego -5 w uzupełnieniu do dwóch wynosi 1011.

Co jeśli chcesz zrobić 2 + (-3) w systemie binarnym? 2 + (-3) wynosi -1. Co musiałbyś zrobić, gdybyś używał wielkości znaku, aby dodać te liczby? 0010 + 1101 =?

Korzystając z uzupełnienia do dwóch, zastanów się, jak łatwo byłoby.

 2  =  0010
 -3 =  1101 +
 -------------
 -1 =  1111

Konwertowanie dopełnienia dwóch na dziesiętne

Konwersja 1111 na dziesiętne:

  1. Liczba zaczyna się od 1, więc jest ujemna, więc znajdujemy uzupełnienie 1111, czyli 0000.

  2. Dodaj 1 do 0000, a otrzymamy 0001.

  3. Konwertuj 0001 na dziesiętne, czyli 1.

  4. Zastosuj znak = -1.

Tada!

Vincent Ramdhanie
źródło
45
Najlepsza odpowiedź moim zdaniem.
Koray Tugay
5
tak, ten jest dość prosty i bardzo dobrze wyjaśnia sprawę
Max Koretskyi
3
Nie rozumiem, jak dodanie jednego przy konwersji w obie strony zawsze prowadzi do tej samej liczby. Moim zdaniem cofniesz kroki lub odejmiesz jeden czy coś.
Marcos Pereira,
2
Po co dodawać 1 do uzupełnienia?
Zinan Xing
4
Tej odpowiedzi należy użyć na Wikipedii.
Hiroki,
119

Podobnie jak większość wyjaśnień, które widziałem, powyższe wyjaśniają, jak pracować z uzupełnieniem 2, ale tak naprawdę nie wyjaśniają, czym matematyczne. Spróbuję to zrobić, przynajmniej dla liczb całkowitych, i omówię tło, które prawdopodobnie jest najpierw znane.

Przypomnij sobie, jak to działa w przypadku liczb dziesiętnych:
  2345
to sposób pisania
  2 × 10 3 + 3 × 10 2 + 4 × 10 1 + 5 × 10 0 .

W ten sam sposób, binarny jest sposobem pisania liczb przy użyciu tylko 0 i 1 zgodnie z tym samym ogólnym pomysłem, ale zastępując te 10 powyżej 2s. Następnie w formacie binarnym
   1111
jest sposobem na napisanie
  1 × 2 3 + 1 × 2 2 + 1 × 2 1 + 1 × 2 0,
a jeśli się uda, okaże się, że wynosi 15 (podstawa 10). To dlatego, że jest to
  8 + 4 + 2 + 1 = 15.

To wszystko dobrze i dobrze dla liczb dodatnich. Działa nawet w przypadku liczb ujemnych, jeśli chcesz po prostu umieścić przed nimi znak minus, tak jak ludzie robią to z liczbami dziesiętnymi. Można to zrobić nawet na komputerach, ale nie widziałem takiego komputera od wczesnych lat siedemdziesiątych. Zostawię powody innej dyskusji.

W przypadku komputerów bardziej wydajne jest stosowanie reprezentacji uzupełnienia dla liczb ujemnych. A oto coś, co często jest pomijane. Notacje dopełniające obejmują pewnego rodzaju odwrócenie cyfr liczby, nawet implikowanych zer poprzedzających normalną liczbę dodatnią. To niezręczne, ponieważ powstaje pytanie: wszystkie? Może to być nieskończona liczba cyfr, które należy wziąć pod uwagę.

Na szczęście komputery nie reprezentują nieskończoności. Liczby są ograniczone do określonej długości (lub szerokości, jeśli wolisz). Wróćmy więc do dodatnich liczb binarnych, ale o określonym rozmiarze. W tych przykładach użyję 8 cyfr („bitów”). Nasz numer binarny to tak naprawdę
  00001111
lub
  0 × 2 7 + 0 × 2 6 + 0 × 2 5 + 0 × 2 4 + 1 × 2 3 + 1 × 2 2 + 1 × 2 1 + 1 × 2 0

Aby utworzyć ujemne uzupełnienie 2, najpierw uzupełniamy wszystkie (binarne) cyfry, tworząc
  11110000,
i dodajemy 1, tworząc
  11110001,
ale jak mamy to rozumieć jako -15?

Odpowiedź brzmi: zmieniamy znaczenie bitu wyższego rzędu (skrajnie lewy). Ten bit będzie wynosił 1 dla wszystkich liczb ujemnych. Zmiana polegać będzie na zmianie znaku jego udziału w wartości liczby, w której się pojawia. Teraz nasz 11110001 jest rozumiany jako
  - 1 × 2 7 + 1 × 2 6 + 1 × 2 5 + 1 × 2 4 + 0 × 2 3 + 0 × 2 2 + 0 × 2 1 + 1 × 2 0
Zauważ, że „-” przed tym wyrażeniem? Oznacza to, że bit znaku ma ciężar -2 7 , czyli -128 (podstawa 10). Wszystkie pozostałe pozycje zachowują tę samą wagę, co w liczbach binarnych bez znaku.

Wypracowanie naszego -15 to
  -128 + 64 + 32 + 16 + 1
Wypróbuj na swoim kalkulatorze. jest -15.

Spośród trzech głównych sposobów, w jakie widziałem liczby ujemne reprezentowane w komputerach, dopełnienie 2 wygrywa zdecydowanie dla wygody w ogólnym użyciu. Ma jednak dziwność. Ponieważ jest binarny, musi istnieć parzysta liczba możliwych kombinacji bitów. Każdą liczbę dodatnią można powiązać z jej ujemną, ale jest tylko jedno zero. Negowanie zera daje zero. Jest jeszcze jedna kombinacja, liczba z 1 w bicie znaku i 0 wszędzie indziej. Odpowiednia liczba dodatnia nie pasowałaby do liczby używanych bitów.

Jeszcze bardziej dziwne w tej liczbie jest to, że jeśli spróbujesz uformować liczbę dodatnią, uzupełniając ją i dodając, otrzymujesz z powrotem tę samą liczbę ujemną. Wydaje się naturalne, że zero by to zrobiło, ale jest to nieoczekiwane i wcale nie jest to zachowanie, do którego jesteśmy przyzwyczajeni, ponieważ poza komputerami, ogólnie myślimy o nieograniczonej podaży cyfr, a nie o arytmetyki o stałej długości.

To jest jak wierzchołek góry lodowej osobliwości. Pod powierzchnią czeka jeszcze więcej, ale to wystarczy na tę dyskusję. Prawdopodobnie można znaleźć więcej, badając „przepełnienie” arytmetyki stałoprzecinkowej. Jeśli naprawdę chcesz się w to zaangażować, możesz także zbadać „arytmetykę modułową”.

ForDummies
źródło
1
Podoba mi się ta odpowiedź! Wyjaśnia, jak biorąc uzupełnienie 2 i dodanie jednego działa.
SJ.
Podoba mi się również ta odpowiedź. Zwłaszcza tam, gdzie pokazuje się liczbę ujemną. Tutaj myślałem, że cała liczba została odwrócona, nie tylko MSB, a następnie dodała inne ważone wartości. Dziękuję, to rozwiązało mój blok mózgowy
użytkownik188757
Dobra robota, wymieniając liczbę nieparzystą, która nie ma odwrotności. Ale co z tym zrobimy? Czy ustawiamy flagę przepełnienia, jeśli ktoś próbuje ją odwrócić?
NH.
Podczas gdy inne odpowiedzi koncentrują się na „jak”, ta odpowiedź prowadzi nas delikatnie przez „dlaczego”. Pomogło mi to. Dzięki!
Abhishek Pathak
Jeśli liczba kończy się na 11000 ... 000, odwrócenie da 01000 ... 000. Notacja z dopełnieniem do dwóch jest oparta na założeniu, że wszystkie cyfry po lewej stronie reprezentowanej cyfry po lewej stronie powinny mieć taką samą wartość jak ta cyfra, ale przy odwracaniu liczby, której reprezentacja wynosi 1000 ... 000, nie będzie to prawdą.
supercat,
20

Uzupełnienie 2 jest bardzo przydatne do znalezienia wartości pliku binarnego, jednak pomyślałem o znacznie bardziej zwięzłym sposobie rozwiązania takiego problemu (nigdy nie widziałem, żeby ktokolwiek go opublikował):

weźmy plik binarny, na przykład: 1101, który jest [zakładając, że spacja „1” jest znakiem] równa -3 .

używając dopełnienia 2, zrobilibyśmy to ... odwróć 1101 na 0010 ... dodaj 0001 + 0010 ===> daje nam 0011. 0011 w dodatnim pliku binarnym = 3. dlatego 1101 = -3 !

Co zdałem sobie sprawę:

zamiast wszystkich przerzucania i dodawania, możesz po prostu wykonać podstawową metodę rozwiązywania pozytywnego pliku binarnego (powiedzmy 0101) to (2 3 * 0) + (2 2 * 1) + (2 1 * 0) + (2 0 * 1) = 5.

Wykonaj dokładnie tę samą koncepcję z negatywem! (Z niewielkim zwrotem akcji)

weź 1101, na przykład:

dla pierwszej liczby zamiast 2 3 * 1 = 8 , wykonaj - (2 3 * 1) = -8 .

następnie kontynuuj jak zwykle, wykonując -8 + (2 2 * 1) + (2 1 * 0) + (2 0 * 1) = -3

Simon Yundov
źródło
1
Najlepszym sposobem było zrozumienie uzupełnienia 2. Po przeczytaniu tego mogłem zrozumieć wszystkie odpowiedzi na powyższe pytanie.
Shakeel Shahzad
1
Jest to metoda wspomniana w książce Computer Systems: A programmer's perspektywy.
jimo
1
To znacznie szybszy sposób!
chanzerre
14

Wyobraź sobie, że masz skończoną liczbę bitów / tritów / cyfr / cokolwiek innego. Zdefiniujesz 0, ponieważ wszystkie cyfry są 0, i naturalnie liczysz w górę:

00
01
02
..

W końcu się przepełnisz.

98
99
00

Mamy dwie cyfry i mogą reprezentować wszystkie liczby od 0 do 100. Wszystkie te liczby są dodatnie! Załóżmy, że też chcemy reprezentować liczby ujemne?

To, co naprawdę mamy, to cykl. Liczba przed 2 to 1. Liczba przed 1 to 0. Liczba przed 0 to ... 99 .

Dla uproszczenia załóżmy, że dowolna liczba powyżej 50 jest ujemna. „0” do „49” oznaczają od 0 do 49. „99” to -1, „98” to -2,… „50” to -50.

Ta reprezentacja jest uzupełnieniem dziesięciu . Komputery zwykle używają uzupełnienia do dwóch , co jest takie samo, z wyjątkiem bitów zamiast cyfr.

Zaletą uzupełnienia dziesiątego jest to, że dodatek po prostu działa . Nie musisz robić nic specjalnego, aby dodać liczby dodatnie i ujemne!

Kapitanie Segfault
źródło
9

Przeczytałem fantastyczne wyjaśnienie na Reddit przez jng, wykorzystując licznik kilometrów jako analogię.

wprowadź opis zdjęcia tutaj

To przydatna konwencja. Te same obwody i operacje logiczne, które dodają / odejmują liczby dodatnie w formacie binarnym, nadal działają zarówno na liczbach dodatnich, jak i ujemnych, jeśli stosuje się konwencję, dlatego jest tak użyteczny i wszechobecny.

Wyobraź sobie licznik kilometrów samochodu, który kręci się w (powiedzmy) 99999. Jeśli zwiększysz 00000, otrzymasz 00001. Jeśli zmniejszysz 00000, otrzymasz 99999 (z powodu zawracania). Jeśli dodasz jedną z powrotem do 99999, wróci do 00000. Warto więc zdecydować, że 99999 reprezentuje -1. Podobnie bardzo przydatne jest stwierdzenie, że 99998 reprezentuje -2 i tak dalej. Musisz gdzieś się zatrzymać, a także, zgodnie z konwencją, górna połowa liczb jest uważana za ujemną (50000-99999), a dolna połowa dodatnia oznacza tylko siebie (00000-49999). W rezultacie, górna cyfra wynosząca 5-9 oznacza, że ​​reprezentowana liczba jest ujemna, a wartość 0-4 oznacza, że ​​reprezentowana jest dodatnia - dokładnie tak samo, jak górny bit reprezentujący znak w dwójkowej liczbie uzupełniającej dwójki.

Zrozumienie tego też było dla mnie trudne. Kiedy go dostałem i wróciłem do ponownego przeczytania artykułów z książkami i wyjaśnień (wtedy nie było internetu), okazało się, że wielu opisujących to tak naprawdę nie rozumie. Potem napisałem książkę uczącą języka asemblera (która sprzedawała się całkiem dobrze przez 10 lat).

Alister
źródło
5

Dwa uzupełnienia można znaleźć, dodając jeden do pierwszego uzupełnienia podanej liczby. Powiedzmy, że musimy znaleźć uzupełnienie dwóch, 10101a następnie znaleźć jego uzupełnienie, to znaczy 01010dodać 1do tego wyniku, to znaczy 01010+1=01011, który jest ostateczną odpowiedzią.

evaa
źródło
4

Uzyskajmy odpowiedź 10–12 w formie binarnej przy użyciu 8 bitów: Naprawdę zrobimy to 10 + (-12)

Musimy uzyskać część komplementu 12, aby odjąć ją od 10. 12 w systemie binarnym to 00001100. 10 w systemie binarnym to 00001010.

Aby uzyskać część komplementu 12, wystarczy odwrócić wszystkie bity, a następnie dodać 1. 12 w binarnie odwrócona to 11110011. Jest to również kod odwrotny (uzupełnienie własne). Teraz musimy dodać jeden, który jest teraz 11110100.

Więc 11110100 to komplement 12! Łatwe, gdy myślisz o tym w ten sposób.

Teraz możesz rozwiązać powyższe pytanie 10-12 w formie binarnej.

00001010
11110100
-----------------
11111110  
NightSky
źródło
3

Uzupełnienia 2: Kiedy dodamy dodatkowy z uzupełnieniami 1 dla liczby, otrzymamy uzupełnienia 2. Na przykład: 100101 to uzupełnienie 1 to 011010, a uzupełnienie 2 to 011010 + 1 = 011011 (Dodając jeden z uzupełnieniem 1) Aby uzyskać więcej informacji, w tym artykule wyjaśnij to graficznie.

Milon
źródło
plus 1 za link, który ma wyjaśnienie z kołem
Manohar Reddy Poreddy
3

Patrząc na matematyczny system dopełniania dwóch z matematycznego punktu widzenia, to naprawdę ma sens. W uzupełnieniu do dziesięciu pomysł polega zasadniczo na „odizolowaniu” różnicy.

Przykład: 63–24 = x

Dodajemy uzupełnienie 24, które jest naprawdę po prostu (100 - 24). Tak naprawdę wszystko, co robimy, to dodanie 100 po obu stronach równania.

Teraz równanie jest następujące: 100 + 63-24 = x + 100, dlatego usuwamy 100 (lub 10 lub 1000 lub cokolwiek innego).

Ze względu na niewygodną sytuację, polegającą na odejmowaniu jednej liczby od długiego łańcucha zer, używamy systemu „zmniejszonego uzupełnienia podstawnika”, w systemie dziesiętnym, uzupełnienia dziewięciu.

Kiedy pojawia się liczba odejmowana od dużego łańcucha dziewiątek, wystarczy odwrócić liczby.

Przykład: 99999 - 03275 = 96724

Dlatego po uzupełnieniu dziewiątym dodajemy 1. Jak zapewne wiesz z matematyki z dzieciństwa, 9 staje się 10 przez „kradzież” 1. Tak więc w zasadzie to tylko uzupełnienie dziesięciu bierze 1 z różnicy.

W trybie binarnym dopełnienie do dwóch jest równoznaczne z dopełnieniem do dziesięciu, a dopełnienie do dopełnienia do dziewięciu. Podstawowa różnica polega na tym, że zamiast próbować izolować różnicę potęgami dziesięciu (dodając 10, 100 itd. Do równania), próbujemy izolować różnicę potęgami dwóch.

Z tego powodu odwracamy bity. Podobnie jak nasz minuend jest łańcuchem dziewiątek dziesiętnych, tak nasz minuend jest łańcuchem jedności binarnych.

Przykład: 111111 - 101001 = 010110

Ponieważ łańcuchy jedności mają wartość 1 poniżej ładnej potęgi dwóch, „kradną” 1 z różnicy, tak jak dziewiątki robią dziesiętnie.

Kiedy używamy ujemnych liczb binarnych, tak naprawdę mówimy po prostu:

0000 - 0101 = x

1111–0101 = 1010

1111 + 0000 - 0101 = x + 1111

Aby „wyizolować” x, musimy dodać 1, ponieważ 1111 jest jeden od 10000 i usuwamy wiodący 1, ponieważ właśnie dodaliśmy go do pierwotnej różnicy.

1111 + 1 + 0000 - 0101 = x + 1111 + 1

10000 + 0000 - 0101 = x + 10000

Wystarczy usunąć 10000 z obu stron, aby uzyskać x, to podstawowa algebra.

KyBrooks
źródło
3

Wiele dotychczasowych odpowiedzi dobrze wyjaśnia, dlaczego dopełnianie dwóch jest używane do reprezentowania liczby ujemnej, ale nie mów nam, jaka jest liczba dopełniacza dwóch, szczególnie nie dlaczego „1” jest dodawane, a w rzeczywistości często dodawane w niewłaściwy sposób.

Zamieszanie wynika ze słabego zrozumienia definicji liczby uzupełniającej. Uzupełnieniem jest brakująca część, która uzupełniałaby coś.

Uzupełnienie podstawnika liczby n cyfry x w podstawce b jest z definicji b ^ nx. W systemie binarnym 4 jest reprezentowane przez 100, który ma 3 cyfry (n = 3) i podstawę 2 (b = 2). Zatem jego dopełnienie podstawnika wynosi b ^ nx = 2 ^ 3-4 = 8-4 = 4 (lub 100 dwójkowo).

Jednak w binarnym uzyskiwaniu uzupełnienia podstawnika nie jest tak łatwe, jak uzyskanie jego zmniejszonego uzupełnienia podstawnika, które jest zdefiniowane jako (b ^ n-1) -y, tylko o 1 mniej niż w przypadku uzupełnienia podstawnika. Aby uzyskać zmniejszone uzupełnienie podstawnika, wystarczy przerzucić wszystkie cyfry.

100 -> 011 (zmniejszone (własne) uzupełnienie podstawy)

aby uzyskać uzupełnienie radix (dwa), dodajemy po prostu 1, zgodnie z definicją.

011 +1 -> 100 (uzupełnienie dwóch).

Teraz, mając to nowe zrozumienie, spójrzmy na przykład podany przez Vincenta Ramdhanie (patrz powyższa druga odpowiedź)

/ * początek Vincenta

Konwersja 1111 na dziesiętne:

Liczba zaczyna się od 1, więc jest ujemna, więc znajdujemy dopełnienie 1111, czyli 0000. Dodaj 1 do 0000 i otrzymamy 0001. Konwertuj 0001 na dziesiętne, czyli 1. Zastosuj znak = -1. Tada!

koniec Vincenta * /

Należy rozumieć jako

Liczba zaczyna się od 1, więc jest ujemna. Więc wiemy, że jest to uzupełnienie dwóch o pewnej wartości x. Aby znaleźć x reprezentowany przez jego uzupełnienie do dwóch, najpierw musimy znaleźć jego uzupełnienie do 1.

dopełnienie do dwóch x: 1111 dopełnienie do dwóch x: 1111-1 -> 1110; x = 0001, (odwróć wszystkie cyfry)

zastosuj znak - i odpowiedź = -x = -1.

użytkownik779764
źródło
3

Słowo „dopełnienie” pochodzi od kompletności. W świecie dziesiętnym cyfry od 0 do 9 stanowią uzupełnienie (kompletny zestaw) cyfr lub symboli numerycznych do wyrażenia wszystkich liczb dziesiętnych. W świecie binarnym cyfry 0 i 1 stanowią uzupełnienie liczb do wyrażenia wszystkich liczb binarnych. W rzeczywistości symbole 0 i 1 muszą być użyte do przedstawienia wszystkiego (tekst, obrazy itp.), A także dodatniego (0) i ujemnego (1). W naszym świecie puste miejsce po lewej stronie liczby jest uważane za zero:

                  35=035=000000035.

W miejscu przechowywania komputera nie ma pustego miejsca. Wszystkie bity (cyfry binarne) muszą mieć wartość 0 lub 1. Aby efektywnie wykorzystać pamięć, numery mogą być przechowywane jako reprezentacje 8-bitowe, 16-bitowe, 32-bitowe, 64-bitowe, 128-bitowe. Gdy liczba przechowywana jako liczba 8-bitowa jest przenoszona do 16-bitowej lokalizacji, znak i wielkość (wartość bezwzględna) muszą pozostać takie same. Ułatwiają to zarówno reprezentacje uzupełnienia 1, jak i uzupełnienia 2. Jako rzeczownik: zarówno dopełnienie 1, jak i dopełnienie 2 są reprezentacjami binarnymi oznaczonych wielkości, przy czym najbardziej znaczącym bitem (ten po lewej) jest bit znaku. 0 oznacza wartość dodatnią, a 1 wartość ujemną. Uzupełnienie 2s nie oznacza wartości ujemnej. Oznacza podpisaną ilość. Podobnie jak w systemie dziesiętnym wielkość jest reprezentowana jako wielkość dodatnia. Struktura wykorzystuje rozszerzenie znaku, aby zachować ilość przy awansie do rejestru [] z większą liczbą bitów:

       [0101]=[00101]=[00000000000101]=5 (base 10)
       [1011]=[11011]=[11111111111011]=-5(base 10)

Jako czasownik: uzupełnienie 2 oznacza zanegowanie . To nie znaczy zrobić negatywne. Oznacza to, że jeśli negatywne stają się pozytywne; jeśli pozytywne, należy zrobić ujemne. Wielkość jest wartością bezwzględną:

        if a >= 0 then |a| = a
        if a < 0 then |a| = -a = 2scomplement of a

Ta zdolność umożliwia efektywne odejmowanie binarne przy użyciu negacji, a następnie dodawania. a - b = a + (-b)

Oficjalnym sposobem pobrania uzupełnienia 1 jest odjęcie każdej cyfry od 1.

        1'scomp(0101) = 1010.

Jest to to samo, co odwracanie lub odwracanie każdego bitu osobno. Powoduje to ujemne zero, które nie jest bardzo lubiane, więc dodanie jednego do uzupełnienia eliminuje problem. Aby zanegować lub wziąć uzupełnienie 2, najpierw weź uzupełnienie 1, a następnie dodaj 1.

        Example 1                             Example 2
         0101  --original number              1101
         1's comp  1010                       0010
         add 1     0001                       0001
         2's comp  1011  --negated number     0011

W przykładach negacja działa również z rozszerzonymi znakami.

Dodawanie:
1110 Carry 111110 Carry 0110 jest taki sam jak 000110 1111 111111 suma 0101 suma 000101

C Pobieranie:

    1110  Carry                      00000   Carry
     0110          is the same as     00110
    -0111                            +11001
  ----------                        ----------
sum  0101                       sum   11111

Zauważ, że podczas pracy z dopełniaczem 2 puste miejsce po lewej stronie liczby jest wypełnione zerami dla liczb dodatnich, ale jest wypełnione zerami dla liczb ujemnych. Przeniesienie jest zawsze dodawane i musi wynosić 1 lub 0.

Twoje zdrowie

Russ
źródło
3

Uzupełnienie 2 jest zasadniczo sposobem wymyślenia addytywnego odwrotności liczby binarnej. Zadaj sobie następujące pytanie: Biorąc pod uwagę liczbę w postaci binarnej, jaki wzór bitowy po dodaniu do pierwotnej liczby spowodowałby, że wynik byłby zerowy? Jeśli możesz wymyślić ten wzór bitowy, wówczas ten wzór bitowy jest reprezentacją -ve (addytywna odwrotność) oryginalnej liczby; ponieważ z definicji dodanie liczby do jej odwrotności addytywnej zawsze powinno dawać zero. Przykład: weź 101, która jest dziesiętna 5. Teraz zadaniem jest wymyślenie wzoru bitowego, który po dodaniu do danego wzorca bitowego (101) dałby zero. Aby to zrobić, zacznij od najbardziej prawego bitu 101 i dla każdego pojedynczego bitu ponownie zadaj to samo pytanie: Jaki bit powinienem dodać do tego „bitu”, aby wynik był zerowy? kontynuuj to, biorąc pod uwagę zwykłe przeniesienie. Po tym, jak skończymy z trzema prawymi większością miejsc (cyframi, które definiują oryginalny numer bez względu na początkowe zera), ostatnie przeniesienie przechodzi w wzór bitowy odwrotności dodatku. Ponadto, ponieważ moglibyśmy utrzymywać w pierwotnym numerze powiedzmy jeden bajt, wszystkie inne wiodące bity w odwrotności addytywnej powinny również wynosić 1, tak że gdy komputer doda liczbę i jej odwrotność za pomocą „tego” typu pamięci (char) wynikiem tego znaku będą wszystkie zera.

 1 1 1
 ----------
   1 0 1
 1 0 1 1 ---> additive inverse
  ---------
   0 0 0
n-mam
źródło
2

Podobało mi się odpowiedź lavinio, ale przesuwanie bitów dodaje pewnej złożoności. Często istnieje wybór ruchomych bitów przy jednoczesnym poszanowaniu bitu znakowego lub nie respektując bitu znakowego. Jest to wybór między traktowaniem liczb jako podpisanych (od -8 do 7 dla wartości liczbowych, od -128 do 127 dla bajtów) lub pełnym zakresem liczb bez znaku (od 0 do 15 dla wartości, 0 do 255 dla bajtów).

Nosredna
źródło
2

Jest to sprytny sposób kodowania ujemnych liczb całkowitych w taki sposób, że około połowa kombinacji bitów typu danych jest zarezerwowana na ujemne liczby całkowite, a dodanie większości ujemnych liczb całkowitych z odpowiadającymi im dodatnimi liczbami całkowitymi powoduje przepełnienie przenoszenia co pozostawia wynik jako zero binarne.

Zatem w uzupełnieniu 2, jeśli jeden ma wartość 0x0001, wówczas -1 oznacza 0x1111, ponieważ spowoduje to łączną sumę 0x0000 (z przepełnieniem 1).

Edwin Buck
źródło
1

Miałem ten sam problem kilka tygodni temu. Skończyło się na czytaniu o tym w Internecie z różnych źródeł, próbowaniu zebrania kawałków i pisaniu o tym samemu, aby upewnić się, że dobrze to zrozumiałem. Używamy uzupełnienia do dwóch z głównie dwóch powodów:

  1. Aby uniknąć wielokrotnych reprezentacji 0
  2. Aby uniknąć śledzenia bitu przenoszenia (jak w uzupełnieniu) w przypadku przepełnienia.
  3. Przeprowadzanie prostych operacji, takich jak dodawanie i odejmowanie, staje się łatwe.

Jeśli chcesz uzyskać bardziej szczegółowe wyjaśnienie omawianej sprawy, wypróbuj artykuł napisany przeze mnie tutaj . Mam nadzieję, że to pomoże!

KN Bhargav
źródło
1

Uzupełnienie dwóch jest jednym ze sposobów wyrażania liczby ujemnej, a większość kontrolerów i procesorów przechowuje liczbę ujemną w postaci uzupełnienia 2

Denis Roosevelt
źródło
1
Nie dodaje to niczego do informacji dostarczonych przez inne odpowiedzi.
Adrian Mole
0

ODNIESIENIE: https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html

Odwracam wszystkie bity i dodaję 1. Programowo:

  // in C++11
  int _powers[] = {
      1,
      2,
      4,
      8,
      16,
      32,
      64,
      128
  };

  int value=3;
  int n_bits=4;
  int twos_complement = (value ^ ( _powers[n_bits]-1)) + 1;
Charles Thomas
źródło
Nawet asembler byłby zbyt wysoki. Musisz zobaczyć schemat poziomu logiki dodawania. Z cyklami T. Jesteś poprawny algorytmicznie.
mckenzm,
0

Uzupełnieniem 2 liczby podanej jest nie. otrzymane przez dodanie 1 z dopełnieniem 1 do nie. załóżmy, że mamy numer binarny: 10111001101 Uzupełnienie 1 to: 01000110010 Uzupełnienie 2 to: 01000110011

rev użytkownik10862846
źródło
0

Uzupełnienie bitowe liczby polega na przerzuceniu wszystkich bitów. Aby uzupełnić dwa, odwracamy wszystkie bity i dodajemy jeden.

Używając reprezentacji dopełniacza 2 dla liczb całkowitych ze znakiem, stosujemy operację dopełniania 2, aby przekonwertować liczbę dodatnią na jej ekwiwalent ujemny i odwrotnie. Tak więc używając na przykład skórek, 0001(1) staje się 1111(-1), a ponowne zastosowanie op powraca do 0001.

Zachowanie operacji na poziomie zerowym jest korzystne, ponieważ daje jedną reprezentację dla zera bez specjalnej obsługi zer dodatnich i ujemnych. 0000uzupełnia, do 1111których dodaje się 1. przepełnia się 0000, dając nam jedno zero, a nie dodatnie i ujemne.

Kluczową zaletą tej reprezentacji jest to, że standardowe obwody dodatkowe dla niepodpisanych liczb całkowitych dają prawidłowe wyniki po zastosowaniu do nich. Na przykład dodanie 1 i -1 do skubków: 0001 + 1111bity wypływają z rejestru, pozostawiając za sobą 0000.

Dla łagodnego wprowadzenia cudowny Computerphile stworzył wideo na ten temat .

ahcox
źródło
0

Mówiąc najprościej, 2's Complementto sposób na zapisanie liczby ujemnej w pamięci komputera. Natomiast liczby dodatnie są przechowywane jako normalna liczba binarna.

Rozważmy ten przykład,

Komputer używa Binary Number Systemdo reprezentowania dowolnej liczby.

x = 5;

Jest to reprezentowane jako 0101.

x = -5;

Kiedy komputer się -podpisuje, oblicza uzupełnienie 2 i zapisuje je. i.e5 = 0101, a uzupełnienie 2 to 1011.

Ważne zasady, których używa komputer do przetwarzania numerów,

  1. Jeśli pierwszy bit jest, 1to musi być negativeliczbą.
  2. Jeśli wszystkie bity z wyjątkiem pierwszego bitu są 0liczbą dodatnią, ponieważ nie ma -0systemu liczbowego ( 1000 is not -0zamiast tego jest dodatnia 8)
  3. Jeśli wszystkie bity są, 0to tak jest 0.
  4. W przeciwnym razie jest to positive number.
Raghu
źródło
-6

Najprostsza odpowiedź:

1111 + 1 = (1) 0000. Więc 1111 musi wynosić -1. Wtedy -1 + 1 = 0.

Idealnie jest dla mnie to wszystko zrozumieć.

Dmitry
źródło
To nie daje odpowiedzi na pytanie. Aby skrytykować lub poprosić autora o wyjaśnienia, zostaw komentarz pod postem.
Codor
To jest odpowiedź. Najprostszy. Dla mnie najlepszy.
Dmitry