Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

obrazek

Autor artykułu: mgr Jerzy Wałaszek

©2019 mgr Jerzy Wałaszek
I LO w Tarnowie

obrazek

Kody binarne

Liczby naturalne

SPIS TREŚCI
Podrozdziały

Konwersje

Kody binarne są bardzo elastyczne. Komputery potrafią przetwarzać każdą informację, jeśli tylko zostanie ona odwzorowana w kod binarny (obrazy, filmy, dźwięk, dane z czujników, itp.). Liczby naturalne (ang. natural numbers) pojawiły się jako pierwsze w naszej historii wiele tysiącleci temu. Są to liczby: 1, 2, 3, ... Tworzą one ciąg nieskończony, co oznacza, iż nie istnieje największa liczba naturalna. Dowód jest banalnie prosty: dwie kolejne liczby naturalne n i m różnią się od siebie o 1:

Załóżmy, że istnieje największa liczba naturalna nn. Tworzymy z niej liczbę mm:

Liczba mm jest również liczbą naturalną, ponieważ różni się ona od nn o 1:

Ponieważ mm jest większe o 1 od nn, liczba nn nie może być największą liczbą naturalną, a to przeczy założeniu. Prawdziwe jest zatem twierdzenie odwrotne: nie istnieje największa liczba naturalna.

Tak jest w matematyce. W informatyce niekoniecznie jest to prawdą. Na początek określimy tzw. naturalny kod binarny (ang. NBC, natural binary code). Konstrukcję kodu przeprowadzimy krok po kroku na przykładzie bajtu, aby wszystko było zrozumiałe. Jeśli jest to dla ciebie zbyt proste, przejdź do dalszej części rozdziału.

Bajt jest grupą 8 bitów, z których każdy może przyjmować stan 0 lub 1. Zapiszmy bitowo kilka bajtów:

00000000
11111111
10000001
00011000
11101001

W takiej postaci trudno nam prowadzić dalsze rozważania. Dlatego zapiszmy symbolicznie każdy bit za pomocą literki b (b – bit):

bbbbbbbb

Dalej, aby rozróżniać poszczególne bity w bajcie, ponumerujemy je następująco:

b7b6b5b4b3b2b1b0

Numery bitów nazwijmy numerami pozycji i oznaczmy symbolicznie literką p. Bit bp oznacza bit znajdujący się na p-tej pozycji w bajcie, gdzie p = 0,1,2,...,7.

Skojarzmy z każdą pozycją p wartość równą 2p, którą będziemy nazywać wagą pozycji. Umówmy się, że bit na pozycji p-tej ma wartość równą iloczynowi bp x 2p. Jeśli bit bp ma stan 0, to wartość ta wynosi 0. Jeśli bit bp ma stan 1, to wartość bitu wynosi 2p. Wartość całego kodu w bajcie jest sumą tych iloczynów. Dla przykładu weźmy kod 11011101. Policzmy jego wartość:

Waga: 27 26 25 24 23 22 21 20
Bit: 1 1 0 1 1 1 0 1
Pozycja: 7 6 5 4 3 2 1 0

Policzmy wartości wag pozycji:

Waga: 128 64 32 16 8 4 2 1
Bit: 1 1 0 1 1 1 0 1

Wymnóżmy wartości wag pozycji przez bity kodu:

Waga: 128 64 32 16 8 4 2 1
Wartość: 128 64 0 16 8 4 0 1

Zsumujmy wartości tych iloczynów:

128 + 64 + 16 + 8 + 4 + 5 = 221

Zatem:

11011101(NBC) = 221

Co uzyskaliśmy do tej pory? Potrafimy obliczyć wartość dowolnego kodu 8-bitowego. Zwróć uwagę na pewne prawidłowości, które warto zapamiętać:

  1. Waga ostatniego bitu wynosi 1.
  2. Waga bitu na pozycji p+1 jest dwukrotnie większa od wagi na pozycji p.
  3. Kolejne wagi pozycji tworzą ciąg kolejnych potęg liczby 2: 1 (20), 2 (21), 4 (22), ..., 64 (26), 128 (27).
  4. Ponieważ bit może mieć wartość 0 lub 1, to jego iloczyn przez wagę pozycji, na której stoi, jest równy 0 lub jest równy wadze tej pozycji.

Wynika z tego prosty algorytm obliczania wartości dowolnego kodu NBC:

  1. Wyznacz wagi pozycji bitów
  2. Zsumuj wagi pozycji, na których bity mają stan 1, pomiń w sumie wagi pozycji, na których bity mają stan 0.

Bitów może być dowolnie wiele.

Dla przykładu policzmy wartość kodu 111010110111. Najpierw wyznaczamy wagi pozycji, poczynając od ostatniej:

Waga:                       1
Bit: 1 1 1 0 1 0 1 1 0 1 1 1

Kolejne wagi otrzymujemy mnożąc poprzednią przez 2 (nie musisz w ten sposób pamiętać wartości tych wag):

Waga: 2048 1024 512 256 128 64 32 16 8 4 2 1
Bit: 1 1 1 0 1 0 1 1 0 1 1 1

Sumujemy wagi pozycji, na których stoją bity 1 (można to robić od końca lub od początku kodu):

2048 + 1024 + 512 + 128 + 32 + 16 + 4 + 2 + 1 = 3767

Warto wykonać samodzielnie kilka takich obliczeń. Można też posłużyć się kalkulatorem, jeśli posiada funkcje programisty (np. kalkulator z Windows):

obrazek

Zastanówmy się, ile różnych liczb można zakodować przy pomocy n-bitowego kodu NBC. Liczba ta jest równa liczbie kombinacji bitów. Każdy bit może przyjmować 2 kombinacje, zatem dla n bitów mamy:

Wynika z tego, iż bajt zawierający 8 bitów potrafi zakodować 28 = 256 różnych liczb. Ponieważ są to kolejne liczby naturalne od 0 w górę, to otrzymujemy zakres od 0 do 255 (kolejna własność: największą n-bitową liczbą w kodzie NBC jest zawsze liczba o wartości 2n - 1).

n-bitowa liczba NBC posiada zakres od 0 do 2n - 1. Oto kilka przykładowych zakresów:

Liczba bitów Zakres
1 0 ... 1
2 0 ... 3
4 0 ... 15
8 0 ... 255
16 0 ... 65535
32 0 ... 4294967295
64 0 ... 18446744073709551615

Kolejne wyrazy kodu NBC budujemy w bardzo prosty sposób. Pokażemy to na przykładzie kodu 4-bitowego. Dla większej liczby bitów jest podobnie. 4 bity kodują 16 liczb naturalnych od 0 do 15. Wypełnimy bitami tego kodu tabelkę:

b3 b2 b1 b0 Wartość
        0
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15

Zaczynamy od najmłodszego bitu b0. Tutaj na przemian umieszczamy 0 i 1:

b3 b2 b1 b0 Wartość
      0 0
      1 1
      0 2
      1 3
      0 4
      1 5
      0 6
      1 7
      0 8
      1 9
      0 10
      1 11
      0 12
      1 13
      0 14
      1 15

Teraz bit b1. Ten zmienia się co dwie liczby. Zaczynamy od 0:

b3 b2 b1 b0 Wartość
    0 0 0
    0 1 1
    1 0 2
    1 1 3
    0 0 4
    0 1 5
    1 0 6
    1 1 7
    0 0 8
    0 1 9
    1 0 10
    1 1 11
    0 0 12
    0 1 13
    1 0 14
    1 1 15

Bit b2 zmienia się co 4 liczby:

b3 b2 b1 b0 Wartość
  0 0 0 0
  0 0 1 1
  0 1 0 2
  0 1 1 3
  1 0 0 4
  1 0 1 5
  1 1 0 6
  1 1 1 7
  0 0 0 8
  0 0 1 9
  0 1 0 10
  0 1 1 11
  1 0 0 12
  1 0 1 13
  1 1 0 14
  1 1 1 15

I ostatni bit b3 zmienia się co 8 liczb (zauważyłeś już prawidłowość?):

b3 b2 b1 b0 Wartość
0 0 0 0 0
0 0 0 1 1
0 0 1 0 2
0 0 1 1 3
0 1 0 0 4
0 1 0 1 5
0 1 1 0 6
0 1 1 1 7
1 0 0 0 8
1 0 0 1 9
1 0 1 0 10
1 0 1 1 11
1 1 0 0 12
1 1 0 1 13
1 1 1 0 14
1 1 1 1 15

Jak widzisz, nie są potrzebne żadne rachunki.

W języku C++ liczby całkowite reprezentowane są typami danych:

Nazwa typu Liczba bajtów Liczba bitów Zakres
unsigned char 1 8 0...255
unsigned short int 2 16 0...65535
unsigned int 4 32 0 ... 4294967295
unsigned long long int 8 64 0 ... 18446744073709551615

Dla pewności skompiluj i uruchom poniższy program:

Przykładowy program w języku C++
// Sprawdzenie typów danych NBC
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    unsigned char cv;
    unsigned short int sv;
    unsigned int iv;
    unsigned long long int lv;

    setlocale(LC_ALL,"");

    lv = 0; lv--;      // W lv wartość maksymalna
    cv = sv = iv = lv; // We wszystkich zmiennych wartości maksymalne

    // Wyniki

     cout << "Liczby naturalne w typach danych języka C++" << endl
          << "-------------------------------------------" << endl << endl;
     cout << "Nazwa typu            Bajty Bity Zakres" << endl;
     cout << left << setw(22) << "unsigned char" << right
          << setw(5)  << sizeof(cv)
          << setw(5)  << sizeof(cv) * 8 << " 0 ... "
          << (int)cv << endl;
     cout << left << setw(22) << "unsigned short int" << right
          << setw(5)  << sizeof(sv)
          << setw(5)  << sizeof(sv) * 8 << " 0 ... "
          << sv << endl;
     cout << left << setw(22) << "unsigned int" << right
          << setw(5)  << sizeof(iv)
          << setw(5)  << sizeof(iv) * 8 << " 0 ... "
          << iv << endl;
     cout << left << setw(22) << "unsigned long long int" << right
          << setw(5)  << sizeof(lv)
          << setw(5)  << sizeof(lv) * 8 << " 0 ... "
          << lv << endl;
    return 0;
}
Wynik
Liczby naturalne w typach danych języka C++
-------------------------------------------

Nazwa typu         Bajty Bity Zakres
unsigned char          1    8 0 ... 255
unsigned short int     2   16 0 ... 65535
unsigned int           4   32 0 ... 4294967295
unsigned long long int 8   64 0 ... 18446744073709551615

Jak przekształcić liczbę dziesiętną w odpowiadającą jej liczbę NBC? Istnieje tutaj wiele algorytmów, ale nie będziemy się ich uczyć, ponieważ nie jest to celem metod numerycznych. Jeśli koniecznie musisz przekształcać takie liczby, skorzystaj z kalkulatora programisty. Zainteresowanych głębiej tym tematem odsyłam do artykułu "Binarne kodowanie liczb". Podam bardzo prosty sposób, który być może nie jest najefektywniejszy, lecz łatwo go zrozumieć.

Załóżmy, że chcemy przekształcić liczbę 91 na liczbę NBC 8-bitową. Budujemy tabelkę na poszczególne bity kodu NBC. Ponad miejscami na cyfry zapisujemy wagi pozycji:

Waga: 128 64 32 16 8 4 2 1
Bit: ? ? ? ? ? ? ? ?

Zaczynamy od najstarszego bitu. Bit ten musi wynosić 0, ponieważ waga 128 > 91:
Waga: 128 64 32 16 8 4 2 1
Bit: 0 ? ? ? ? ? ? ?

Przechodzimy do bitu o wadze 64. Ten bit będzie miał stan 1, ponieważ 64 < 91:

Waga: 128 64 32 16 8 4 2 1
Bit: 0 1 ? ? ? ? ? ?

Ponieważ mamy już wartość 64, to musimy ją odjąć od 91, aby znaleźć kolejne bity:

91 - 64 = 27

To nowa wartość, którą w podobny sposób kodujemy na pozostałych bitach. Waga 32 nie wchodzi do kodu NBC, ponieważ 32 > 27:

Waga: 128 64 32 16 8 4 2 1
Bit: 0 1 0 ? ? ? ? ?

Przechodzimy do wagi 16, ponieważ 16 < 27, waga ta wchodzi do kodu NBC:

Waga: 128 64 32 16 8 4 2 1
Bit: 0 1 0 1 ? ? ? ?

Wagę 16 odejmujemy od liczby 27: 27 - 16 = 11. Otrzymaliśmy nową wartość, kontynuujemy z wagą 8, ponieważ 8 < 11, waga 8 wchodzi do kodu NBC:

Waga: 128 64 32 16 8 4 2 1
Bit: 0 1 0 1 1 ? ? ?

Odejmujemy wagę 8 od 11: 11 - 8 = 3 i otrzymujemy nową liczbę 3. Waga 4 nie wchodzi do kodu NBC, ponieważ 4 > 3:

Waga: 128 64 32 16 8 4 2 1
Bit: 0 1 0 1 1 0 ? ?

Waga 2 wchodzi do kodu NBC, ponieważ 2 < 3:

Waga: 128 64 32 16 8 4 2 1
Bit: 0 1 0 1 1 0 1 ?

Odejmujemy: 3 - 2 = 1. Ostatnia waga wchodzi do kodu NBC:

Waga: 128 64 32 16 8 4 2 1
Bit: 0 1 0 1 1 0 1 1

Mamy wszystkie bity, ponieważ 1 - 1 = 0. Ponieważ wagi odejmowaliśmy od konwertowanej wartości aż do otrzymania zera, to suma tych wag da nam liczbę wyjściową:

1 + 2 + 8 + 16 + 64 = 91

Zatem:

91 = 01011011(NBC)

Wypróbuj poniższy program. Przekształca on wprowadzoną liczbę dziesiętną w liczbę binarną w kodzie NBC. Zera wiodące (bity o stanie 0 na początku liczby) są pomijane w wyniku.

Przykładowy program w języku C++
// Przeliczanie na NBC
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//------------------------------

#include <iostream>

using namespace std;

int main()
{
    unsigned long long int m,v;

    setlocale(LC_ALL,"");
    cout << "Przeliczanie liczb naturalnych na liczby binarne w kodzie NBC" << endl
         << "-------------------------------------------------------------" << endl << endl;
    cout << "Podaj liczbę naturalną lub zero : ";
    cin  >> v; // Odczytujemy liczbę do konwersji

    // Komputer przechowuje liczbę w pamięci w kodzie NBC.
    // Nic nie musimy przeliczać. Zrobi to komputer za nas.

    cout << v << " = "; 

    if(v)
    {
      // Szukamy pozycji pierwszego bitu 1
      for(m = 0x1000000000000000L; !(v & m); m >>= 1);
      // Począwszy od tej pozycji do pozycji 0 wyświetlamy wszystkie bity liczby
      while(m)
      {
        cout << ((v & m) > 0);
        m >>= 1;
      }
    }
    else cout << 0;

    cout << "(NBC)" << endl;

    return 0;
}
Wynik
Przeliczanie liczb naturalnych na liczby binarne w kodzie NBC
-------------------------------------------------------------

Podaj liczbę naturalną lub zero : 2019
2019 = 11111100011(NBC)
Na początek:  podrozdziału   strony 

Operacje arytmetyczne

Operacje dodawania i mnożenia dla liczb naturalnych zapisanych w kodzie NBC dają dobre wyniki pod warunkiem, iż wyniki te mieszczą się w zakresie liczb danego typu. Na przykład liczby 8-bitowe NBC mają zakres od 0 do 255. Zatem dodawanie:

100 + 100 = 200

da poprawny wynik, ponieważ 200 < 255. Jednak dodawanie:

100 + 200 = 300

nie da poprawnego wyniku, ponieważ liczba 300 jest większa od maksymalnej liczby, którą można przedstawić kodem 8-bitowym. Co dostaniemy w wyniku? Otrzymamy wynik obcięty do 8 młodszych bitów:

300 = 100101100(NBC) = 00101100(NBC8) = 44

Bit zaznaczony na czerwono jest 9-tym bitem kodu i zostanie pominięty w wyniku. Dlatego otrzymasz wartość 44, a nie spodziewane 300. Taka sytuacja nazywa się nadmiarem (ang. overflow). Nadmiar oznacza przekroczenie dopuszczalnego zakresu i zawsze prowadzi do błędu. Wykonując obliczenia na liczbach naturalnych powinieneś sprawdzać, czy nie doprowadzą one do nadmiaru.

W języku C++ nadmiar możemy wykryć, jeśli obliczenia wykonujemy w typie wyższym (np. unsigned int), a wyniki przekształcamy na typ niższy (np. unsigned char).

Poniższy program odczytuje dwie liczby 8-bitowe, a następnie dodaje je i wyświetla wynik, sprawdzając, czy nie pojawił się nadmiar.

Przykładowy program w języku C++
// Dodawanie dwóch liczb 8-bitowych NBC
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//------------------------------

#include <iostream>

using namespace std;

int main()
{
    unsigned int a,b,ir;
    unsigned char cr;

    setlocale(LC_ALL,"");

    cout << "Dodawanie 8-bitowych liczb naturalnych" << endl
         << "--------------------------------------" << endl << endl;

    // Liczby wczytujemy jako 32-bitowe

    cout << "a = "; cin >> a;
    cout << "b = "; cin >> b;

    // Wczytane liczby obcinamy do 8 bitów

    a &= 0x000000ff;
    b &= 0x000000ff;

    // Wykonujemy dodawanie

    cr = ir = a + b;

    // Wyświetlamy wyniki

    cout << a << " + " << b << " = " << (unsigned int)cr;

    // Sprawdzamy, czy wynik jest poprawny, czy z nadmiarem

    if(ir == cr) cout << " : Wynik poprawny";
    else         cout << " : Wynik błędny, NADMIAR!!!";

    cout << endl << endl;

    return 0;
}

Przykładowe wyniki (zakres 8-bitowych liczb NBC wynosi od 0 do 255):

Dodawanie 8-bitowych liczb naturalnych
--------------------------------------

a = 100
b = 100
100 + 100 = 200 : Wynik poprawny
 
Dodawanie 8-bitowych liczb naturalnych
--------------------------------------

a = 100
b = 200
100 + 200 = 44 : Wynik błędny, NADMIAR!!!

Innym sposobem wykrycia nadmiaru jest sprawdzenie, czy wynik dodawania jest mniejszy od większej z dodawanych liczb (nie trzeba wtedy stosować do obliczeń większego typu). Np. dla liczb 8-bitowych NBC (zakres 0...255):

100 + 156 = 0 (100+156=256 = 100000000(NBC), co po obcięciu od 8 bitów daje 00000000(NBC)).
Przykładowy program w języku C++
// Dodawanie dwóch liczb 8-bitowych NBC
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//------------------------------

#include <iostream>

using namespace std;

int main()
{
    unsigned int x,y;      // 32-bitowe zmienne pomocnicze
    unsigned char a,b,m,r; // Właściwe zmienne 8-bitowe

    setlocale(LC_ALL,"");

    cout << "Dodawanie 8-bitowych liczb naturalnych" << endl
         << "--------------------------------------" << endl << endl;

    // Liczby wczytujemy jako 32-bitowe, gdyż inaczej dane wejściowe
    // zostałyby zinterpretowane jako znaki, a nie liczby.

    cout << "a = "; cin >> x;
    cout << "b = "; cin >> y;

    // Wczytane liczby zapamiętujemy w zmiennych 8-bitowych NBC

    a = x; b = y;

    // Zapamiętujemy większą z liczb a,b

    m = a;
    if(b > a) m = b;

    // Wykonujemy dodawanie

    r = a + b;

    // Wyświetlamy wyniki

    cout << (unsigned int)a << " + " << (unsigned int)b << " = " << (unsigned int)r;

    // Sprawdzamy, czy wynik jest poprawny, czy z nadmiarem

    if(r >= m) cout << " : Wynik poprawny";
    else       cout << " : Wynik błędny, NADMIAR!!!";

    cout << endl << endl;

    return 0;
}

Przykładowe wyniki (zakres 8-bitowych liczb NBC wynosi od 0 do 255):

Dodawanie 8-bitowych liczb naturalnych
--------------------------------------

a = 100
b = 100
100 + 100 = 200 : Wynik poprawny
 
Dodawanie 8-bitowych liczb naturalnych
--------------------------------------

a = 100
b = 200
100 + 200 = 44 : Wynik błędny, NADMIAR!!!

Podobnie jest z mnożeniem. Jeśli wynik mnożenia wykracza poza zakres, mamy do czynienia z nadmiarem.

Przykładowy program w języku C++
// Mnożenie dwóch liczb 16-bitowych NBC
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-------------------------------------

#include <iostream>

using namespace std;

int main()
{
    unsigned long long int a,b,lr;
    unsigned short int sr;

    setlocale(LC_ALL,"");

    cout << "Mnożenie 16-bitowych liczb naturalnych" << endl
         << "--------------------------------------" << endl << endl;
    // Liczby wczytujemy jako 32-bitowe

    cout << "a = "; cin >> a;
    cout << "b = "; cin >> b;

    // Wczytane liczby obcinamy do 16 bitów

    a &= 0x000000000000ffffL;
    b &= 0x000000000000ffffL;

    // Wykonujemy mnożenie

    sr = lr = a * b;

    // Wyświetlamy wyniki

    cout << a << " x " << b << " = " << sr;

    if(lr == sr) cout << " : Wynik poprawny";
    else         cout << " : Wynik błędny, NADMIAR!!!";

    cout << endl << endl;

    return 0;
}

Przykładowe wyniki (zakres 16-bitowych liczb NBC wynosi od 0 do 65535):

Mnożenie 16-bitowych liczb naturalnych
--------------------------------------

a = 100
b = 500
100 x 500 = 50000 : Wynik poprawny
 
Mnożenie 16-bitowych liczb naturalnych
--------------------------------------

a = 100
b = 1000
100 x 1000 = 34464 : Wynik błędny, NADMIAR!!!

Dzielenie liczb naturalnych NBC zdefiniowane jest jako dzielenie całkowite, tzn. wynik określa ile razy dzielnik mieści się w dzielnej. Na przykład:

7 / 2 = 3

Ponieważ 2 mieści się 3 razy w 7 i zostaje reszta 1. Wartość reszty z dzielenia daje nam operacja %:

7 % 2 = 1

Wynik dzielenia jest zawsze poprawny pod warunkiem, że dzielnik jest różny od zera.

Przykładowy program w języku C++
// Dzielenie i reszta z dzielenia liczb NBC
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

#include <iostream>

using namespace std;

int main()
{
    unsigned int a,b;

    setlocale(LC_ALL,"");

    cout << "Dzielenie i reszta z dzielenia liczb NBC" << endl
         << "----------------------------------------" << endl << endl;
    // Wczytujemy liczby do dzielenia

    cout << "a = "; cin >> a;
    cout << "b = "; cin >> b;


    // Sprawdzamy, czy dzielnik jest zerem

    if(!b) cout << "DZIELENIE PRZEZ ZERO !!!";
    else   cout << a << " / " << b << " = " << a / b << endl
                << a << " % " << b << " = " << a % b;
    cout << endl << endl;

    return 0;
}
Wynik
Dzielenie i reszta z dzielenia liczb NBC
----------------------------------------

a = 7
b = 2
7 / 2 = 3
7 % 2 = 1
 
Dzielenie i reszta z dzielenia liczb NBC
----------------------------------------

a = 7
b = 0
DZIELENIE PRZEZ ZERO !!!

Wykonując działania na liczbach NBC należy zwracać uwagę na ich prawidłową kolejność. Na przykład chcesz policzyć 2/3 z 9:

2 / 3 * 9 = 0

Dlaczego tak się dzieje? Operacje dzielenia i mnożenia mają ten sam priorytet, a to oznacza, iż zostaną wykonane w kolejności zapisu od strony lewej do prawej. Zatem komputer najpierw wykona dzielenie całkowite:

2 / 3 = 0

Następnie wynik tego dzielenia jest mnożony przez 9:

0 * 9 = 0

I wynikiem jest zero. Jeśli chcesz otrzymać 2/3 z 9, to należy zmienić kolejność obliczeń:

9 * 2 / 3 = 6

Teraz komputer najpierw wykona mnożenie:

9 * 2 = 18

A następnie ten wynik podzieli przez 3:

18 / 3 = 6
Jeśli wykonujesz mnożenie i dzielenie liczb naturalnych NBC, dzielenie umieszczaj na końcu wyrażenia.

Przy odejmowaniu liczb NBC należy sprawdzać, czy odjemnik nie jest większy od odjemnej, ponieważ wtedy wynik będzie ujemny, czyli poniżej dolnej granicy zakresu. Taką sytuację nazywamy niedomiarem (ang. underflow). Niedomiar daje zawsze błędne wyniki, ponieważ kod NBC nie potrafi reprezentować liczb ujemnych.

Przykładowy program wykonuje odejmowanie i sprawdza warunek niedomiaru.

Przykładowy program w języku C++
// Odejmowanie liczb naturalnych NBC
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

#include <iostream>

using namespace std;

int main()
{
    unsigned int a,b;

    setlocale(LC_ALL,"");

    cout << "Odejmowanie 32-bitowych liczb naturalnych w kodzie NBC" << endl
         << "------------------------------------------------------" << endl << endl;
    // Odczytujemy dane wejściowe

    cout << "a = "; cin >> a;
    cout << "b = "; cin >> b;

    // Wykonujemy odejmowanie

    cout << a << " - " << b << " = " << a - b;

    // Sprawdzamy niedomiar

    if(a >= b) cout << " : Wynik prawidłowy";
    else       cout << " : Wynik błędny, NIEDOMIAR !!!";

    cout << endl << endl;

    return 0;
}
Wynik
Odejmowanie 32-bitowych liczb naturalnych w kodzie NBC
------------------------------------------------------

a = 25
b = 12
25 - 12 = 13 : Wynik prawidłowy
 
Odejmowanie 32-bitowych liczb naturalnych w kodzie NBC
------------------------------------------------------

a = 25
b = 26
25 - 26 = 4294967295 : Wynik błędny, NIEDOMIAR !!!

Przy mnożeniu dużych liczb NBC (np. 64-bitowych) możesz mieć kłopoty przy sprawdzaniu poprawności wyniku, ponieważ operacji tej nie da się wykonać w większym typie danych (bez użycia specjalnej biblioteki arytmetycznej dużych liczb). W takim przypadku poprawność otrzymanego wyniku sprawdza się za pomocą dzielenia całkowitego:

Jeśli (b > 0) i (r = a x b), to (a = r / b)
Jeśli (b = 0), to (r = 0) i wynik jest zawsze poprawny

Poniższy program mnoży dwie 64-bitowe liczby NBC i sprawdza poprawność wyniku.

Przykładowy program w języku C++
// Mnożenie liczb naturalnych NBC
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

#include <iostream>

using namespace std;

int main()
{
    unsigned long long int a,b,r;

    setlocale(LC_ALL,"");

    cout << "Mnożenie 64-bitowych liczb naturalnych w kodzie NBC" << endl
         << "---------------------------------------------------" << endl << endl;
    // Odczytujemy dane wejściowe

    cout << "a = "; cin >> a;
    cout << "b = "; cin >> b;

    // Wykonujemy mnożenie

    r = a * b;

    // Wypisujemy wynik

    cout << a << " x " << b << " = " << r;

    // Sprawdzamy nadmiar

    if (b && (a != r / b)) cout << " Wynik błędny, NADMIAR !!!";
    else                   cout << " Wynik prawidłowy";

    cout << endl << endl;

    return 0;
}
Wynik
Mnożenie 64-bitowych liczb naturalnych w kodzie NBC
---------------------------------------------------

a = 1999999999
b = 1999999999
1999999999 x 1999999999 = 3999999996000000001 Wynik prawidłowy
 
Mnożenie 64-bitowych liczb naturalnych w kodzie NBC
---------------------------------------------------

a = 9999999999
b = 9999999999
9999999999 x 9999999999 = 7766279611452241921 Wynik błędny, NADMIAR !!!
Na początek:  podrozdziału   strony 

Kwadratowy pierwiastek całkowity

Kwadratowy pierwiastek całkowity (ang. integer square root) z liczby naturalnej n jest największą liczbą naturalną m, której kwadrat jest mniejszy lub równy n. Pierwiastek całkowity będziemy oznaczać symbolem [√n].

W celu redukcji obliczeń przyjmijmy:

Istnieje kilka metod rozwiązania tego problemu. Najprostsza polega na sprawdzaniu kwadratów kolejnych liczb naturalnych 1,2,3... aż do momentu, gdy kwadrat będzie większy od n. W takim przypadku za [√n] przyjmujemy ostatnio sprawdzaną liczbę pomniejszoną o 1.

Przykładowy program:

Przykładowy program w języku C++
// Kwadratowy pierwiastek całkowity
// Metoda 1
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

#include <iostream>

using namespace std;

int main()
{
    unsigned int n, i, isqr;

    setlocale(LC_ALL,"");

    cout << "Obliczanie wartości kwadratowego pierwiastka całkowitego" << endl
         << "--------------------------------------------------------" << endl << endl;

    // Odczytujemy liczbę, której pierwiastek całkowity ma zostać obliczony

    cout << "Liczba      = "; cin >> n;
    if(n < 2) isqr = n; // Pierwiastki z 0 i z 1 są równe odpowiednio 0 i 1
    else
    {
        for(i = 2; i * i <= n; i++);
        isqr = i - 1;
    }
    cout << "Pierwiastek = " << isqr << endl
         << "Błąd        = " << n - isqr * isqr << endl << endl;

    return 0;
}
Wynik
Obliczanie wartości kwadratowego pierwiastka całkowitego
--------------------------------------------------------

Liczba      = 1
Pierwiastek = 1
Błąd        = 0
 
Obliczanie wartości kwadratowego pierwiastka całkowitego
--------------------------------------------------------

Liczba      = 8976976
Pierwiastek = 2996
Błąd        = 960

Kolejny program wykorzystuje tę samą metodę. Usprawnienie polega na wyliczaniu kolejnych kwadratów nie poprzez mnożenie, lecz poprzez dodawanie, które jest szybsze od mnożenia.

Jeśli mamy kwadrat liczby n, to kwadrat następnej liczby wynosi:

Binarnie mnożenie przez 2 wykonujemy za pomocą przesunięcia bitów o 1 pozycję w lewo:

0110(NBC) =   6
1100(NBC) = 12

W języku C++ wykonujemy tę operację operatorem bitowym <<. Przesunięcie bitów wykonywane jest szybko, ponieważ dla mikroprocesora jest to bardzo prosta operacja.

Program po modyfikacji wygląda następująco:

Przykładowy program w języku C++
// Kwadratowy pierwiastek całkowity
// Metoda 2
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

#include <iostream>

using namespace std;

int main()
{
    unsigned int n, i, n2;

    setlocale(LC_ALL,"");

    cout << "Obliczanie wartości kwadratowego pierwiastka całkowitego" << endl
         << "--------------------------------------------------------" << endl << endl;

    // Odczytujemy liczbę, której pierwiastek całkowity ma zostać obliczony

    cout << "Liczba      = "; cin >> n;
    if(n < 2) i = n; // Pierwiastki 0 i 1 są równe odpowiednio 0 i 1
    else
    {
        n2 = 1; // Pierwszy kwadrat
        for(i = 1; (n2 += 1 + (i << 1) ) <= n; i++);
    }
    cout << "Pierwiastek = " << i << endl
         << "Błąd        = " << n - i * i << endl << endl;

    return 0;
}
Wynik
Obliczanie wartości kwadratowego pierwiastka całkowitego
--------------------------------------------------------

Liczba      = 0
Pierwiastek = 0
Błąd        = 0
 
Obliczanie wartości kwadratowego pierwiastka całkowitego
--------------------------------------------------------

Liczba      = 9999
Pierwiastek = 99
Błąd        = 198

W powyższych programach wyliczenie pierwiastka wymaga tyle obiegów pętli, ile wynosi wartość pierwiastka. Zatem czas wykonania będzie proporcjonalny do pierwiastka z n. W informatyce taką własność nazywamy czasową złożonością obliczeniową (ang. time computational complexity) i oznaczamy symbolem O(√n) (czytaj "omikron pierwiastek z n"). Istnieją dużo szybsze algorytmy, które obliczają wartość całkowitego pierwiastka kwadratowego. Jedną z takich metod jest metoda babilońska:

Pracujemy z trzema zmiennymi, oznaczmy je n, x i y. Zmienna n przechowuje wartość liczby, której pierwiastek obliczamy. Zmienna x jest kolejnym przybliżeniem pierwiastka. Zmienna y jest zmienną pomocniczą, która służy do sprawdzenia, czy x osiągnęło pożądaną dokładność.

Algorytm obliczania całkowitego pierwiastka kwadratowego

Dane wejściowe:

n liczba, której pierwiastek należy obliczyć, n N

Dane wyjściowe

x całkowity pierwiastek z n, x N

Zmienne pomocnicze

y do sprawdzenia dokładności x, y N

Lista kroków

K01: xn inicjujemy zmienne
K02: y ← 1  
K03: Dopóki x > y, wykonuj kroki K4...K5 pętla obliczająca pierwiastek
K04:     wyliczamy przybliżenie pierwiastka
K05:     sprawdzamy przybliżenie
K06: Zakończ  

W algorytmie występują dwa dzielenia w pętli. Dzielenie przez 2 możemy zastąpić dużo szybszym przesunięciem bitów o 1 pozycję w prawo:

1100(NBC) = 12
0110(NBC) =   6

Operację przesunięcia bitów w języku C++ wykonujemy za pomocą operatora bitowego >>.

Przykładowy program

Przykładowy program w języku C++
// Kwadratowy pierwiastek całkowity
// Metoda 3
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

#include <iostream>

using namespace std;

int main()
{
    unsigned int n,x,y,i;

    setlocale(LC_ALL,"");

    cout << "Obliczanie wartości kwadratowego pierwiastka całkowitego" << endl
         << "--------------------------------------------------------" << endl << endl;

    // Odczytujemy liczbę, której pierwiastek całkowity ma zostać obliczony

    cout << "Liczba      = "; cin >> n;

    i = 0;
    x = n;
    y = 1;
    while(x > y) // Sprawdzamy, czy x osiągnęło pożądaną dokładność
    {            // Jeśli nie, to wyliczamy kolejne przybliżenie pierwiastka
       x = (x + y) >> 1; // Średnia arytmetyczna
       y = n / x;
       i++;      // Licznik obiegów
    }
    cout << "Pierwiastek = " << x << endl
         << "Błąd        = " << n - x * x << endl
         << "Obiegi      = " << i << endl;

    return 0;
}
Wynik
Obliczanie wartości kwadratowego pierwiastka całkowitego
--------------------------------------------------------

Liczba      = 9
Pierwiastek = 3
Błąd        = 0
Obiegi      = 2
 
Obliczanie wartości kwadratowego pierwiastka całkowitego
--------------------------------------------------------

Liczba      = 9999
Pierwiastek = 99
Błąd        = 198
Obiegi      = 10

W programie został dodany licznik obiegów pętli wyznaczającej kolejne przybliżenia pierwiastka. Czas obliczeń jest zbieżny do logarytmu z n, co zapisujemy jako O(log n). Złożoność logarytmiczna jest dużo korzystniejsza od złożoności pierwiastkowej.

Na początek:  podrozdziału   strony 

Logarytm całkowity o podstawie 2

Logarytm o podstawie a z liczby x jest to wykładnik potęgowy y, do którego należy podnieś podstawę a, aby otrzymać x. Zapisujemy to następująco:

Na przykład logarytm przy podstawie 3 z liczby 9 jest równy 2, ponieważ 32 = 9.

Logarytm całkowity jest zawsze liczbą całkowitą. Jest to największy całkowity wykładnik, dla którego potęga podstawy o tym wykładniku jest niewiększa od liczby logarytmowanej. Z definicji tej wynika, iż logarytm ten ma zawsze wykładnik największej potęgi 2, która nie jest większa od liczby logarytmowanej. Jeśli rozważymy bitowo kod NBC, to okaże się, że największą potęgą 2 o pożądanej wartości jest waga najstarszego bitu równego 1 w kodzie NBC tej liczby:

    5 = 101NBC = 22 + 20, stąd [log25] = 2
    7 = 111NBC = 22 + 21 + 20, stąd [log27] = 2
    9 = 1001NBC = 23 + 20, stąd [log29] = 3
 
15 = 1111NBC = 23 + 22 + 21 + 20, stąd [log215] = 3
 
17 = 10001NBC = 24 + 20, stąd [log217] = 4
131 = 10000011NBC = 27 + 21 + 20, stąd [log2131] = 7

Wartość tej potęgi jest równa 2p, gdzie p jest numerem pozycji najstarszego bitu. Wynika stąd prosty algorytm wyznaczania logarytmu całkowitego o podstawie 2 dla liczby naturalnej x (zero nie jest liczbą naturalną):

  1. Znajdź pozycję najstarszego bitu.
  2. Numer tej pozycji jest wartością logarytmu.

Zadanie to można wykonać na kilka sposobów. Jeden z nich przedstawia przykładowy program:

Przykładowy program w języku C++
// Logarytm całkowity o podstawie 2
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-----------------------------------------

#include <iostream>

using namespace std;

int main()
{
    unsigned long long int x,m;
    unsigned int p;

    setlocale(LC_ALL,"");

    cout << "Obliczanie wartości logarytmu całkowitego o podstawie 2" << endl
         << "-------------------------------------------------------" << endl << endl;

    // Odczytujemy liczbę, której logarytm ma zostać obliczony

    cout << "Liczba   = "; cin >> x;
    if(!x) cout << "Nie istnieje logarytm z liczby 0";
    else
    {
        p = 63;                  // Numer pozycji najstarszego bitu
        m = 0x8000000000000000L; // Maska bitowa
        while(!(x & m))
        {
            m >>= 1;
            p--;
        }
        cout << "Logarytm = " << p << endl
             << "Błąd     = " << x - m;
    }
    cout << endl << endl;

    return 0;
}
Wynik
Obliczanie wartości logarytmu całkowitego o podstawie 2
-------------------------------------------------------

Liczba   = 0
Nie istnieje logarytm z liczby 0
 
Obliczanie wartości logarytmu całkowitego o podstawie 2
-------------------------------------------------------

Liczba   = 131
Logarytm = 7
Błąd     = 3
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2019 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.