Dzielenie binarne jest najbardziej skomplikowaną operacją arytmetyczną z dotychczas opisywanych. Wymyślono wiele algorytmów efektywnego dzielenia, ale dla potrzeb tego opracowania wystarczy znany wam algorytm szkolny, który polega na cyklicznym odejmowaniu odpowiednio przesuniętego dzielnika od dzielnej. W systemie dwójkowym jest to szczególnie proste, ponieważ dzielnika nie musimy mnożyć.
PRZYKŁAD
Podzielimy liczbę 1101(2) przez 10(2) (13(10) : 2(10)).
- Przesuwamy w lewo dzielnik, aż zrówna się jego najstarszy, niezerowy bit z najstarszym, niezerowym bitem dzielnej. Nad dzielną rysujemy kreseczkę:
1101 - dzielna 10 - przesunięty dzielnik
- Porównujemy dzielną z dzielnikiem. Jeśli dzielna jest większa lub równa dzielnikowi, to odejmujemy od niej dzielnik. Ponad kreską na pozycji ostatniej cyfry dzielnika piszemy 1. Jeśli dzielna jest mniejsza od dzielnika, to nie wykonujemy odejmowania, lecz przesuwamy dzielnik o 1 pozycję w prawo i powtarzamy opisane operacje. Jeśli w ogóle dzielnika nie da się odjąć od dzielnej (np. przy dzieleniu 7 przez 9), to wynik dzielenia wynosi 0, a dzielna ma w takim przypadku wartość reszty z dzielenia. W naszym przykładzie odejmowanie to jest możliwe, zatem:
1 - pierwsza cyfra wyniku dzielenia 1 1 0 1 - dzielna - 1 0 - przesunięty dzielnik 0 1 0 1 - wynik odejmowania dzielnika od dzielnej
- Dzielnik przesuwamy o jeden bit w prawo i próbujemy tego samego z otrzymaną różnicą. Jeśli odejmowanie jest możliwe, to nad kreską w następnej kolumnie dopisujemy 1, odejmujemy dzielnik od różnicy, przesuwamy go o 1 bit w prawo i kontynuujemy. Jeśli odejmowanie nie jest możliwe, to dopisujemy nad kreską 0, przesuwamy dzielnik o 1 bit w prawo i kontynuujemy.
1 1 0 - wynik dzielenia 1 1 0 1 - dzielna - 1 0 - przesunięty dzielnik 0 1 0 1 - dzielna po pierwszym odejmowaniu przesuniętego dzielnika - 1 0 - przesunięty dzielnik 0 0 0 1 - dzielna po drugim odejmowaniu przesuniętego dzielnika - 1 0 - dzielnik na swoim miejscu, odejmowanie niemożliwe 0 0 0 1 - reszta z dzielenia
- Operacje te wykonujemy dotąd, aż dzielnik osiągnie swoją pierwotną wartość. Pozostała dzielna jest resztą z dzielenia. Oczywiście w tym momencie możemy dalej kontynuować odejmowanie wg opisanych zasad otrzymując kolejne cyfry ułamkowe - identycznie postępujemy w systemie dziesiętnym. Jednakże pozostawimy ten problem do rozwiązania bardziej ambitnym czytelnikom.
W naszym przykładzie otrzymaliśmy wynik dzielenia równy:
1101(2) : 10(2) = 110(2) i resztę 1(2) (6(10) i 1(10))
Jest to wynik poprawny, gdyż 2 mieści się w 13 sześć razy i pozostaje reszta 1.
Dla wprawki podzielmy liczbę 110101101(2) przez 111(2) (429(10) przez 7(10)):
0111101 - wynik dzielenia
110101101 : 111
111 - nie da się odjąć, nad kreską 0
110101101
111 - da się odjąć, nad kreską 1
11001101
111 - da się odjąć, nad kreską 1
1011101
111 - da się odjąć, nad kreską 1
100101
111 - da się odjąć, nad kreską 1
1001
111 - nie da się odjąć, nad kreską 0
1001
111 - da się odjąć, nad kreską 1, koniec
10 - reszta z dzielenia
110101101(2) : 111(2) = 111101(2) i reszta 10(2) (429(10) : 7(10) = 61(10) i reszta 2(10)).
Brak komentarzy:
Prześlij komentarz