Jak wykrywa się przepełnienie na poziomie binarnym?

Za każdym razem, gdy chcesz radzić sobie z tego rodzaju elementami alu, czy to dodawanie, odejmowanie, mnożenie itp., zacznij od liczb 2 lub 3 bitowych, o wiele łatwiej jest uzyskać uchwyt na liczbach 32 lub 64 bitowych. po 2 lub 3 bitach nie ma znaczenia, czy jest to 22 lub 2200 bitów, wszystko działa dokładnie tak samo od tego momentu. Zasadniczo można ręcznie, jeśli chcesz zrobić tabelę wszystkich 3-bitowych operandów i ich wyników, tak aby można było zbadać całą tabelę wizualnie, ale tabelę wszystkich 32-bitowych operandów przeciwko wszystkim 32-bitowym operands i ich wyniki nie mogą zrobić tego ręcznie w rozsądnym czasie i nie mogą wizualnie zbadać całej tabeli.

Teraz dopełniają się dwójki, to jest tylko schemat przedstawiania liczb dodatnich i ujemnych, i nie jest to jakaś arbitralna rzecz, która ma powód, powodem szaleństwa jest to, że twoja logika dodawania (która jest również tym, czego używa odejmer, który jest tego samego rodzaju rzeczą, której używa mnożnik) nie dba o niepodpisane lub podpisane. Nie zna różnicy. YOU the programista dba w moim świecie trzech bitów bit patter 0b111 może być postitive seven (+7) lub może być ujemny. Ten sam wzorzec bitowy, podaj go do logiki add i wyjdzie to samo, a odpowiedź, która wyjdzie, mogę wybrać interpretację jako niepodpisane lub dopełniacz dwójek (tak długo, jak interpretuję operandy i wynik jako niepodpisane lub wszystkie jako dopełniacz dwójek). Dopełniacz dwójkowy ma również tę funkcję, że dla liczb ujemnych ustawiany jest bit najbardziej znaczący (msbit), dla liczby dodatnie to zero. Więc to nie jest znak plus wielkość, ale nadal mówimy o msbit jest Bit znak, bo z wyjątkiem dwóch specjalnych liczb, które jest to, co nam mówi, znak liczby, inne bity są rzeczywiście mówi nam wielkość są po prostu nie unsigned wielkości, jak można mieć w znak + wielkość notacji.

Więc kluczem do tego całego pytania jest zrozumienie swoich ograniczeń. Dla 3-bitowej liczby niepodpisanej nasz zakres wynosi od 0 do 7, 0b000 do 0b111. na interpretacja 3-bitowa (dopełniacz dwójkowy) nasz zakres wynosi od -4 do +3 (0b100 do 0b011). Na razie ograniczamy się do 3 bitów jeśli dodamy 7+1, 0b111 + 0b001 = 0b1000, ale mamy tylko 3 bitowy system, czyli 0b000, 7 + 1 = 8, nie możemy reprezentować 8 w naszym systemie, więc jest to przepełnienie, ponieważ tak się składa, że interpretujemy bity jako niepodpisane patrzymy na "unsigned overflow", który jest również znany jako carry bit lub flaga. Jeśli weźmiemy te same bity, ale zinterpretujemy je jako Podpisane, to 0b111 (-1) + 0b001 (+1) = 0b000 (0). Minus jeden plus jeden to zero. Brak przepełnienia, "podpisane przepełnienie" nie jest ustawione...Co to jest podpisane przepełnienie?

Najpierw co to jest "unsigned overflow".

Powód, dla którego" wszystko działa tak samo", bez względu na to, ile bitów mamy w naszych rejestrach, nie różni się od podstawowej matematyki z liczbami 10 (dziesiętnymi). Jeśli dodasz 9 + 1, które są oba w kolumnie one, mówisz 9 + 1 = zero. przenosisz jedną do kolumny tens, a następnie 1 plus 0 plus 0 (wypełniłeś dwa zera w kolumnie tens) to 1. MASZ 1 w kolumnie dziesiątki i zero w kolumnie jedynki

  1
  09
 +01
====
  10

Co by było, gdybyśmy zadeklarowali, że jesteśmy ograniczeni tylko do liczb w kolumnie jedynek, nie ma miejsca na kolumnę dziesiątek. Dobrze, że BIT carry jest niezerowy oznacza, że mamy przepełnienie, aby poprawnie obliczyć wynik potrzebujemy innej kolumny, tak samo z binarnym

  111 
   111
 + 001
=======
  1000

7 + 1 = 8, ale nie możemy zrobić 8 jeśli zadeklarujemy system 3 bitowy, my może zrobić 7 + 1 = 0 z zestawem bitów nośnych. Tutaj pojawia się piękno dopełnienia dwójek:

  111 
   111
 + 001
=======
   000

Jeśli spojrzysz na powyższe dodanie trzech bitów, nie możesz stwierdzić, patrząc, czy to jest 7 + 1 = 0 z ustawionym bitem przenoszenia, czy to jest -1 + 1 = 0.

Więc dla unsigned dodanie, jak wiemy od podstawówki, że przeniesienie do następnej kolumny czegoś innego niż zero oznacza, że mamy przepełnione, że wiele elementów zastępczych i potrzebujemy jeszcze jednego elementu zastępczego, jeszcze jednej kolumny, aby utrzymać właściwą odpowiedź.

Podpisane przepełnienie. Rodzaj akademickiej odpowiedzi brzmi, jeśli carry in kolumny msbit nie pasuje do carry out. weźmy kilka przykładów w naszym 3-bitowym świecie. Tak więc z dopełnieniem dwójek jesteśmy ograniczeni do -4 do + 3. więc jeśli dodamy -2 + -3 = -5 to nie zadziała poprawnie? Aby dowiedzieć się, co minus dwa to robimy odwrócenie i dodajemy jeden 0b010, odwrócony 0b101, dodajemy jeden 0B110. minus trzy to 0b011 - > 0b100 - > 0b101

Więc teraz możemy zrobić to:

  abc
  100 
   110
 + 100
======
   010

Jeśli spojrzysz na liczbę pod b, która jest "carry in" do kolumny msbit, Liczba pod a the 1, jest przeprowadzeniem, te dwa nie pasują, więc wiemy, że jest "signed overflow"

Spróbujmy 2 + 2 = 4

  abc
  010
   010
 + 010
======
   100

Można powiedzieć, ale to wygląda dobrze, na pewno niepodpisane, ale robimy tutaj podpisaną matematykę, więc wynik jest w rzeczywistości -4, a nie dodatni 4. 2 + 2 != -4. carry in which is under the b is a 1, The carry out of the msbit is zero, carry in I carry out nie pasują. podpisane przelewy.

Istnieje skrót do określenia podpisanego przelewu bez konieczności patrzenia na carry in (lub carry out). if (msbit (opa) = = msbit ( opb)) & & (msbit (res) != msbit (opb)) signed overflow, else no signed overflow. opa jest jednym operandem, opb jest drugim i res wynik.

   010
 + 010
======
   100

Weź to +2 + +2 = -4. msbit (opa) i msbit (opb) są równe, a wynik msbit nie jest równy OPB msbit więc to jest podpisane przepełnienie. Możesz o tym pomyśleć używając tej tabeli

x ab cr 
0 00 00
0 01 01
0 10 01
0 11 10 signed overflow
1 00 01 signed overflow
1 01 10
1 10 10
1 11 11

Ta tabela jest wszystkimi możliwymi kombinacjami, jeśli carry in bit, operand a, operand b, carry out i result bit dla pojedynczej kolumny obróć głowę bokiem w lewo, aby zobaczyć, że X jest carry in, kolumny a i B są dwoma operandami. cr jako para jest wynikiem xab 011 oznacza 0+1+1 = 2 dziesiętne, co jest wartością binarną 0b10. Przyjmując więc regułę, która nam została podyktowana, że jeśli przenosimy i przenosimy out do not match that is a signed overflow. Dobrze dwa przypadki, w których element w kolumnie x nie pasuje do elementu w kolumnie c są wskazane, są to przypadki, w których wejścia a i b pasują do siebie, ale bit wyniku jest przeciwieństwem a i b. więc zakładając, że reguła jest poprawna, ten szybki skrót, który nie wymaga wiedzy, jakie są bity przenoszenia, powie Ci, czy było podpisane przepełnienie.

Teraz czytasz książkę H & P. Co prawdopodobnie oznacza mips lub dlx, ani mips lub dlx zajmują się przenoszeniem i podpisywaniem FLAG w sposób, w jaki robi to większość innych procesorów. mips nie jest najlepszym pierwszym zestawem instrukcji IMO przede wszystkim z tego powodu, ich podejście nie jest złe w żaden sposób, ale będąc dziwakiem, spędzisz zawsze myślenie inaczej i konieczność tłumaczenia podczas przechodzenia do większości innych procesorów. Gdzie jeśli nauczyłeś się typowych FLAG znvc (flaga zerowa, flaga ujemna, V=signed overflow, c=carry lub unsigned overflow) to musisz tylko przetłumaczyć, gdy idziesz do mips. Zwykle są one obliczane przy każdej operacji alu (dla procesorów innych niż MIPS), podczas dodawania i odejmowania zobaczysz podpisane i niepodpisane przepełnienie. (Jestem przyzwyczajony do starszego mips, może ten gen książek i obecny zestaw instrukcji ma coś innego). Nazwanie go addu add unsigned tuż na początku mips po zapoznaniu się z wszystkimi powyższymi informacjami o tym, jak układ adder nie dba o signed vs unsigned, jest ogromnym problemem z mips to naprawdę stawia cię w złe nastawienie do zrozumienia czegoś tak prostego. Prowadzi to do przekonania, że istnieje różnica między podpisanym dodaniem a niepodpisanym dodaniem, gdy nie ma. To tylko flagi przepełnienia, które są obliczane inaczej. Teraz mnożenie i dzielenie jest definitywnie dopełniacz dwójek vs niepodpisana różnica i idealnie potrzebujesz mnożenia podpisanego i niepodpisanego lub musisz poradzić sobie z ograniczeniem.

Polecam prosty (w zależności od tego jak mocny jest Twój bit manipulacja jest i dwójki dopełniają) ćwiczenia, które można napisać w jakimś języku wysokiego poziomu. Zasadniczo weź wszystkie kombinacje niepodpisanych liczb od 0 do 7 dodanych do 0 do 7 i zapisz wynik. Wypisuje zarówno w postaci dziesiętnej, jak i binarnej (trzy bity dla operandów, cztery bity dla wyniku) i jeśli wynik jest większy niż 7, wydrukuj przepełnienie. Powtórz to używając podpisanych zmiennych używając liczb od -4 do +3 dodanych do -4 do +3. wypisuje zarówno dziesiętne ze znakiem+/ -, jak i binarne. Jeśli wynik jest mniej niż -4 lub więcej niż +3 przepełnienie wydruku. Z tych dwóch tabel powinieneś być w stanie zobaczyć, że powyższe zasady są prawdziwe. Patrząc ściśle na wzorce bitowe operandu i wynikowych dla dozwolonego rozmiaru (w tym przypadku trzy bity), zobaczysz, że operacja dodawania daje ten sam wynik, ten sam wzór bitowy dla danej pary wejść niezależnie od tego, czy te wzorce bitowe są uważane za niepodpisane, czy za dopełnienie dwójek. Możesz również sprawdzić, czy niepodpisane przepełnienie jest wtedy, gdy wynik musi użyj tej czwartej kolumny, jest przeprowadzka z msbit. dla signed when carry in doesnt match the carry out, które widzisz używając skrótu patrząc na msbits operands i result. Jeszcze lepiej jest, aby twój program zrobił te porównania i wydrukował coś. Jeśli więc widzisz notatkę w tabeli, której wynik jest większy niż 7, a notatkę w tabeli, której bit 3 jest ustawiony w wyniku, zobaczysz dla tabeli niepodpisanej, która zawsze ma miejsce (ograniczone do danych wejściowych od 0 do 7). A bardziej skomplikowany, signed overflow, jest zawsze wtedy, gdy wynik jest mniejszy niż -4 i większy niż 3 i gdy górne bity operandu pasują, a górny bit wyniku nie pasują do operandów.

Wiem, że to jest bardzo długie i bardzo elementarne. Jeśli całkowicie pominąłem tutaj znak, proszę o komentarz, a ja usunę lub ponownie napiszę tę odpowiedź. Druga połowa dwójek uzupełnia magię. sprzęt nie posiada logiki odejmowania. jeden sposób na "konwersję" na dwójki dopełnieniem jest "odwrócenie i dodanie jednego". gdybym chciał odjąć 3-2 za pomocą dwójek dopełniających to co faktycznie się dzieje to jest to samo co + 3 + (-2) prawo, a aby uzyskać od +2 do -2 odwracamy i dodajemy jeden. Patrząc na nasz dodatek do podstawówki, zauważyłeś dziurę w nosidełku w pierwszej kolumnie?

  111H
   111
 + 001
=======
  1000

Umieściłem H powyżej, gdzie jest dziura. Cóż, że carry in bit jest dodawany do operandów, prawda? nasza logika dodawania nie jest dodawarką dwu wejściową, jest to dodawarka trzy wejściowa tak? większość kolumn musi dodać trzy liczby jednobitowe, aby obliczyć dwa operandy. Jeśli użyjemy trzy wejścia adder na pierwszej kolumnie teraz mamy miejsce do ... dodaj jedną. Gdybym chciał odjąć 3 - 2 = 3 + (-2) = 3 + (~2) + 1 czyli:

    1
  011
+ 101
=====

Zanim zaczniemy i wypełnimy to jest:

 1111
  011
+ 101
=====
  001

3 - 2 = 1.

To, co robi logika, to:

If add then carry in = 0; operand b nie jest odwrócony, carry out nie jest odwrócony. if subtract then carry in = 1; operand b jest odwrócony, wykonanie może być odwrócone.

Dodatek powyżej pokazuje przeprowadzenie, nie wspomniałem, że jest to operacja niepodpisana 3-2 = 1. Użyłem kilku sztuczek dopełniających dwójki, aby wykonać operację niepodpisaną, ponieważ tutaj ponownie Bez względu na to, czy interpretuję operandy jako Podpisane czy niepodpisane, te same zasady dotyczą if add lub if subtract. Dlaczego powiedziałem, że carry out może być odwrócony jest to, że niektóre procesory odwracają carry out, a niektóre nie. to musi zrobić z operacjami kaskadowymi, biorąc powiedzmy 32-bitową logikę dodawania i używając flagi carry I add with carry lub subtract z instrukcją borrow, tworząc 64-bitowy add lub subtract, lub dowolną wielokrotność podstawowego rozmiaru rejestru. powiedzmy, że masz dwie 64-bitowe liczby w 32-bitowym systemie a: b + c: D gdzie a: b to 64-bitowa liczba, ale jest przechowywana w dwóch rejestrach a i b, gdzie a to górna połowa, A b to dolna połowa. więc a: b + c: d = e: f na 32 bitowym systemie niepodpisanym, który ma bit carry i dodaje z carry:

add f,b,d
addc e,a,c

Add pozostawia swój bit carry out z górnego pasa większości bitów we fladze carry w rejestrze stanu, Instrukcja addc to add with carry pobiera operandy a+c i jeśli bit carry jest ustawiony, dodaje jeszcze jeden. a + c + 1 umieszczając wynik w e I carry out w fladze carry, więc

add f,b,d
addc e,a,c
addc x,y,z

Jest 96-bitowym dodatkiem i tak dalej. Tutaj znowu coś bardzo obcego mips, ponieważ nie używa FLAG jak inne procesory. Where the invert or dont invert comes in for signed carry out is on the subtract with borrow for a particular processor. dla odjęcia:

If subtract then carry in = 1; operand b jest odwrócony, carry out może być odwrócony.

Aby odjąć pożyczkę, musisz powiedzieć, że jeśli flaga carry z rejestru statusu wskazuje pożyczkę, to carry in jest 0, w przeciwnym razie carry in jest 1, i musisz wprowadzić carry out do rejestru statusu, aby wskazać pożyczkę.

Zasadniczo dla normalnego odejmuj niektóre procesory odwracają operand b i kontynuują w drodze i przeprowadzają w drodze, niektóre procesory odwracają operand b i przeprowadzają w drodze, ale dont odwracają przeprowadzają w drodze. Wtedy, gdy chcesz wykonać warunkową gałąź, musisz wiedzieć, czy znacznik carry oznacza większe lub mniejsze niż (często składnia będzie miała gałąź if greater lub gałąź if less than I czasami powie Ci, która z nich jest uproszczoną gałąź if carry set lub gałąź if carry clear). (jeśli dont " get " to, co właśnie tam powiedział, że jest to kolejna równie długa odpowiedź, która nie znaczy nic tak długo, jak studiujesz mips).