Arytmetyka z Nasyceniem

Wstęp

Dodawanie dwóch liczb w komputerze jest bardzo wygodne, ale problem pojawa się, gdy wynik nie mieści się w zakresie zmiennej. Wtedy nie można mieć pewności co do wyniku, ponieważ jednostka arytmetyczna ucina część wyniku. Rozwiązaniem jest napisanie własnych funkcji tak, aby wynik nigdy nie wyszedł poza zakres. W tym artykule zostanie wyjaśnione jak takie funkcje można napisać.

Problem

Przed przystąpieniem do pisania funkcji warto zastanowić się skąd i na czym polega problem. Komputerowa jednostka arytmetyczna ALU ma pewne zdefiniowane zasady dodawania. Dodawanie liczb jest bardzo proste. Poczynając od najmniej znaczącego bitu dodawj dwa bity. Jeśli wynik nie mieści się na jednym bicie to mniej znaczący bit pozostaw, a drugi dodaj do następnej pary bitów. Innymi słowy to dodawanie pisemne, ale w systemie binarnym. Przykładowo dodając dwie 8 bitowe liczby bez znaku:

Wiedząc już jak wygląda dodawanie zastanówmy się nad następującym przypadkiem:

Jak można zauważyć wynik wymaga 9 bitów, a zmienne są jedynie 8 bitowe. W tym momencie jednostka arytmetyczna ucina nadmiarowy bit i zapisuje jedynie pierwsz 8 obliczonych bitów do zmiennej. W rezultacie nietrudno się domyśleć, że wynik nie będzie poprawny. W tym przypadku według komputera 39 + 85 = 167 + 213 co oczywiście nie jest prawdą! Z tego powodu stosuje się często nasycenie.

Dodawanie z nasyceniem rozwiązuje częściowo problem z nieprawidłowym wynikiem. Otóż jeśli wynik wykracza poza zakres pojemności zmiennej to jest zwracana odpowiednio wartość najmniejsza lub największa zakresu. W podanym wyżej przykładzie zamiast uzyskania wartości 124 wynik zostałby ustawiony na 255 czyli największą wartość do zapisu na 8 bitach.

Implementacja

Liczby bez znaku

Dodawanie

Dodawanie dwóch liczb bez znaku może spowodować jedynie nadmiar (ang. overflow). Można się przed tym ustrzec sprawdzając czy różnica pomiędzy maksymalną wartością, a a jest w stanie znaleźć b. Jeśli nie to należy zwróci maksymalny zakres, a jeśli tak to po prostu zwrócić sumę.

1. unsigned int dodaj(unsigned int a, unsigned int b) {
2.   if (UINT32_MAX - a <= b) {
3.     return UINT32_MAX;
4.   } else {
5.     return a + b;
6.   }
7. }

Odejmowanie

Dla liczb bez znaku najmniejszą wartością jest 0. Jeśli b będzie większa od a to dojdzie do przekroczenia dolnego zakresu (ang. underflow). W takim jednak przypadku wystarczy zwrócić 0, aby uniknąć problemu.

1. unsigned int odejmij(unsigned int a, unsigned int b) {
2.   if (a >= b) {
3.     return a - b;
4.   } else {
5.     return 0U;
6.   }
7. }

Liczby z znakiem

Dodawanie

Dodawanie dwóch liczb ze znakiem wymaga sprawdzenia wielu różnych przypadków. Otóż jeśli obydwie liczby są dodatnie to może dojść do przepełnienia (overflow), więc dla tego przypadku należy postępować jak dla liczb bez znaku. Drugim przypadkiem jest sytuacja, gdy liczby są różnego znaku - wtedy wystarczy zwrócić ich sumę. Ostatni przypadek dotyczy sytuacji, gdy obie liczby są ujemne. Wtedy należy postępować podobnie jak w przypadku dwóch liczb dodatnich, ale pamiętać, że zakres maksymalny jest inny (np. w systemie U2. jest jedna liczba ujemna więcej).

1. int dodaj(int a, int b) {
2.   if (a >= 0 && b >= 0)
3.     return (INT32_MAX - a >= b) ? a + b : INT32_MAX;
4.   if (a < 0 && b < 0)
5.     return (abs(INT32_MIN - a) >= abs(b)) ? INT32_MIN : a + b;
6.   return a + b;
7. }

Odejmowanie

Jak wiadomo odejmowanie można zastąpić poprzez dodawanie jeśli drugi argument ustawi się na liczbę przeciwną. Jednak i tu czai się pewien drobny problem. Otóż wartość absolutna minimalnej wartości zakresu zmiennej nie ma dodatniego odpowiednika. Z tego powodu należy dopisać własną implementację wartości absolutnej, która odpowiednio będzie zmieniać wartość na przeciwną w określonym zakresie. Oto przykładowa implementacja:

1. int modul(int a) {
2.   if (a == INT32_MIN)
3.     return INT32_MAX;
4.   return -a;
5. }

Wtedy można przejść do napisania funkcji odejmij():

1. int odejmij(int a, int b) {
2.   return dodaj(a, modul(b));
3. }

Testowanie funkcji

Dla każdej funkcji należy napisać oddzielne testy. W każdym przypadku należy pamiętać, aby sprawdzić skrajne przypadki. Oto przykładowe testy do funkcji dodaj() dla liczb bez znaku.

1. int main () {
2.   assert(dodaj(2U, 3U) == 5U);
3.   assert(dodaj(2U, UINT32_MAX) == UINT32_MAX);
4.   assert(dodaj(2U, UINT32_MAX - 3U) == UINT32_MAX - 1);
5.   cout << "Funkcja poprawna!";
6.   system("pause");
7.   return 0;
8. }

• Kod źródłowy Implementacja