Artykuł pobrano ze strony
eioba.pl
Operacje arytmetyczne w systemie dwójkowym
Zasady arytmetyki w systemie binarnym są identyczne (prawie) jak w dobrze nam
znanym systemie dziesiętnym. Zaletą arytmetyki binarnej jest jej prostota, dzięki
czemu można ją tanio realizować za pomocą układów elektronicznych.
Poniżej opisujemy zasady wykonywania podstawowych działań arytmetycznych wraz
z odpowiednimi przykładami.
Do wykonywania dodawania niezbędna jest znajomość tabliczki dodawania, czyli
wyników sumowania każdej cyfry z każdą inną. W systemie binarnym mamy tylko
dwie cyfry 0 i 1, zatem tabliczka dodawania jest niezwykle prosta i składa się tylko
z 4 pozycji:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 =
1
0
Zsumować liczby binarne 1111001
(2)
oraz 10010
(2)
.
Sumowane liczby zapisujemy jedna pod drugą tak, aby w kolejnych
kolumnach znalazły się cyfry stojące na pozycjach o tych samych
wagach (identycznie postępujemy w systemie dziesiętnym zapisując
liczby w słupkach przed sumowaniem):
1.
1111001
+
10010
Sumowanie rozpoczynamy od ostatniej kolumny. Sumujemy cyfry w
kolumnie zgodnie z podaną tabelką zapisując wynik pod kreską:
1.
1111001
+
10010
1011
Jeśli wynik sumowania jest dwucyfrowy (1 + 1 = 10), to pod kreską
zapisujemy tylko ostatnią cyfrę 0, a 1 przechodzi do następnej
kolumny - dodamy ją do wyniku sumowania cyfr w następnej
kolumnie. Jest to tzw. przeniesienie (ang. carry). Przeniesienie
zaznaczyliśmy na czerwono:
1.
1
1111001
+ 10010
01011
Jeśli w krótszej liczbie zabrakło cyfr, to dopisujemy zera.
Pamiętajmy o przeniesieniach.
1.
1 1 1
1111001
+ 0010010
0001011
Dodaliśmy wszystkie cyfry, ale przeniesienie wciąż wynosi 1. Zatem
1.
dopisujemy je do otrzymanego wyniku (możemy potraktować pustą
kolumnę tak, jakby zawierała cyfry 0 i do wyniku sumowania dodać
przeniesienie).
1 1 1
01111001
+ 00010010
10001011
1111001
(2)
+ 10010
(2)
= 10001011
(2)
(121 + 18 = 139)
Oto kilka dalszych przykładów:
1 1 1 1 1 1 1
01111111
+ 00000001
10000000
1 1 1 1 1 1 1
01111111
+ 00000101
10000100
1 1 1 1
10111110
+ 00001100
11001010
W pamięci komputera liczby binarne przechowywane są w postaci ustalonej ilości
bitów (np. 8, 16, 32 bity). Jeśli wynik sumowania np. dwóch liczb 8 bitowych jest
większy niż 8 bitów, to najstarszy bit (dziewiąty bit) zostanie utracony. Sytuacja taka
nazywa się nadmiarem(ang. overflow) i występuje zawsze, gdy wynik operacji
arytmetycznej jest większy niż górny zakres danego formatu liczb binarnych (np. dla
8 bitów wynik większy od 2
8
- 1, czyli większy od 255):
11111111
(2)
+ 00000001
(2)
=
1
|00000000
(2)
(255 + 1 = 0)
Przy nadmiarze otrzymany wynik jest zawsze błędny, dlatego należy bardzo
dokładnie analizować problem obliczeniowy i ustalić typy danych zgodnie z
przewidywanym zakresem wartości otrzymywanych wyników. Zwykle kompilatory
języków programowania posiadają opcję włączenia sprawdzania zakresów wyników
operacji arytmetycznych na liczbach całkowitych (w Dev-Pascalu jest to opcja menu
Options/Compiler Options, a w okienku opcji na zakładce Code
generation/Optimization zaznaczamy Check overflow of integer operations). Opcję
tę włączamy w fazie testowania programu. Natomiast w gotowym produkcie należy ją
wyłączyć, ponieważ wydłuża czas wykonywania operacji arytmetycznych.
program overflow;
{$APPTYPE CONSOLE}
var
a : byte; // dana 8 bitowa
b : word; // dana 16 bitowa
c : longword; // dana 32 bitowa
begin
a := $FF; // wszystkie bity na 1
b := $FFFF;
c := $FFFFFFFF;
writeln(' 8b 16b 32b');
writeln('Przed dodaniem 1 : ',a:5,b:7,c:12);
inc(a); inc(b); inc(c); // dodajemy 1 do każdej zmiennej
writeln('Po dodaniu 1 : ',a:5,b:7,c:12);
readln;
end.
8b 16b 32b
Przed dodaniem 1 : 255 65535 4294967295
Po dodaniu 1 : 0 0 0
Przy odejmowaniu korzystamy z tabliczki odejmowania, która w systemie binarnym
jest bardzo prosta:
0 - 0 = 0
0 - 1 = 1 i pożyczka do następnej pozycji
1 - 0 = 1
1 - 1 = 0
Odejmując 0 - 1 otrzymujemy wynik 1 i pożyczkę (ang. borrow) do następnej
pozycji. Pożyczka oznacza konieczność odjęcia 1 od wyniku odejmowania cyfr w
następnej kolumnie. Identycznie postępujemy w systemie dziesiętnym, tyle że tam
jest to o wiele bardziej skomplikowane.
Na razie załóżmy, iż od liczb większych odejmujemy mniejsze (w przeciwnym razie
musielibyśmy wprowadzić liczby ujemne, a nie chcemy tego robić w tym miejscu).
Wykonać odejmowanie w systemie binarnym 1101110
(2)
-
1111
(2)
.
Obie liczby umieszczamy jedna pod drugą tak, aby ich cyfry
znalazły się w kolumnach o tych samych wagach:
1.
1101110
-
1111
Odejmowanie rozpoczynamy od cyfr ostatniej kolumny. Wyniki
zapisujemy pod kreską. W tym przykładzie odjęcie ostatnich cyfr 0 -
1 daje wynik 1 oraz pożyczkę do następnej kolumny. Pożyczki
zaznaczamy kolorem czerwonym.
1.
1
1101110
- 1111
1
Odjęcie cyfr w drugiej od końca kolumnie daje wynik 1 - 1 = 0. Od
tego wyniku musimy odjąć pożyczkę 0 - 1 = 1 i pożyczka do
następnej kolumny.
1.
1 1
1101110
- 1111
11
Według tych zasad kontynuujemy odejmowanie cyfr w pozostałych
kolumnach. Pamiętaj o pożyczkach! Jeśli w krótszej liczbie
zabraknie cyfr, to możemy kolumny wypełnić zerami:
1.
1 1 1 1 1
1101110
- 0001111
1011111
1101110
(2)
- 1111
(2)
= 1011111
(2)
(110
(10)
- 15
(10)
= 95
(10)
).
Oto kilka dalszych przykładów:
1 1 1 1 1 1 1
10000000
- 00000001
01111111
1 1 1 1
11110000
- 00001111
11100001
1
1
1
1
10101010
- 01010101
01010101
Przy odejmowaniu również może dochodzić do nieprawidłowych sytuacji. Jeśli od
liczby mniejszej odejmiemy mniejszą, to wynik będzie ujemny. Jednakże w
naturalnym systemie binarnym nie można zapisywać liczb ujemnych. Zobaczmy
zatem co się stanie, gdy od liczby 0 odejmiemy 1, a wynik ograniczymy do 8 bitów:
1 1 1 1 1 1 1 1
00000000
- 00000001
11111111
Otrzymujemy same jedynki, a pożyczka nigdy nie zanika. Sytuacja taka nazywa się
niedomiarem(ang. underflow) i występuje zawsze, gdy wynik operacji arytmetycznej
jest mniejszy od dolnego zakresu formatu liczb binarnych (dla naturalnego kodu
dwójkowego wynik mniejszy od zera). Oczywiście otrzymany rezultat jest błędny:
program underflow;
{$APPTYPE CONSOLE}
var
a : byte; // dana 8 bitowa
b : word; // dana 16 bitowa
c : longword; // dana 32 bitowa
begin
a := 0; // wszystkie bity na 0
b := 0;
c := 0;
writeln(' 8b 16b 32b');
writeln('Przed odejmowaniem 1 : ',a:5,b:7,c:12);
dec(a); dec(b); dec(c); // odejmujemy 1 od każdej zmiennej
writeln('Po odejmowaniu 1 : ',a:5,b:7,c:12);
readln;
end.
8b 16b 32b
Przed odejmowaniem 1 : 0 0 0
Po odejmowaniu 1 : 255 65535 4294967295
Naukę mnożenia binarnego rozpoczynamy od tabliczki mnożenia. Bez paniki - jest
ona równie prosta jak podane powyżej tabliczki
dodawania
i
odejmowania
.
0 x 0 = 0
0 x 1 = 0
1 x 0 = 0
1 x 1 = 1
Tabliczka mnożenia binarnego (podobnie jak w systemie dziesiętnym) posłuży do
tworzenia iloczynów częściowych cyfr mnożnej przez cyfry mnożnika. Iloczyny te
następnie dodajemy wg opisanych zasad i otrzymujemy wynik mnożenia.
Pomnożyć binarnie liczbę 1101
(2)
przez 1011
(2)
.
Obie liczby umieszczamy jedna pod drugą tak, aby ich cyfry
znalazły się w kolumnach o tych samych wagach:
1.
1101
x 1011
Każdą cyfrę mnożnej mnożymy przez poszczególne cyfry mnożnika
zapisując wyniki mnożeń w odpowiednich kolumnach - tak samo
postępujemy w systemie dziesiętnym, a tutaj jest nawet prościej,
gdyż wynik mnożenia cyfry przez cyfrę jest zawsze jednocyfrowy:
1.
1101
x 1011
1101
1101
0000
1101
Zwróć uwagę, iż wynikiem mnożenia mnożnej przez cyfrę
mnożnika jest powtórzenie mnożnej z przesunięciem o
pozycję cyfry (cyfra mnożnika 1) lub same zera (cyfra
mnożnika 0). Spostrzeżenie to bardzo ułatwia konstrukcję
układów mnożących.
Puste kolumny uzupełniamy zerami i dodajemy do siebie wszystkie
cyfry w kolumnach. Uważaj na przeniesienia.
1.
1101
x 1011
0001101
0011010
+1101000
10001111
Sprawdź, czy otrzymany wynik jest poprawny.
Oto kilka dalszych przykładów:
101
x 111
101
101
+101
100011
1011
x 110
0000
1011
+1011
1000010
111
x 111
111
111
+111
110001
Z uwagi na ustalone formaty danych binarnych w komputerach (8, 16 i 32 bity)
mnożenie również może dawać niepoprawne rezultaty, gdy wynik będzie większy od
górnego zakresu liczb dla danego formatu, czyli od
max = 2
n
- 1, gdzie n - liczba bitów w danym formacie.
Poniżej prezentujemy odpowiedni przykład programowy:
program overflow;
{$APPTYPE CONSOLE}
var
a : byte; // dana 8 bitowa
b : word; // dana 16 bitowa
c : longword; // dana 32 bitowa
begin
a := $10; // 2^4
b := $100; // 2^8
c := $10000; // 2^16
writeln(' 8b 16b 32b');
writeln('Przed mnozeniem : ',a:5,b:7,c:12);
a := a * a; // a nie pomieści wyniku 2^8!
b := b * b; // b nie pomieści wyniku 2^16!
c := c * c; // c nie pomieści wyniku 2^32!
writeln('Po mnozeniu : ',a:5,b:7,c:12);
readln;
end.
8b 16b 32b
Przed mnozeniem : 16 256 65536
Po mnozeniu : 0 0 0
DLA
GENIUSZA
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ć.
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ę:
1.
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.
1 - pierwsza cyfra wyniku dzielenia
1101 - dzielna
-10 - przesunięty dzielnik
0101 - 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.
110 - wynik dzielenia
1101 - dzielna
-10 - przesunięty dzielnik
0101
- dzielna po pierwszym odejmowaniu przesuniętego
dzielnika
- 10 - przesunięty dzielnik
0001 - dzielna po drugim odejmowaniu przesuniętego dzielnika
- 10 - dzielnik na swoim miejscu, odejmowanie niemożliwe
0001 - 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.
1.
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)
).
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.
Autor: mgr Jerzy Wałaszek
Przedruk ze strony:
http://www.i-lo.tarnow.pl/edu/inf/alg/num/index.html
Artykuł pobrano ze strony
eioba.pl