Crypto-IT

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.

Liczba binarna zapisana w systemie NBS i posiadająca n cyfr, może przyjmować wartości od 0 do 2ⁿ-1.

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 binarnych w NBS można przedstawić za pomocą zwykłego pisemnego sumowania:

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ę:

Jest to ten sam wynik, jak w przypadku odejmowania liczb w systemie dziesiętnym (19-6=13).

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:

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:

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

Liczba binarna zapisana w systemie U2 i posiadająca n cyfr, może przyjmować wartości dodatnie i ujemne w przedziale od -2^n-1 do 2^n-1-1.

Skrajnie lewy bit liczby binarnej nazywany jest bitem znaku i decyduje czy liczba jest dodania czy ujemna (liczba jest ujemna, jeśli bit znaku równy jest 1).

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 (1001₂), można rozszerzyć ją do 5 bitów poprzez powielenie bitu znaku z lewej strony (11001₂):
     1001₂ = -2³ + 2⁰ = -8 + 1 = -7
    11001₂ = -2⁴ + 2³ + 2⁰ = -16 + 8 + 1 = -7

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 110101₂), należy w pierwszej kolejności zanegować wszystkie bity:
    ~110101 = 001010,
a następnie dodać do otrzymanej wartości jedynkę:

    2³ + 2¹ + 2⁰ = 8 + 2 + 1 = 11

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ę:

czyli -5 w systemie dziesiętnym:
    -2⁵ + 2⁴ + 2³ + 2¹ + 2⁰ = -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 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ę:

czyli poprawą wartość w systemie dziesiętnym:
    -2⁵ + 2³ + 2² + 2¹ + 2⁰ = -32 + 8 + 4 + 2 + 1 = -17

Podobnie, aby odjąć 22 od -11 w systemie U2 należy:

co w systemie dziesiętnym wynosi:
    -2⁶ + 2⁴ + 2³ + 2² + 2¹ + 2⁰ = -64 + 16 + 8 + 4 + 2 + 1 = -33

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 Booth'a (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:

1. 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,
2. Obliczyć odwrotność X w U2 (czyli -X),
3. 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),
4. 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),
5. 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:

1. 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.
2. 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.

Rozważmy przebieg mnożenia liczb -8 i 3:

    X = -8 = 1000₂
    Y = 3 = 011₂

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:
    -2⁷ + 2⁶ + 2⁵ + 2³ = -128 + 64 + 32 + 8 = -24

Jest to poprawny wynik mnożenia liczb -8 i 3.