Liczby zapisywane w postaci binarnej składają się z ciągów zer i jedynek. Obecnie wykorzystywanych jest kilka rodzajów systemów binarnych, z których najpopularniejsze to:
- naturalny system dwójkowy (ang. Natural Binary System - NBS), który umożliwia zapisywanie wyłącznie liczb nieujemnych,
- kod uzupełnień do dwóch, w skrócie U2 lub ZU2 (ang. Two's Complement - 2C), za pomocą którego można zapisywać liczby dodatnie i ujemne.
Zapis liczb w NBS
Liczba binarna zapisana w systemie NBS i posiadająca n cyfr, może przyjmować wartości od 0 do 2n-1.
Zapis ułamkowy w NBS
Za pomocą systemu NBS można zapisywać liczby binarne ułamkowe stałoprzecinkowe. Pewna ilość bitów koduje wtedy wartość ułamkową liczby.
Dodawanie liczb w NBS
Dodawanie liczb binarnych w NBS można przedstawić za pomocą zwykłego pisemnego sumowania:
| 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | 0 | 1 | ||
| + | 0 | 0 | 0 | 1 | 1 | 0 | |
| 1 | 0 | 0 | 0 | 0 | 1 | 1 |
Odejmowanie liczb w NBS
Odejmowanie liczb binarnych w systemie NBS można łatwo przeprowadzić sposobem pisemnym. Odejmuje się odpowiadające sobie bity, w razie potrzeby pożyczając bity z kolumn po lewej strony aktualnej. Pożyczane liczby mają zawsze wartości o jeden większe niż wynosi podstawa systemu, czyli w tym przypadku 10 (lub 2 w zapisie dziesiętnym; dla uproszczenia zapisu w przykładzie poniżej użyto dwójki).
Przykładowo, odejmując 6 od 19 w systemie NBS otrzyma się:
| 1 | 2 | ||||
| 1 | 0 | 0 | 1 | 1 | |
| - | 1 | 1 | 0 | ||
| 1 | 1 | 0 | 1 |
Jest to ten sam wynik, jak w przypadku odejmowania liczb w systemie dziesiętnym (19-6=13).
Mnożenie liczb w NBS
Mnożenie liczb binarnych zapisanych w NBS przeprowadza się analogicznie, do mnożenia liczb w systemie dziesiętnym. Przykładowo mnożąc 22 razy 5 otrzymuje się poprawny wynik równy 110:
| 1 | 0 | 1 | 1 | 0 | ||||
| x | 1 | 0 | 1 | |||||
| 1 | 0 | 1 | 1 | 0 | ||||
| 0 | 0 | 0 | 0 | 0 | ||||
| + | 1 | 0 | 1 | 1 | 0 | |||
| 1 | 1 | 0 | 1 | 1 | 1 | 0 |
Dzielenie liczb w NBS
Dzielenie liczb binarnych w naturalnym systemie dwójkowym można przedstawić w formie pisemnej, za pomocą operacji odejmowania i rotacji.
W tym celu należy zapisać obie liczby pod kreską, dzielną nad dzielnikiem. Dzielnik przesuwa się w lewo, aż jego najstarszy niezerowy bit zrówna się z najstarszym niezerowym bitem dzielnej.
Następnie porównuje się dzielną z dzielnikiem. Jeśli dzielna (czyli liczba zapisana wyżej) jest większa od dzielnika, to odejmuje się od niej dzielnik, a ponad kreską na ostatniej pozycji dzielnika dopisuje jedynkę. W kolejnym porównywaniu zamiast dzielnej należy używać wyniku z odejmowania.
Jeśli dzielnik jest większy od dzielnej, to nie wykonuje się odejmowania, tylko zapisuje zero nad kreską i przesuwa dzielnik (dolną liczbę) o jedną pozycję w prawo, a następnie powtarza całe porównywanie.
Jeśli dzielnika nie da się już przesunąć bardziej w prawo, to nad kreską dopisuje się zero, a aktualna różnica dzielnej i dzielnika stanowi resztę z dzielenia.
Na przykład, dzieląc pisemnie 11 przez 3 otrzyma się w wyniku 3 i resztę 2:
| 0 | 1 | 1 | ||
| 1 | 0 | 1 | 1 | |
| 1 | 1 | |||
| 1 | 0 | 1 | 1 | |
| - | 1 | 1 | ||
| 1 | 0 | 1 | ||
| - | 1 | 1 | ||
| 1 | 0 |
Po otrzymaniu reszty w dzieleniu, jest możliwe dalsze kontynuowanie tych samych operacji, otrzymując cyfry ułamkowe (podobnie jak w przypadku dzielenia pisemnego liczb dziesiętnych).
Zapis liczb w U2
Liczba binarna zapisana w systemie U2 i posiadająca n cyfr, może przyjmować wartości dodatnie i ujemne w przedziale od -2n-1 do 2n-1-1.
Skrajnie lewy bit liczby binarnej nazywany jest bitem znaku i decyduje czy liczba jest dodatnia czy ujemna (liczba jest ujemna, jeśli bit znaku równy jest 1).
Zwiększenie ilości bitów w U2
Liczby w systemie U2 można zapisywać na różnej ilości bitów, podobnie jak liczby w systemie dziesiętnym można zapisać za pomocą różnej ilości cyfr, dodając z lewej strony dodatkowe zera. W celu zwiększenia ilości bitów, na których zapisana jest liczba, należy dopisać bit z lewej strony i przypisać mu taką samą wartość jaką miał dotychczasowy bit znaku. Gwarantuje to zachowanie oryginalnej wartości liczby.
Na przykład, mając daną liczbę -7 zapisaną w kodzie U2 na 4 bitach (10012), można rozszerzyć ją do 5 bitów poprzez powielenie bitu znaku z lewej strony (110012):
10012 = -23 + 20 = -8 + 1 = -7
110012 = -24 + 23 + 20 = -16 + 8 + 1 = -7
Zmiana znaku liczby w U2
Wyznaczenie liczby przeciwnej polega na negacji wszystkich bitów w liczbie (zastąpieniu zerami jedynek, a jedynkami zer), a następnie dodaniu do otrzymanej wartości liczby 1.
Przykładowo, aby wyznaczyć liczbę 11 w kodzie U2, znając binarną wartość liczby -11 w kodzie U2 (czyli 1101012), należy w pierwszej kolejności zanegować wszystkie bity:
~110101 = 001010,
a następnie dodać do otrzymanej wartości jedynkę:
| 0 | 1 | 0 | 1 | 0 | |
| + | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 |
23 + 21 + 20 = 8 + 2 + 1 = 11
Dodawanie liczb w U2
Dodawanie liczb binarnych w U2 można przedstawić za pomocą zwykłego pisemnego sumowania, analogicznie jak w przypadku dodawania liczb w formacie NBS. Przykładowo, dodając 6 do -11 w systemie U2 otrzyma się:
| 1 | |||||||
| 1 | 1 | 0 | 1 | 0 | 1 | ||
| + | 0 | 0 | 0 | 1 | 1 | 0 | |
| 1 | 1 | 1 | 0 | 1 | 1 |
czyli -5 w systemie dziesiętnym:
-25 + 24 + 23 + 21 + 20 = -32 + 16 + 8 + 2 + 1 = -5
Wykonując operacje na liczbach binarnych, należy mieć na uwadze, aby wynik zawierał się w zakresie dla jakiego zdefiniowano aktualnie przetwarzane liczby. W przeciwnym wypadku otrzymana wartość nie zmieści się w słowie o przewidzianej ilości bitów i będzie niepoprawna.
Odejmowanie liczb w U2
Odejmowanie liczb binarnych w systemie U2 można przedstawić za pomocą zwykłego pisemnego odejmowania (tak jak w systemie NBS). Pożyczane liczby mają (również podobnie jak w NBS) wartości o jeden większe niż wynosi podstawa systemu, czyli w tym przypadku 10 (lub 2 w zapisie dziesiętnym; dla uproszczenia zapisu w przykładach poniżej użyto dwójki). Przykładowo, odejmując 6 od -11 w systemie U2 otrzyma się:
| 1 | 2 | 2 | ||||
| 1 | 1 | 0 | 1 | 0 | 1 | |
| - | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 |
czyli poprawną wartość w systemie dziesiętnym:
-25 + 23 + 22 + 21 + 20 = -32 + 8 + 4 + 2 + 1 = -17
Podobnie, aby odjąć 22 od -11 w systemie U2 należy:
| 2 | 1 | 2 | 2 | ||||
| 1 | 1 | 1 | 0 | 1 | 0 | 1 | |
| - | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 |
co w systemie dziesiętnym wynosi:
-26 + 24 + 23 + 22 + 21 + 20 = -64 + 16 + 8 + 4 + 2 + 1 = -33
Mnożenie liczb w U2
Binarne mnożenie w systemie U2 jest nieco bardziej skomplikowane niż mnożenie liczb w binarnym systemie naturalnym. Wydajnym algorytmem umożliwiającym przeprowadzenie obliczeń jest tak zwany algorytm mnożenia Bootha (ang. Booth's multiplication algorithm). W celu przemnożenia przez siebie dwóch liczb (X o długości dłX bitów i Y o długości dłY bitów) zapisanych w U2, należy najpierw wykonać następujące kroki inicjujące:
- Jeżeli wartość którejś z mnożonych liczb jest równa maksymalnej ujemnej liczbie możliwej do zapisana na ilości bitów, jaką ta liczba posiada, to przed rozpoczęciem dalszych działań należy ją rozszerzyć o jeden bit z lewej strony,
- Obliczyć odwrotność X w U2 (czyli -X),
- Zainicjować zmienną pomocniczą A o długości dłX+dłY+1 bitów: wypełnić najbardziej znaczące dłX bitów liczby A bitami z liczby X, natomiast pozostałe dłY+1 bitów wypełnić zerami (litera A nawiązuje do operacji dodawania, ang. addition, wykonywanego w dalszych krokach algorytmu),
- Zainicjować zmienną pomocniczą S o długości dłX+dłY+1 bitów: wypełnić najbardziej znaczące dłX bitów liczby S bitami z liczby -X, natomiast pozostałe dłY+1 bitów wypełnić zerami (litera S nawiązuje do operacji rotacji, ang. shifting, wykonywanej w dalszych krokach algorytmu),
- Zainicjować zmienną pomocniczą P o długości dłX+dłY+1 bitów: wypełnić najbardziej znaczące dłX bitów liczby P zerami, kolejne dłY bitów liczby P bitami z liczby Y, natomiast ostatni bit (najmniej znaczący) liczby P ustawić na zero (litera P nawiązuje do wyniku operacji mnożenia, ang. product).
Po inicjalizacji zmiennych, należy wykonać poniższe dwa kroki dłY razy:
- Jeżeli dwa ostatnie bity liczby P są równe 01, to dodać P+A (ignorując ewentualne przepełnienie) i wynik przypisać do P. W przeciwnym wypadku, jeżeli dwa ostatnie bity liczby P są równe 10, to dodać P+S (ignorując ewentualne przepełnienie) i wynik przypisać do P. W przeciwnym wypadku, jeżeli są równe 00 lub 11, to liczba P powinna zostać niezmieniona.
- Przesunąć arytmetycznie wszystkie bity otrzymanej liczby P o jedną pozycje w prawo (porzucając najmniej znaczący bit, a wartość dotychczasowego najbardziej znaczącego bitu pozostawiając niezmienioną) i przypisać wynik do P.
Po ukończeniu powyższych kroków, należy odrzucić z otrzymanej liczby P najmniej znaczący bit. Wynik, otrzymana nowa liczba P, jest iloczynem mnożenia oryginalnych liczb X i Y.
Przykład mnożenia liczb binarnych w U2
Rozważmy przebieg mnożenia liczb -8 i 3:
X = -8 = 10002
Y = 3 = 0112
W pierwszym kroku należy rozszerzyć liczbę X:
X = 11000
Następnie należy wyznaczyć wartość -X:
-X = ~11000 + 01 = 00111 + 01 = 01000
Wyznaczenie początkowych wartości liczb pomocniczych A, S i P:
A = 1 1000 0000
S = 0 1000 0000
P = 0 0000 0110
Następnie dwa kolejne kroki algorytmu powinny zostać powtórzone trzy razy (tyle wynosi długość liczby Y):
Runda 1:
P = P + S = 0 1000 0110
P >> 1 = 0 0100 0011
Runda 2:
P >> 1 = 0 0010 0001
Runda 3:
P = P + A = 1 1010 0001
P >> 1 = 1 1101 0000
Na końcu należy usunąć najmniej znaczący bit liczby P:
P = 1110 1000
Otrzymana wartość jest równa:
-27 + 26 + 25 + 23 = -128 + 64 + 32 + 8 = -24
Jest to poprawny wynik mnożenia liczb -8 i 3.