Binarne Kodowanie Liczb - Operacje arytmetyczne w systemie dwójkowym

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 =	10

Przykład:

Zsumować liczby binarne 1111001₍₂₎ oraz 10010₍₂₎.

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

	1111001
+	10010

Sumowanie rozpoczynamy od ostatniej kolumny. Sumujemy cyfry w kolumnie zgodnie z podaną tabelką zapisując wynik pod kreską:

	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	1	1	1	0	0	1
+			1	0	0	1	0
			0	1	0	1	1

Jeśli w krótszej liczbie zabrakło cyfr, to dopisujemy zera. Pamiętajmy o przeniesieniach.

1	1	1
	1	1	1	1	0	0	1
+	0	0	1	0	0	1	0
	0	0	0	1	0	1	1

Dodaliśmy wszystkie cyfry, ale przeniesienie wciąż wynosi 1. Zatem 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
	0	1	1	1	1	0	0	1
+	0	0	0	1	0	0	1	0
	1	0	0	0	1	0	1	1

1111001₍₂₎ + 10010₍₂₎ = 10001011₍₂₎ (121 + 18 = 139)

Oto kilka dalszych przykładów:

	1	1	1	1	1	1	1
	0	1	1	1	1	1	1	1
+	0	0	0	0	0	0	0	1
	1	0	0	0	0	0	0	0

	1	1	1	1	1	1	1
	0	1	1	1	1	1	1	1
+	0	0	0	0	0	1	0	1
	1	0	0	0	0	1	0	0

		1	1	1	1
	1	0	1	1	1	1	1	0
+	0	0	0	0	1	1	0	0
	1	1	0	0	1	0	1	0

Uwaga, pułapka:

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⁸ - 1, czyli większy od 255):

11111111₍₂₎ + 00000001₍₂₎ = 1|00000000₍₂₎ (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).

Przykład:

Wykonać odejmowanie w systemie binarnym 1101110₍₂₎ - 1111₍₂₎.

Obie liczby umieszczamy jedna pod drugą tak, aby ich cyfry znalazły się w kolumnach o tych samych wagach:

	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	1	0	1	1	1	0
-				1	1	1	1
							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	1	0	1	1	1	0
-				1	1	1	1
						1	1

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	1	0	1	1	1	0
-	0	0	0	1	1	1	1
	1	0	1	1	1	1	1

1101110₍₂₎ - 1111₍₂₎ = 1011111₍₂₎ (110₍₁₀₎ - 15₍₁₀₎ = 95₍₁₀₎).

Oto kilka dalszych przykładów:

	1	1	1	1	1	1	1
	1	0	0	0	0	0	0	0
-	0	0	0	0	0	0	0	1
	0	1	1	1	1	1	1	1

				1	1	1	1
	1	1	1	1	0	0	0	0
-	0	0	0	0	1	1	1	1
	1	1	1	0	0	0	0	1

	1		1		1		1
	1	0	1	0	1	0	1	0
-	0	1	0	1	0	1	0	1
	0	1	0	1	0	1	0	1

Uwaga, pułapka:

Przy odejmowaniu również może dochodzić do nieprawidłowych sytuacji. Jeśli od liczby mniejszej odejmiemy większą, 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
		0	0	0	0	0	0	0	0
-		0	0	0	0	0	0	0	1
		1	1	1	1	1	1	1	1

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 × 0 =	0
0 × 1 =	0
1 × 0 =	0
1 × 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.

Przykład:

Pomnożyć binarnie liczbę 1101₍₂₎ przez 1011₍₂₎.

Obie liczby umieszczamy jedna pod drugą tak, aby ich cyfry znalazły się w kolumnach o tych samych wagach:

	1101
×	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	1	0	1
×				1	0	1	1
				1	1	0	1
			1	1	0	1
		0	0	0	0
	1	1	0	1

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	1	0	1
×				1	0	1	1
	0	0	0	1	1	0	1
	0	0	1	1	0	1	0
+	1	1	0	1	0	0	0
1	0	0	0	1	1	1	1

Sprawdź, czy otrzymany wynik jest poprawny.

Oto kilka dalszych przykładów:

			1	0	1
×			1	1	1
			1	0	1
		1	0	1
+	1	0	1
1	0	0	0	1	1

			1	0	1	1
×				1	1	0
			0	0	0	0
		1	0	1	1
+	1	0	1	1
1	0	0	0	0	1	0

			1	1	1
×			1	1	1
			1	1	1
		1	1	1
+	1	1	1
1	1	0	0	0	1

Uwaga, pułapka:

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ⁿ - 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

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

Przykład:

Podzielimy liczbę 1101₍₂₎ przez 10₍₂₎ (13₍₁₀₎ : 2₍₁₀₎).

Przesuwamy w lewo dzielnik, aż zrówna się jego najstarszy, niezerowy bit z najstarszym, niezerowym bitem dzielnej. Nad dzielną rysujemy kreseczkę:

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			- pierwsza cyfra wyniku dzielenia
	1	1	0	1	- dzielna
-	1	0			- przesunięty dzielnik
	0	1	0	1	- 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	1	0	- wynik dzielenia
	1	1	0	1	- dzielna
-	1	0			- przesunięty dzielnik
	0	1	0	1	- dzielna po pierwszym odejmowaniu przesuniętego dzielnika
-		1	0		- przesunięty dzielnik
	0	0	0	1	- dzielna po drugim odejmowaniu przesuniętego dzielnika
-			1	0	- dzielnik na swoim miejscu, odejmowanie niemożliwe
	0	0	0	1	- 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.

W naszym przykładzie otrzymaliśmy wynik dzielenia równy:

1101₍₂₎ : 10₍₂₎ = 110₍₂₎ i resztę 1₍₂₎ (6₍₁₀₎ i 1₍₁₀₎)

Jest to wynik poprawny, gdyż 2 mieści się w 13 sześć razy i pozostaje reszta 1.

Przykład:

Dla wprawki podzielmy liczbę 110101101₍₂₎ przez 111₍₂₎ (429₍₁₀₎ przez 7₍₁₀₎):

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₍₂₎ : 111₍₂₎ = 111101₍₂₎ i reszta 10₍₂₎ (429₍₁₀₎ : 7₍₁₀₎ = 61₍₁₀₎ i reszta 2₍₁₀₎).

Zadanie 1 (łatwe)

Zadanie 2 (łatwe)

Zadanie 3 (łatwe)

Zadanie 4 (łatwe)

Zadanie 5 (średnie)

Czy nie wykonując dzielenia binarnego potrafiłbyś oszacować ilość cyfr wyniku na podstawie znajomości dzielnej i dzielnika? Odpowiedź uzasadnij.

Zadanie 6 (łatwe)

Podaj szybką regułę mnożenia liczb binarnych przez 2ⁿ, gdzie n = 1,2,3...

Zadanie 7 (łatwe)

Podaj szybką regułę dzielenia liczb binarnych przez 2ⁿ, gdzie n = 1,2,3...

Zadanie 8 (średnie)

Podaj szybką regułę mnożenia liczby binarnej przez 10₍₁₀₎.

Zadanie 9 (średnie)

Operacje arytmetyczne dodawania, odejmowania i mnożenia mogły w przypadku ustalonego formatu liczb dawać niepoprawne wyniki. Czy taką cechę posiada również operacja dzielenia dwójkowego? Odpowiedź uzasadnij.

Zadanie 10 (średnie)

Jakie wartości może przyjmować reszta z dzielenia całkowitego dwóch liczb? Jaki wniosek wyciągniesz, jeśli jest ona różna od zera i równa zero?

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.

I Liceum Ogólnokształcące
im. Kazimierza Brodzińskiego
w Tarnowie
(C)2013 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

11001 + 111 =		.
11111 + 100 =		.
111 + 1001 =		.
1010101 + 10101 =		.
11110000 + 111000 =		.

1000000 - 1 =		.
11110000 - 11 =		.
1100110011 - 111 =		.
11001011 - 1100111 =		.
110111 - 1011 =		.

1101 • 101 =		.
11 • 1101 =		.
1111 • 11 =		.
11011 • 1011 =		.
1111 • 1111 =		.

Twój email:	(jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga:	← tutaj wpisz wyraz ilo , inaczej list zostanie zignorowany

Operacje arytmetyczne w systemie dwójkowym

Dodawanie dwójkowe

Uwaga, pułapka:

Odejmowanie dwójkowe

Uwaga, pułapka:

Mnożenie dwójkowe

Uwaga, pułapka:

Dzielenie dwójkowe

Zadania

Zadanie 1 (łatwe)

Zadanie 2 (łatwe)

Zadanie 3 (łatwe)

Zadanie 4 (łatwe)

Zadanie 5 (średnie)

Zadanie 6 (łatwe)

Zadanie 7 (łatwe)

Zadanie 8 (średnie)

Zadanie 9 (średnie)

Zadanie 10 (średnie)

List do administratora Serwisu Edukacyjnego I LO

11111 : 11 =	i reszta	.
10000 : 11 =	i reszta	.
101101111 : 1010 =	i reszta	.