W jaki sposób komputer określa, czy liczba jest mniejsza czy większa od innej?

To może brzmieć jak głupie pytanie, ale jestem naprawdę ciekawy, skąd komputer wie, że ? Ponadto, skąd komputer wie, że kolejność liczb całkowitych wynosi a alfabet to A, B, C, D, ...? Czy jest to gdzieś zapisane w sprzęcie, czy też system operacyjny zapewnia tego rodzaju informacje?$1<2$$1,2,3,4,5,\ldots$

Najpierw liczby całkowite są konwertowane na liczby binarne. Na przykład liczba całkowita 2 jest konwertowana na 0010.

Procesor korzysta z komparatora cyfrowego :

Cyfrowy komparator lub wielkość komparator jest elektroniczne urządzenie, które trwa dwa numery jako wsad w postaci binarnej i określa, czy jedna liczba jest większa lub mniejsza lub równa drugiej liczbie.

Komparatory są stosowane w jednostkach centralnych (CPU) i mikrokontrolerach.

Źródło: https://en.wikipedia.org/wiki/Digital_comparator

W sprzęcie komparatora stosowane są niektóre bramki (AND, OR, NAND, NOR, XOR itp.). Te bramki pobierają dane binarne i dają wynik w postaci binarnej. Dane wyjściowe można zobaczyć z tabeli prawdy.

Inputs           Outputs
A   B     A>B    A=B    A<B
0   0     0       1      0
0   1     0       0      1
1   0     1       0      0
1   1     0       1      0

Oto 0i 1są napięcia elektryczne dla bramy.
1- Reprezentuje pewne napięcie progowe, które wskazuje pewne napięcie dodatnie.
0- Reprezentuje napięcie poniżej progu.

Załóżmy na przykład, że komparator działa na 5 woltów (należy to wyjaśnić), a następnie:
Napięcie powyżej 3 woltów można uznać za binary-1.
Napięcie poniżej 3 woltów należy traktować jakobinary-0

Jeśli bramka otrzymuje jedno wejście jako 3,5 wolta, a drugie wejście jako 2 wolty, wówczas uważa, że ​​przyjmuje jedno wejście jako binarne 1, a drugie wejście jako binarne 0.

Te sekwencje zer i jedynek są dostarczane bardzo szybko przez obwód przełączający.

Działanie dwubitowego komparatora cyfrowego można wyrazić jako tabelę prawdy:

 Inputs                            Outputs
   A1   A0  B1  B0  A>B    A=B   A<B        
    0   0   0   0    0      1     0
    0   0   0   1    1      0     0
    0   0   1   0    1      0     0
    0   0   1   1    1      0     0
    0   1   0   0    0      0     1
    0   1   0   1    0      1     0
    0   1   1   0    1      0     0
    0   1   1   1    1      0     0
    1   0   0   0    0      0     1
    1   0   0   1    0      0     1
    1   0   1   0    0      1     0
    1   0   1   1    1      0     0
    1   1   0   0    0      0     1
    1   1   0   1    0      0     1
    1   1   1   0    0      0     1
    1   1   1   1    0      1     0

Cytat z Wikipedii :

Przykłady: Rozważ dwie 4-bitowe liczby binarne A i B, tak że


tutaj każdy indeks dolny reprezentuje jedną z cyfr liczb.

Równość

Liczby binarne A i B będą równe, jeśli wszystkie pary cyfr znaczących obu liczb będą równe, tj
. . .

Ponieważ liczby są binarne, cyfry mają wartość 0 lub 1, a funkcja boolowska dla równości dowolnych dwóch cyfr i> może być wyrażona jako

1 jest tylko wtedy, gdy i są równe.

Aby uzyskać równość A i B, wszystkie zmienne (dla i = 0,1,2,3) muszą wynosić 1. Zatem warunek jakości A i B można zaimplementować za pomocą operacji AND jako

zmiennej binarnej (A = B) wynosi 1 tylko wtedy, gdy wszystkie pary cyfr dwóch liczb są równe.

Nierówność

Aby ręcznie określić większą z dwóch liczb binarnych, sprawdzamy względne wielkości par cyfr znaczących, zaczynając od najbardziej znaczącego bitu, stopniowo przechodząc w kierunku niższych znaczących bitów, aż do znalezienia nierówności. Gdy zostanie znaleziona nierówność, jeśli odpowiedni bit A wynosi 1, a bit B wynosi 0, wówczas wnioskujemy, że A> B. To sekwencyjne porównanie można wyrazić logicznie jako:

Nie tylko „wie”, sprawdza za każdym razem. Zasadniczo robi to samo, co byś zrobił: aby porównać, sprawdza (od lewej), która liczba ma pierwszą cyfrę, która jest większa niż odpowiadająca jej cyfra w drugiej liczbie. Oczywiście musisz dodać wiodące zera do krótszej liczby.

Litery to tylko liczby dla komputera. Ludzie przypisali litery , np. ASCII lub Unicode , tak aby porównania liczbowe nadały również „prawidłową” kolejność liter.

To nie system operacyjny porównuje liczby całkowite, procesor się tym zajmuje. Jest wykonany na poziomie logicznych bramek, zapoznaj się z tymi slajdami, aby zobaczyć, jak to zrobić.

O alfabecie, w ASCII , znaki alfanumeryczne i inne znaki specjalne są reprezentowane jako liczby całkowite, więc ich porównanie jest również operacją porównywania liczb całkowitych, wykonywaną przez CPU.

Właściwie, aby uzyskać pełny obraz, myślę, że byłoby bardzo pomocne na własne oczy zobaczyć ścieżkę danych rzeczywistego procesora, na przykład MIPS:

Jak widać, faktycznie istnieje drugie wyjście z ALU, które jest sygnałem o nazwie Zero. Istnieje w celu wykonywania szybkich operacji rozgałęzień po ustaleniu, czy dwa argumenty porównania są równe zero, czy nie , ponieważ większość porównań w programie dotyczy rozgałęzień. Dlatego podczas tworzenia możliwości rozgałęzienia w kodzie, takich jak:

jeśli (a <b) {...}

$~\Rightarrow$$~\Rightarrow$

Zauważ, że sygnał zero jest jednym z wejść bramki AND, która określa, skąd licznik programu (PC) przyjmie swoją wartość: Zakładając, że sygnał rozgałęzienia to „1”, ponieważ mamy operację rozgałęzienia

• $\Rightarrow$
• $\Rightarrow$

Mam nadzieję, że pomogłem ci zobaczyć „pod maską”. Możesz poprosić o dalszą analizę w tej sprawie. Wiele rzeczy uważamy za pewnik, procesory robią to w bardzo fascynujący sposób!

Jeśli chcesz wiedzieć o tym, jak robi to procesor, to coś takiego.

Procesor działa na liczbach tylko do określonego rozmiaru. W dzisiejszych czasach jest to zwykle liczba całkowita 64-bitowa (zignorujemy liczby zmiennoprzecinkowe; pomysł będzie podobny).

Więc powinniśmy to rozpoznać

1. Procesor przechowuje liczby binarne o długości do (powiedzmy) 64 bitów, w jakimś formacie (prawdopodobnie uzupełnienie 2s, ale co nie ma większego znaczenia).

2. Procesor nie może natywnie nic zrobić z liczbami większymi niż to. Musimy pisać algorytmy programowe, jeśli chcemy porównywać większe liczby.

OK, powiedzmy, że mamy dwie liczby, z których każda mieści się w normalnej wielkości 64-bitowej liczbie całkowitej. Mówić$a$ i $b$. Jak porównuje je procesor? Zwykle odejmuje jeden od drugiego (jest to pojedyncza natywna operacja zaimplementowana sprzętowo).

Teraz procesor zapisał jeden numer $a-b$. Ponownie liczba ta wynosi maksymalnie 64 bity, więc mieści się w „rejestrze” o długości 64 bitów, w którym przechowujemy nasze liczby do obliczeń. Teraz sprawdza tylko, czy$a-b$jest mniejsza niż zero. Robi to za pomocą jednej natywnej operacji, która mogłaby działać na poziomie obwodu, podobnie jak algorytmy porównawcze, które opisały inne odpowiedzi. Będzie to wyglądać bardzo podobnie do tych, ale wszystkie są zaimplementowane w obwodach (ponieważ liczba wynosi maksymalnie 64 bity, jest to obwód pewnej wielkości, który możemy podłączyć i przykleić do procesora). W zależności od sposobu przechowywania liczb przez procesor może być jeszcze szybszy, ponieważ może być tak, że wszystkie liczby ujemne mają pierwszy bit ustawiony na jeden lub coś w tym rodzaju. Tak czy inaczej, w sumie jest tylko 64 bity, więc możemy zdecydowanie sprawdzić, czy liczba ta jest ujemna.

Jeśli tak, to wiemy $a < b$; jeśli nie, to wiemy$a \geq b$.

Teraz, dla większych liczb, musimy zaimplementować coś w oprogramowaniu, które wykorzysta te małe porównania jako podprogramy.

Aby odpowiedzieć na to pytanie, pozwól mi najpierw wskazać, że istnieją co najmniej dwa poziomy abstrakcji dla liczb porównawczych na komputerze, na poziomie maszyny i na poziomie oprogramowania .

Porównywanie liczb na poziomie maszyny

W dzisiejszym komputerze procesor ma bogaty zestaw instrukcji. Instrukcje te obejmują na przykład ładowanie komórki pamięci do rejestru, zwiększanie rejestru, dodawanie dwóch rejestrów i wiele innych. Muszą być również instrukcje dotyczące skoków warunkowych . Na przykład procesory z rodziny Intel x86 obsługują instrukcje jnz(skok, jeśli nie zero), jne(skok nie równy) i tak dalej. Gdyby ich brakowało, procesor nie byłby kompletny w Turingu. Zmienne, od których zależy skok warunkowy, są przechowywane w rejestrach. Tak więc instrukcje te są wbudowane w architekturę CPU jako obwód zbudowany z logicznych bram. Jest to jedyny sposób, w jaki procesor może porównać dwie liczby.

Porównywanie liczb na poziomie oprogramowania

Jeśli porównasz dwie liczby, powiedzmy w programie c ++, to zostanie to przetłumaczone na kod maszynowy, a zatem przeprowadzone na poziomie maszynowym. Jednak takie porównanie może być bardziej złożone. To zależy od typu użytych danych, w jaki sposób porównanie jest tłumaczone na kod maszynowy. Tylko jeden przykład: liczby, które chcesz porównać, pochodzą z 64-bitowych słów, ale twoje urządzenie działa tylko z 32 bitami. Wówczas liczba ta nie mieści się w rejestrze, dlatego kompilator podzieli porównanie na sekwencję porównań na poziomie kodu maszynowego. To samo dotyczy bardziej skomplikowanych typów danych / struktur danych, reprezentujących na przykład liczby wymierne, ciągi znaków lub znaki. Dlatego gdy trzeba porównać dwa znaki, jest to tłumaczone przez oprogramowanie (system operacyjny, kompilator, interpreter, ...) na kod maszynowy.

Na koniec chciałbym zauważyć, że standardowe procesory mogą również pracować z różnymi reprezentacjami liczb (liczby całkowite ze znakiem w postaci 1 lub 2 uzupełnień, liczby zmiennoprzecinkowe). Również porównania mogą być przeprowadzane w innych częściach komputera, takich jak GPU.

inne odpowiedzi są dobre, po prostu rzucając inną w celu dalszego rozważenia / wglądu z posmakiem / zwrotem CS. można zbudować FSM , maszynę skończoną, która może porównywać dwie liczby binarne o dowolnej długości, zaczynając od par od najbardziej znaczących bitów i pracując do najmniej znaczącego bitu (LSB). można go również wykorzystać do konceptualizacji komparatora cyfrowego podanego w innej odpowiedzi, jednak FSM nie wymaga liczb binarnych o skończonej długości. może nawet działać na liczbach całkowitych z ułamkami binarnymi po LSB. ma indukcyjny i rekurencyjny smak i można go udowodnić za pomocą prostej indukcji. działa w następujący sposób:

• wprowadź dwie górne cyfry binarne jako parę (a, b)
• jeśli a = 1 ib = 0, lewa liczba jest większa.
• jeśli a = 0 ib = 1, właściwa liczba jest większa.
• w przeciwnym razie liczby są „równe do chwili obecnej”, przejdź do następnej pary.

innymi słowy, największa liczba to ta z pierwszym wystąpieniem bitu, który jest jeden, a druga to zero, po początkowym przebiegu zerowym lub więcej identycznych 1. komparator cyfrowy o skończonej długości wykonany z bramek lub komparatorów 1-bitowych może być postrzegany jako oparty na ustaleniu długości tej operacji FSM do pewnej stałej liczby bitów. (tak, istnieje silna zgodność między wszystkimi obwodami skończonymi a „ustalaniem długości” obliczeń FSM).

może się to wydawać ćwiczeniem teoretycznym, ale w rzeczywistości logika w oprogramowaniu do reprezentowania dowolnych liczb dokładności operuje czymś analogicznym do tego FSM, z wyjątkiem zakodowanej w pętli komputerowej, którą można postrzegać jako zapętlanie lub symulowanie kroków FSM (wydajna implementacja może śledzić za pomocą indeksu lokalizację MSB).

pozwala również rozsądnie interpretować / uogólniać to pytanie jako nieograniczone do liczb całkowitych . pytanie dotyczy liczb całkowitych, ale tytuł odnosi się tylko do liczb. zaskakująco nikt jeszcze nie wspomniał o arytmetyki zmiennoprzecinkowej .

w zasadzie działa to poprzez porównanie wykładnika i mantysy, gdzie liczba jest w postaci$a \times 10^b$, $a$mantysa, b wykładnik potęgi. mantysę można znormalizować do liczby, w której pierwsza cyfra jest zawsze niezerowa. następnie, aby porównać dwie liczby, logika najpierw porównuje wykładniki$b$, a jeśli są nierówne, może zwrócić wynik bez porównywania mantys (używając powiedzmy obwodu komparatora). jeśli wykładniki są równe, porównuje mantysę.