Istnieją trzy różne sposoby przedstawiania liczby całkowitej ze znakiem (artykuł). a: bit ze znakiem, b: uzupełnienie 1 i c: uzupełnienie 2. Spróbujmy zrozumieć, w jaki sposób wyprowadzono te metody i dlaczego uzupełnienie do 2 jest preferowane w stosunku do innych.

Jak wiemy, dane są przechowywane w bitach. Jak możemy przechowywać liczbę całkowitą ze znakiem w pamięci? Aby rozwiązać ten problem, najpierw opracujemy rozwiązanie naiwne, a następnie będziemy je powtarzać, aż znajdziemy najlepsze rozwiązanie naszego problemu.

a) Bit ze znakiem

Próbując zapisać liczbę całkowitą ze znakiem, oczywiste wydaje się zarezerwowanie lewego bitu najbardziej na znak i wykorzystanie pozostałych bitów do faktycznego przechowywania wartości. Na przykład: w systemie 4-bitowym pierwszy bit od lewej strony będzie zarezerwowany na znak (0 oznacza wartość dodatnią, a 1 oznacza wartość ujemną), a pozostałe 3 bity zostaną wykorzystane do przechowywania wartości. Podobnie w systemie 8-bitowym pierwszy bit od lewej będzie używany jako znak, a pozostałe 7 jako wartości.

Stosując to podejście, jesteśmy w stanie z powodzeniem przedstawić liczbę całkowitą ze znakiem. Kiedy jednak przeanalizujemy to bliżej, możemy zauważyć następujące wady:

1) Dwie reprezentacje zera:

W systemie 4-bitowym powinniśmy być w stanie zapisać 16 (24) wartości, ale +1 do +7 i -1 do -7 to tylko 14 wartości. Gdzie znajdują się pozostałe dwie wartości? Kiedy uważnie przyjrzymy się tabeli, odkryjemy, że te dwie wartości zbiegają się do 0. Mamy zatem dwie reprezentacje zera, co oznacza jedną reprezentację dla +0 i drugą dla -0.

Ale czy dwie reprezentacje 0 są dużym problemem? Więc co? Zamiast 16 unikalnych wartości jesteśmy w stanie przechowywać tylko 15 wartości. Możemy sobie pozwolić na zmniejszenie zakresu o 1, prawda? Dla twórcy oprogramowania może to nie dotyczyć, ale dla projektanta obwodów bardzo frustrujące może być sprawdzenie najpierw, czy wartość wynosi +0, a następnie sprawdzenie, czy wynosi -0.

2) Podpisane rozszerzenie nie działa dla liczb ujemnych:

Rozmiar danych szybko rośnie. Kiedyś będziemy musieli rozszerzyć system bitowy, abyśmy mogli zwiększyć zakres danych, które można przechowywać. W 2014 roku film Gangnam Style przekroczył limit wyświetleń w YouTube, co zmusiło YouTube do zwiększenia liczby wyświetleń z 32-bitowej do 64-bitowej liczby całkowitej ze znakiem. Podobnie 32-bitowy zegar Uniksa przepełni się 19 stycznia 2038 r., ponieważ rejestruje czas w sekundach w 32-bitowej liczbie całkowitej ze znakiem.

Zatem równie ważne jest, aby nasz system reprezentacji dawał się łatwo rozszerzać, co nie jest możliwe w przypadku tego systemu reprezentacji.

3) Dodawanie binarne nie działa:

Spróbujmy dodać dwie liczby binarne:

Dlaczego prosty dodatek binarny tutaj nie działa? Powodem jest to, że bit znaku (najbardziej z lewej strony) nie jest zwykłym bitem i nie jest częścią rzeczywistej liczby. Wyobraźmy sobie sytuację, w której trzeba zaprojektować obwód sprzętowy tak, aby ignorował bit znaku w celu wykonania dodawania, a następnie dołączyć bit znaku.

Był to więc naiwny sposób przedstawiania liczby całkowitej ze znakiem. Główny problem związany z tym podejściem polega na tym, że liczby ujemne odwzorowaliśmy w dół. Jeśli zmienimy nasz system mapowania na niższy, niektóre z powyższych problemów zostaną rozwiązane.

b) 1’s Co wdrożyć

Jeśli przemapujemy nasze liczby ujemne z góry na dół, otrzymamy następującą tabelę binarną:

Jak uzyskać binarną reprezentację liczby całkowitej w metodzie uzupełnienia do 1?

• Liczby dodatnie są reprezentowane podobnie jak metoda liczb całkowitych ze znakiem
• Liczby ujemne są reprezentowane przez odwrócenie każdego bitu odpowiedniej liczby dodatniej (odwrócenie można łatwo wykonać za pomocą bramki NOT podczas projektowania sprzętu)

Przeanalizujmy to dokładnie, aby sprawdzić, czy osiągnęliśmy pewną poprawę.

1) Dwie reprezentacje zera:

W tym podejściu również mamy dwie reprezentacje zera.

2) Podpisane rozszerzenie nie działa dla liczb ujemnych:

Podpisane rozszerzenie działa doskonale w przypadku liczb ujemnych.

3) Dodawanie binarne działa ze zmodyfikowanymi regułami:

Odpowiedź nie zawsze jest prawidłowa, ale jest bardzo bliska prawidłowej. Możemy sprawić, że to zadziała, jeśli będziemy przestrzegać tej zasady jeśli wygenerowałeś przeniesienie do przodu po lewej stronie, nie wyrzucaj go, zamiast tego przynieś je z powrotem i dodaj po prawej stronie.

Zdecydowanie metoda uzupełnienia jedynki jest lepsza niż bit ze znakiem. Nasze główne obawy zostały rozwiązane, ale nadal występują problemy (posiadanie dwóch reprezentacji zera), a nasz hack w dodawaniu binarnym daje wskazówki, jak ulepszyć metodę uzupełniania jedynki. Przeformułujmy te zdania, żeby było łatwiej.

• Mamy dodatkową reprezentację zera, która jest niepotrzebna
• Podczas dodawania dwóch liczb binarnych, jeśli mamy przeniesienie w skrajnym lewym bicie, musimy dodać +1 do wyniku, co oznacza, że ​​właściwą odpowiedź można znaleźć, przechodząc do następnego wiersza w tabeli binarnej.

Obydwa wskazują nam, że główną przyczyną problemu jest dodatkowa reprezentacja zera. Zatem usuńmy to dodatkowe zero i przesuńmy wszystkie wartości ujemne do następnego wiersza (-7 przesunie się z I -> J, -6 przesunie się z J -> K i tak dalej…)

c) Uzupełnienie 2

Kiedy usuniemy -0 z tabeli uzupełnień do 1 i przesuniemy wszystkie wartości ujemne o jeden wiersz poniżej, otrzymamy następującą tabelę, którą nazywamy uzupełnieniem do 2:

Jak uzyskać binarną reprezentację liczby całkowitej w metodzie uzupełnienia do 2?

• Liczby dodatnie są reprezentowane podobnie jak metoda liczb całkowitych ze znakiem
• Liczby ujemne są reprezentowane przez odwrócenie każdego bitu odpowiedniej liczby dodatniej, a następnie dodanie do niej 1 bitu

1) Jedna reprezentacja zera:

Teraz mamy tylko jedną reprezentację zera i pozwala nam to przechowywać łącznie 16 unikalnych wartości (+0 do +7 i -1 do -8).

2) Podpisane rozszerzenie działa dla liczb ujemnych:

Podpisane rozszerzenie działa doskonale w przypadku liczb ujemnych.

3) Dodawanie binarne:

4) Pierwszy bit jest bitem ze znakiem:

Dopełnienie do 2 ma tę ciekawą właściwość, że pierwszy bit jest bitem znaku, ponieważ wszystkie dodatnie zaczynają się od 0, a wszystkie ujemne od 1.

5) Kontrola przepełnienia pamięci:

Dodając, upewniliśmy się, że nasza odpowiedź mieści się w zakresie, ale podczas projektowania sprzętu należy wykryć przepełnienie pamięci. Sprawdzanie wielkości w celu wykrycia przepełnienia będzie bardzo złym pomysłem dla projektantów sprzętu. Metoda uzupełnienia 2 zapewnia bardzo prosty sposób na wykrycie przepełnienia pamięci. I f przeniesienie do bitu ze znakiem nie jest równoznaczne z przeniesieniem bitu ze znakiem, to mamy do czynienia z przepełnieniem pamięci tj. jeśli przeniesienie do bitu ze znakiem wynosi 0, ale wykonanie wynosi 1 lub jeśli przeniesienie wynosi 1, ale wykonanie wynosi 0, to jest to przypadek przepełnienia pamięci.