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


34

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<21,2,3,4,5,


1
Aby odpowiedź na to pytanie była zadowalająca, musielibyśmy wiedzieć, ile Ricky Stam wie o architekturze komputerowej. Z pytania to wygląda bardzo mało, więc żadna z poniższych fantazyjnych odpowiedzi nie będzie dla niego zrozumiała.
Andrej Bauer,

@AndrejBauer: Właściwie nie zalogował się od czasu zadania pytania. Może teraz wie wszystko, czego potrzebuje.
Dave Clarke

Odpowiedzi:


31

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
wprowadź opis zdjęcia tutaj
wprowadź opis zdjęcia tutaj
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
wprowadź opis zdjęcia tutaj. wprowadź opis zdjęcia tutaj. wprowadź opis zdjęcia tutaj. wprowadź opis zdjęcia tutaj

Ponieważ liczby są binarne, cyfry mają wartość 0 lub 1, a funkcja boolowska dla równości dowolnych dwóch cyfr wprowadź opis zdjęcia tutaji> wprowadź opis zdjęcia tutajmoże być wyrażona jako
wprowadź opis zdjęcia tutaj

wprowadź opis zdjęcia tutaj 1 jest tylko wtedy, gdy wprowadź opis zdjęcia tutaji wprowadź opis zdjęcia tutaj są równe.

Aby uzyskać równość A i B, wszystkie wprowadź opis zdjęcia tutajzmienne (dla i = 0,1,2,3) muszą wynosić 1. Zatem warunek jakości A i B można zaimplementować za pomocą operacji AND jako
wprowadź opis zdjęcia tutaj
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:

wprowadź opis zdjęcia tutaj


2
Whoa, co tu się dzieje?
Gilles „SO- przestań być zły”

1
„Najpierw liczby całkowite są konwertowane na liczby binarne” ... źle, na początku są tylko liczby binarne w pamięci, wszystkie 1 i 0 na poziomie maszyny, więc nie ma „konwersji”, 2 to reprezentowane jako 10 od początku do końca.
Dr.Haimovitz

Podczas kopiowania materiałów z innych źródeł musisz podać odpowiednie źródła swoich źródeł. Zobacz tutaj i tutaj .
DW

Dwubitowa cyfrowa tabela porównawcza jest niepoprawna. ijesi.org/papers/Vol(2)1%20(version%202)/C211324.pdf, gdy A1, A0 są równe zero, ale B0 i B1 są równe 0, 1 A> B będzie wynosić na przykład 0.
user1455116

14

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.


Ponadto jest to zwykle nazywane „ porządkiem leksykograficznym ”. Zwykle możemy myśleć o tym jako o kolejności według długości (od najkrótszej do najdłuższej), a następnie alfabetycznie.
usul

@usul To przypomina mi, że szczegóły porównywania liczb całkowitych oczywiście zależą od konkretnego kodowania; to, co opisuję, działa dla „naiwnych” liczb binarnych, które mogą być dalekie od tego, co wykorzystuje rzeczywisty procesor.
Raphael

Tak, absolutnie. Zbyt często myślałem o maszynach Turinga :). Prawdziwe maszyny nie do końca pasują do tego, co tu mówiliśmy ...
usul

9

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.


4

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: wprowadź opis zdjęcia tutaj

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) {...}

  

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

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!


Ethan, jak działa operacja „mniej” na tej ścieżce danych? Jak rozumiem, opisałeś operację „nie równa się”. Co oznacza instrukcja „SLT”?
osgx,

2

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ćza 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 za-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, czyza-bjest 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 za<b; jeśli nie, to wiemyzab.

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


1

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.


0

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 postaciza×10b, zamantysa, 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ładnikib, 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ę.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.