Dlaczego wdrażane są numery bez znaku?

Nie mogę zrozumieć, dlaczego systemy mikroprocesorowe implementują niepodpisane liczby. Sądzę, że koszt jest tylko dwukrotnością liczby gałęzi warunkowych, ponieważ większa niż, mniejsza niż .etc, potrzebuje innego algorytmu niż podpisany, czy nadal istnieją jakieś algorytmy, dla których liczby bez znaku są znaczącą zaletą?

moje pytanie częściowo dotyczy tego, dlaczego muszą one znajdować się w zestawie instrukcji, a nie być obsługiwane przez kompilator?

Numery niepodpisane to jedna interpretacja sekwencji bitów. Jest to również najprostsza i najczęściej stosowana interpretacja wewnętrzna procesora, ponieważ adresy i kody operacji są po prostu bitami. Adresowanie pamięci / stosu i arytmetyka są fundamentami mikroprocesora, no cóż, przetwarzania. Idąc w górę piramidy abstrakcji, kolejną częstą interpretacją bitów jest znak (ASCII, Unicode, EBCDIC). Są też inne interpretacje, takie jak zmiennoprzecinkowy IEEE, RGBA dla grafiki i tak dalej. Żadna z tych liczb nie jest prostym znakiem (IEEE FP nie jest prosta, a użycie arytmetyki przy użyciu tych liczb jest bardzo skomplikowane).

Ponadto, z nieoznaczoną arytmetyką, implementacja pozostałych jest dość prosta (jeśli nie najskuteczniejsza). Odwrotna sytuacja nie jest prawdą.

Większość kosztów sprzętu dla operacji porównania to odjęcie. Wynik odejmowania zastosowany przez porównanie to zasadniczo trzy bity stanu:

• czy wszystkie bity są równe zero (tj. warunek równości),
• bit znaku wyniku
• bit przeniesienia odejmowania (tj. 33-ty bit najwyższego rzędu na komputerze 32-bitowym)

Przy odpowiedniej kombinacji testowania tych trzech bitów po operacji odejmowania możemy określić wszystkie podpisane operacje relacyjne, a także wszystkie niepodpisane operacje relacyjne (te bity są również sposobem wykrywania przepełnienia, podpisania vs. niepodpisania). Ten sam podstawowy sprzęt ALU może być współdzielony w celu wdrożenia wszystkich tych porównań (nie wspominając o instrukcji odejmowania), aż do ostatecznego sprawdzenia tych trzech bitów stanu, które różnią się zgodnie z pożądanym porównaniem relacyjnym. Tak więc nie jest to dużo dodatkowego sprzętu.

Jedynym realnym kosztem jest potrzeba kodowania dodatkowych trybów porównania w architekturze zestawu instrukcji, co może nieznacznie zmniejszyć gęstość instrukcji. Mimo to jest całkiem normalne, że sprzęt ma wiele instrukcji, które nie są używane w żadnym języku.

Ponieważ, jeśli chcesz policzyć coś, co jest zawsze >= 0 , niepotrzebnie zmniejszysz swoje miejsce do liczenia o połowę, używając podpisanych liczb całkowitych.

Rozważ automatyczną inkrementację INT PK, którą możesz umieszczać w tabelach bazy danych. Jeśli użyjesz tam podpisanej liczby całkowitej, twoja tabela przechowuje POŁOWĘ tylu rekordów, ile może, dla tego samego rozmiaru pola BEZ korzyści.

Lub oktety koloru RGBa. Nie chcemy niezręcznie zaczynać liczenia tej naturalnie dodatniej liczby jako liczby ujemnej. Podpisana liczba albo przerwie model mentalny, albo zmniejszy o połowę naszą przestrzeń. Liczba całkowita bez znaku nie tylko pasuje do koncepcji, ale zapewnia dwukrotnie większą rozdzielczość.

Z punktu widzenia sprzętu liczby całkowite bez znaku są proste. Są prawdopodobnie najłatwiejszą strukturą bitów do wykonania matematyki. I bez wątpienia moglibyśmy uprościć sprzęt, symulując typy całkowite (lub nawet zmiennoprzecinkowe!) W kompilatorze. Dlaczego więc w sprzęcie są zaimplementowane zarówno liczby całkowite niepodpisane, jak i podpisane ?

Cóż ... wydajność!

Bardziej wydajne jest implementowanie podpisanych liczb całkowitych w sprzęcie niż w oprogramowaniu. Sprzęt może zostać poinstruowany, aby przeprowadzał matematykę na dowolnym typie liczby całkowitej w jednej instrukcji. I to bardzo dobrze , ponieważ sprzęt rozbija bity mniej więcej równolegle. Jeśli spróbujesz symulować to w oprogramowaniu, liczba całkowita, którą wybierzesz do „symulacji”, niewątpliwie będzie wymagała wielu instrukcji i będzie zauważalnie wolniejsza.

Twoje pytanie składa się z dwóch części:

1. Jaki jest cel liczb całkowitych bez znaku?

2. Czy wartości całkowite bez znaku są warte kłopotu?

1. Jaki jest cel liczb całkowitych bez znaku?

Liczby niepodpisane po prostu reprezentują klasę wielkości, dla których wartości ujemne są bez znaczenia. Jasne, możesz powiedzieć, że odpowiedź na pytanie „ile mam jabłek?” może być liczbą ujemną, jeśli jesteś komuś winien jabłka, ale co z pytaniem „ile mam pamięci?” - nie możesz mieć ujemnej ilości pamięci. Zatem liczby całkowite bez znaku są bardzo odpowiednie do reprezentowania takich wielkości i mają tę zaletę, że mogą reprezentować dwukrotność zakresu wartości dodatnich niż liczby całkowite ze znakiem. Na przykład maksymalna wartość, którą można reprezentować za pomocą 16-bitowej liczby całkowitej ze znakiem, to 32767, natomiast z 16-bitową liczbą całkowitą bez znaku to 65535.

2. Czy wartości całkowite bez znaku są warte kłopotu?

Niespisane liczby całkowite nie stanowią żadnego problemu, więc tak, są tego warte. Widzisz, nie wymagają one dodatkowego zestawu „algorytmów”; zespół obwodów wymaganych do ich zaimplementowania jest podzbiorem zespołu obwodów wymaganych do implementacji podpisanych liczb całkowitych.

Procesor nie ma jednego mnożnika dla podpisanych liczb całkowitych i innego mnożnika dla niepodpisanych; ma tylko jeden mnożnik, który działa w nieco inny sposób, w zależności od charakteru operacji. Obsługiwanie podpisanego mnożenia wymaga nieco więcej obwodów niż niepodpisanych, ale ponieważ i tak musi być obsługiwane, niepodpisane mnożenie przychodzi praktycznie za darmo, jest zawarte w pakiecie.

Jeśli chodzi o dodawanie i odejmowanie, obwód nie ma żadnej różnicy. Jeśli przeczytasz tak zwaną reprezentację liczb całkowitych z dopełnianiem dwóch, przekonasz się, że jest ona tak sprytnie zaprojektowana, że ​​operacje te można wykonywać dokładnie w ten sam sposób, niezależnie od charakteru liczb całkowitych.

Porównanie działa również w ten sam sposób, ponieważ nie jest niczym innym, jak odjęciem i odrzuceniem wyniku, jedyną różnicą są instrukcje warunkowe rozgałęzienia (skoku), które działają, patrząc na różne flagi procesora ustawione przez parametr poprzedzająca (porównawcza) instrukcja. W tej odpowiedzi: /programming//a/9617990/773113 można znaleźć wyjaśnienie ich działania w architekturze Intel x86. Tak się składa, że ​​oznaczenie instrukcji skoku warunkowego jako podpisanej lub niepodpisanej zależy od tego, które flagi bada.

Mikroprocesory są z natury niepodpisane. Podpisane liczby to coś, co zostało zaimplementowane, a nie na odwrót.

Komputery mogą i działają dobrze bez podpisanych liczb, ale to my, ludzie, którzy potrzebujemy liczb ujemnych, wynaleziono sygnaturę.

Ponieważ mają jeszcze jeden bit, który jest łatwo dostępny do przechowywania i nie musisz się martwić o liczby ujemne. Nie ma w tym nic więcej.

Teraz, jeśli potrzebujesz przykładu, gdzie potrzebujesz tego dodatkowego bitu, jest wiele do znalezienia, jeśli spojrzysz.

Mój ulubiony przykład pochodzi z bitboardów w silnikach szachowych. Na szachownicy znajdują się 64 kwadraty, co unsigned longzapewnia idealne miejsce do przechowywania różnych algorytmów związanych z generowaniem ruchów. Biorąc pod uwagę fakt, że potrzebujesz operacji binarnych (a także operacji zmiany !!), łatwo jest zrozumieć, dlaczego łatwiej jest nie martwić się o to, co się stanie, jeśli MSB zostanie ustawiony. Można to zrobić przy użyciu długiego podpisu, ale o wiele łatwiej jest używać niepodpisanego.

Mając czysto matematyczne doświadczenie, jest to nieco bardziej matematyczne podejście dla wszystkich zainteresowanych.

Jeśli zaczniemy od 8-bitowej liczby całkowitej ze znakiem i bez znaku, mamy w zasadzie liczbę całkowitą modulo 256, jeśli chodzi o dodawanie i mnożenie, pod warunkiem, że dopełnienie 2 jest używane do reprezentowania liczb całkowitych ujemnych (i tak robi to każdy nowoczesny procesor) .

Rzeczy różnią się w dwóch miejscach: jedno to operacje porównania. W pewnym sensie liczby całkowite modulo 256 są najlepiej uważane za koło liczb (podobnie jak liczby całkowite modulo 12 na staromodnej analogowej powierzchni zegarowej). Aby porównania numeryczne (czyli x <y) były znaczące, musieliśmy zdecydować, które liczby są mniejsze niż inne. Z punktu widzenia matematyka chcemy jakoś osadzić liczby całkowite modulo 256 w zbiorze wszystkich liczb całkowitych. Odwzorowanie 8-bitowej liczby całkowitej, której binarna reprezentacja składa się z samych zer, na liczbę całkowitą 0, jest oczywistą czynnością. Następnie możemy przystąpić do mapowania innych, tak aby „0 + 1” (wynik zerowania rejestru, powiedzmy ax, i zwiększenie go o jeden, poprzez „inc ax”) trafił do liczby całkowitej 1 i tak dalej. Możemy zrobić to samo z -1, na przykład mapując „0-1” na liczbę całkowitą -1 i „0-1-1” do liczby całkowitej -2. Musimy upewnić się, że to osadzanie jest funkcją, więc nie można zmapować pojedynczej liczby całkowitej 8-bitowej na dwie liczby całkowite. Oznacza to, że jeśli zamapujemy wszystkie liczby na zbiór liczb całkowitych, będzie tam 0, wraz z niektórymi liczbami całkowitymi mniejszymi niż 0 i niektórymi większymi niż 0. Istnieją zasadniczo 255 sposobów, aby to zrobić za pomocą 8-bitowej liczby całkowitej (zgodnie z do jakiego minimum chcesz, od 0 do -255). Następnie możesz zdefiniować „x <y” w kategoriach „0 <y - x”.

Istnieją dwa typowe przypadki użycia, dla których uzasadnione jest wsparcie sprzętowe: jeden przy wszystkich niezerowych liczbach całkowitych większych od 0, a drugi przy około 50/50 podzielonych wokół 0. Wszystkie inne możliwości można łatwo emulować poprzez translację liczb za pomocą dodatkowego „add” i sub 'przed operacjami, a potrzeba tego jest tak rzadka, że ​​nie mogę wymyślić wyraźnego przykładu we współczesnym oprogramowaniu (ponieważ możesz po prostu pracować z większą mantysą, powiedzmy 16 bitów).

Innym problemem jest odwzorowanie 8-bitowej liczby całkowitej na przestrzeń 16-bitowych liczb całkowitych. Czy -1 idzie do -1? Tego właśnie chcesz, jeśli 0xFF ma reprezentować -1. W takim przypadku rozsądne jest wydłużanie znaków, aby 0xFF poszedł do 0xFFFF. Z drugiej strony, jeśli 0xFF miało reprezentować 255, to chcesz, aby było odwzorowane na 255, a więc na 0x00FF, a nie 0xFFFF.

Jest to również różnica między operacjami „przesunięcia” i „przesunięcia arytmetycznego”.

Ostatecznie jednak sprowadza się to do tego, że int w oprogramowaniu nie są liczbami całkowitymi, ale reprezentacjami w postaci binarnej i tylko niektóre z nich mogą być reprezentowane. Projektując sprzęt, należy dokonać wyboru, co zrobić natywnie w sprzęcie. Ponieważ w przypadku uzupełnienia 2 operacje dodawania i mnożenia są identyczne, sensowne jest przedstawianie w ten sposób ujemnych liczb całkowitych. Zatem jest to tylko kwestia operacji, które zależą od liczb całkowitych, które mają reprezentować twoje reprezentacje binarne.

Pozwala zbadać koszt implementacji dodawania liczb całkowitych bez znaku do projektu procesora z istniejącymi liczbami całkowitymi ze znakiem.

Typowy procesor potrzebuje następujących instrukcji arytmetycznych:

• DODAJ (która dodaje dwie wartości i ustawia flagę, jeśli operacja się przepełni)
• SUB (który odejmuje jedną wartość od drugiej i ustawia różne flagi - omówimy je poniżej)
• CMP (który jest zasadniczo „SUB i odrzuć wynik, zachowaj tylko flagi”)
• LSH (lewy Shift, ustaw flagę przy przepełnieniu)
• RSH (przesunięcie w prawo, ustaw flagę, jeśli 1 zostanie przesunięty)
• Warianty wszystkich powyższych instrukcji, które obsługują przenoszenie / pożyczanie z flag, umożliwiając wygodne łączenie instrukcji razem, aby operować na większych typach niż rejestry procesora
• MUL (mnożenie, ustawianie flag itp. - nie są powszechnie dostępne)
• DIV (dzielenie, ustawianie flag itp. - brakuje tego w wielu architekturach procesora)
• Przejdź z mniejszego typu liczb całkowitych (np. 16-bitowych) na większy (np. 32-bitowych). W przypadku liczb całkowitych ze znakiem jest to zwykle nazywane MOVSX (ruch z rozszerzeniem znaku).

Potrzebuje również logicznych instrukcji:

• Oddział na zero
• Oddział na większy
• Oddział na mniej
• Rozgałęzienie przy przepełnieniu
• Negowane wersje wszystkich powyższych

Aby wykonać powyższe rozgałęzienia na podpisanych porównaniach liczb całkowitych, najłatwiejszym sposobem jest ustawienie instrukcji SUB następujących flag:

• Zero. Ustaw, jeśli odejmowanie skutkuje wartością zero.
• Przelewowy. Ustaw, jeśli odejmowanie pożyczyło wartość od najbardziej znaczącego bitu.
• Znak. Ustaw bit znaku wyniku.

Następnie gałęzie arytmetyczne są realizowane w następujący sposób:

• Rozgałęzienie na zero: jeśli ustawiona jest flaga zero
• Rozgałęź mniej: jeśli flaga znaku różni się od flagi przepełnienia
• Rozgałęzienie na większe: jeśli flaga znaku jest równa flagi przepełnienia, a flaga zero jest czysta.

Ich negacje powinny wynikać oczywiście ze sposobu ich realizacji.

Więc twój istniejący projekt już implementuje je wszystkie dla podpisanych liczb całkowitych. Teraz zastanówmy się, co musimy zrobić, aby dodać liczby całkowite bez znaku:

• ADD - implementacja ADD jest identyczna.
• SUB - musimy dodać dodatkową flagę: flaga przenoszenia jest ustawiana, gdy wartość jest zapożyczona spoza najbardziej znaczącego bitu rejestru.
• CMP - nie zmienia się
• LSH - nie zmienia się
• RSH - odpowiednie przesunięcie dla podpisanych wartości zachowuje wartość najbardziej znaczącego bitu. W przypadku wartości bez znaku należy zamiast tego ustawić wartość zero.
• MUL - jeśli wielkość wyjściowa jest taka sama jak wejścia, nie są wymagane żadne specjalne postępowanie (x86 nie ma specjalnego traktowania, ale tylko dlatego, że ma wyjście do pary rejestrów, ale uwaga, że obiekt ten jest rzeczywiście dość rzadko stosowane, więc byłoby bardziej oczywisty kandydat do opuszczenia procesora niż typy niepodpisane)
• DIV - bez zmian
• Przejście z mniejszego typu na większy - należy dodać MOVZX, przejść z zerowym rozszerzeniem. Zauważ, że MOVZX jest niezwykle prosty w implementacji.
• Rozgałęzienie na zero - bez zmian
• Rozgałęzienie na mniej - skacze po ustawieniu flagi przenoszenia.
• Rozgałęzienie na większym - skacze, jeśli flaga nośna i zero zarówno czyste.

Należy pamiętać, że w każdym przypadku modyfikacje są bardzo proste i można je wdrożyć, włączając lub wyłączając niewielką część obwodu, lub dodając nowy rejestr flag, który może być kontrolowany przez wartość, którą należy obliczyć jako część w każdym razie wdrożenie instrukcji.

Dlatego koszt dodawania niepodpisanych instrukcji jest bardzo mały . Jeśli chodzi o to, dlaczego należy to zrobić , należy pamiętać, że adresy pamięci (i przesunięcia w tablicach) są z natury wartościami bez znaku. Ponieważ programy spędzają dużo czasu na manipulowaniu adresami pamięci, posiadanie typu, który obsługuje je poprawnie, ułatwia programom pisanie.

Numery niepodpisane istnieją głównie w celu radzenia sobie z sytuacjami, w których trzeba owinąć pierścień algebraiczny (w przypadku 16-bitowego typu niepodpisanego byłby to pierścień liczb całkowitych zgodny mod 65536). Weź wartość, dodaj dowolną kwotę mniejszą niż moduł, a różnica między dwiema wartościami będzie kwotą, która została dodana. Jako przykład w świecie rzeczywistym, jeśli miernik użytkowy odczytuje 9995 na początku miesiąca, a jeden zużywa 23 jednostki, miernik odczyta 0018 na koniec miesiąca. Kiedy używasz pierścienia algebraicznego, nie musisz robić nic specjalnego, aby poradzić sobie z przepełnieniem. Odejmowanie 9995 od 0018 da 0023, dokładnie liczbę użytych jednostek.

Na PDP-11, maszynie, dla której C po raz pierwszy zaimplementowano, nie było żadnych niepodpisanych typów liczb całkowitych, ale typy ze znakiem mogły być używane do arytmetyki modułowej, która zawierała między 32767 a -32768 zamiast między 65535 a 0. Instrukcje liczb całkowitych na niektórych innych platformy nie zawijały jednak wszystkiego; zamiast wymagać, aby implementacje musiały emulować liczby całkowite z dopełnianiem dwóch używanych w PDP-11, język zamiast tego dodał typy niepodpisane, które w większości musiały zachowywać się jak pierścienie algebraiczne, i pozwalał na podpisywanie typów całkowitych zachowywać się w inny sposób w przypadku przepełnienia.

Na początku C istniało wiele wielkości, które mogły przekroczyć 32767 (wspólny INT_MAX), ale nie 65535 (wspólny UINT_MAX). W ten sposób powszechne stało się stosowanie typów niepodpisanych do przechowywania takich ilości (np. Size_t). Niestety w języku nie ma nic, co odróżniałoby typy, które powinny zachowywać się jak liczby z dodatkowym dodatnim zakresem, od typów, które powinny zachowywać się jak pierścienie algebraiczne. Zamiast tego język sprawia, że ​​typy mniejsze niż „int” zachowują się jak liczby, podczas gdy typy pełnowymiarowe zachowują się jak pierścienie algebraiczne. W związku z tym wywołanie funkcji takiej jak:

uint32_t mul(uint16_t a, uint16_t b) { return a*b; }

z (65535, 65535) będzie miał jedno zdefiniowane zachowanie w systemach, w których intjest 16 bitów (tzn. zwraca 1), inne zachowanie w przypadku int33 bitów lub większych (zwracają 0xFFFE0001) oraz Niezdefiniowane zachowanie w systemach, w których „int” jest gdziekolwiek in pomiędzy [zauważ, że gcc zwykle daje arytmetycznie poprawne wyniki z wynikami między INT_MAX + 1u a UINT_MAX, ale czasami generuje kod dla powyższej funkcji, która zawodzi przy takich wartościach!]. Niezbyt pomocny.

Jednak brak typów, które zachowują się spójnie jak liczby lub konsekwentnie jak pierścień algebraiczny, nie zmienia faktu, że typy pierścieni algebraicznych są prawie niezbędne dla niektórych rodzajów programowania.