Dodawanie dwójkowe

Do wykonywania dodawania dwójkowego (ang. binary addition) 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.

System U2

Na poprzedniej lekcji poznaliśmy szczegółowo naturalny system binarny NBC (ang. Natural Binary Code). Jest on niezmiernie ważny dla informatyka, ponieważ stanowi punkt wyjścia dla większości innych systemów kodowania liczb. Jednakże NBC pozwala zapisywać tylko liczby dodatnie oraz liczbę zero. W przypadku liczb ujemnych mamy problem. W tym momencie większość uczniów podrapie się za uchem i odpowie - jaki tam znowu problem, po prostu dopisujemy przed liczbą znak minus i załatwione, na przykład:

-101₍₂₎ = -5₍₁₀₎.

Super. Ale tak można zrobić jedynie na papierze. Liczby binarne muszą być umieszczane w pamięci komputera, a tam mamy tylko bity, czyli symbole 0 lub 1. Żaden bit nie przyjmuje dodatkowego stanu '-'. Mamy zatem problem. A problem ten sprowadza się do wymyślenia takiego sposobu kodowania, aby za pomocą bitów można było zapisywać wartości ujemne.

O ile system NBC był swobodny co do ilości bitów w zapisie liczby, to systemy kodowania liczb ze znakiem posiadają ściśle ustalone formaty, tzn. ilość bitów w zapisie liczby jest określona na stałe (8b, 16b, 32b, 64b itd.). Jest to konieczne, ponieważ zwykle najstarszy bit posiada inne znaczenie od pozostałych bitów liczby (nazywany jest on często bitem znaku - ang. sign bit) i musimy znać jego położenie, aby prawidłowo zinterpretować wartość liczby.

System kodowania liczb ze znakiem nazywany jest systemem uzupełnień do podstawy 2 lub w skrócie U2 (ang. 2C - Two's Complement). W systemie U2 wagi pozycji dwójkowych są takie same jak w NBS, z wyjątkiem najstarszej pozycji, która jest ujemna. Bit na tej pozycji nosi nazwę bitu znakowego (ang. sign bit).

Wartości wag pozycji w zapisie U2
waga	-2^n-1	2^n-2	2^n-3		2²	2¹	2⁰
cyfra	b_n-1	b_n-2	b_n-3	...	b₂	b₁	b₀

Liczba jest dodatnia, gdy bit znaku ma wartość 0 - suma pozostałych wag tworzy zawsze liczbę dodatnią lub zero. Jeśli bit znaku przyjmie wartość 1, to liczba jest ujemna.

Zapamiętaj:

Wartość liczby U2 obliczamy tak samo jak w systemie NBS - cyfry mnożymy przez wagi pozycji, na których się znajdują i dodajemy otrzymane iloczyny. Waga bitu znakowego jest ujemna.

b_n-1b_n-2b_n-3...b₂b₁b_{0
(U2)} = b_n-1(-2^n-1) + b_n-22^n-2 + b_n-32^n-3 + ... + b₂2² + b₁2¹ + b₀2⁰

gdzie

b - bit, cyfra dwójkowa 0 lub 1
n - liczba bitów w zapisie liczby

4 bitowy system U2
Kod U2	Przeliczenie	Wartość
0000	0	0
0001	2⁰	1
0010	2¹	2
0011	2¹ + 2⁰	3
0100	2²	4
0101	2²+ 2⁰	5
0110	2² + 2¹	6
0111	2² + 2¹ + 2⁰	7
1000	(-2³)	(-8)
1001	(-2³) + 2⁰	(-7)
1010	(-2³) + 2¹	(-6)
1011	(-2³) + 2¹ + 2⁰	(-5)
1100	(-2³) + 2²	(-4)
1101	(-2³) + 2² + 2⁰	(-3)
1110	(-2³) + 2² + 2¹	(-2)
1111	(-2³) + 2² + 2¹ + 2⁰	(-1)

Ponieważ w systemach binarnych cyfry przyjmują tylko dwie wartości 0 lub 1, można rachunek znacznie uprościć sumując jedynie te wagi, dla których cyfra zapisu liczby ma wartość 1.

W tabelce obok zebraliśmy wszystkie możliwe do utworzenia 4-bitowe liczby w kodzie U2. Zauważ, iż w tym systemie liczb ujemnych jest o 1 więcej niż dodatnich (-8 .. -1, 1 .. 7). Najstarszy bit określa znak liczby. Jeśli jest równy 0, liczba jest dodatnia i resztę zapisu możemy potraktować jak liczbę w naturalnym kodzie dwójkowym.

Przykład:

01101011_(U2) = 64 + 32 + 8 + 2 + 1 = 107₍₁₀₎.

Jeśli bit znaku ustawiony jest na 1, to liczba ma wartość ujemną. Bit znaku ma wagę (-2^n-1), gdzie n oznacza liczbę bitów w wybranym formacie U2. Reszta bitów jest zwykłą liczbą w naturalnym kodzie dwójkowym. Wagę bitu znakowego i wartość pozostałych bitów sumujemy otrzymując wartość liczby U2:

Przykład:

11101011_(U2) = (-2⁷) + 64 + 32 + 8 + 2 + 1 = -128 + 107 = (-21)₍₁₀₎.

Liczbę przeciwną do danej liczby U2 uzyskujemy na dwa sposoby:

Zapamiętaj:

Sposób 1 - procedura wyznaczania liczby przeciwnej w kodzie U2

Dokonać negacji wszystkich bitów zapisu liczby U2.
Do wyniku dodać 1.

Przykład:

Wyznaczyć liczbę przeciwną w kodzie U2 do danej liczby 01101110_(U2).

Dokonujemy negacji (zmianę na wartości przeciwne) wszystkich bitów liczby U2:

NOT	01101110
	10010001

Do wyniku negacji dodajemy 1:

	10010001
+	00000001
	10010010

Liczbą przeciwną do 01101110_(U2) jest 10010010_(U2).

Aby się o tym przekonać, obliczmy wartości dziesiętne obu liczb:

01101110_(U2) = 64 + 32 + 8 + 4 + 2 = 110₍₁₀₎.
10010010_(U2) = (-128) + 16 + 2 = (-128) + 18 = (-110)₍₁₀₎.

Zwróć uwagę, iż tym sposobem nie da się otrzymać liczby przeciwnej do najmniejszej liczby ujemnej (bit znaku ustawiony na 1, a wszystkie pozostałe bity równe 0). Na przykład dla 4 bitowego kodu U2 otrzymujemy:

(-8)₍₁₀₎ = 1000_(U2) ; NOT(1000) = 0111; 0111 + 0001 = 1000, a to jest ta sama liczba wyjściowa.

Oczywistym wyjaśnieniem tego faktu jest to, iż najmniejsza w danym formacie U2 liczba ujemna nie posiada w tym formacie swojego odpowiednika po stronie dodatniej, gdyż suma wszystkich wag dodatnich jest o 1 mniejsza od modułu wagi ujemnej bitu znakowego.

Zapamiętaj:

Sposób 2 - procedura wyznaczania liczby przeciwnej w kodzie U2

Przejść do pierwszego od prawej strony bitu zapisu liczby.
Do wyniku przepisać kolejne bity 0, aż do napotkania bitu o wartości 1, który również przepisać.
Wszystkie pozostałe bity przepisać zmieniając ich wartość na przeciwną.

Ten drugi sposób jest o wiele prostszy, ponieważ nie wymaga od nas dodawania. Możemy go zastosować prawie bezmyślnie do dowolnie długich liczb U2.

Przykład:

Znaleźć liczbę przeciwną w kodzie U2 do danej liczby 1100100010111010111010010100001000000_(U2). Bez paniki, pokażemy w kolejnych krokach, jak to zadanie wykonać:

Analizę liczby rozpoczynamy od ostatniej cyfry zapisu liczby. Przesuwamy się w lewą stronę. Do wyniku przepisujemy wszystkie kolejne bity o wartości 0, aż do napotkania bitu 1.

Liczba U2	1100100010111010111010010100001000000
Liczba przeciwna U2	000000

Napotkany bit 1 również przepisujemy do wyniku bez zmian:

Liczba U2	1100100010111010111010010100001000000
Liczba przeciwna U2	1000000

Pozostałe bity przepisujemy zmieniając ich stan na przeciwny. To wszystko.

Liczba U2	1100100010111010111010010100001000000
Liczba przeciwna U2	0011011101000101000101101011111000000

Również drugi sposób zawodzi przy wyznaczaniu liczby przeciwnej do najmniejszej liczby ujemnej w danym formacie U2. Dlatego na wartość tę należy zwrócić szczególną uwagę.

Przeliczanie liczb dziesiętnych na liczby U2

Dla liczb dodatnich nie ma problemu z przeliczaniem na kod U2. Wystarczy znaleźć reprezentację dwójkową danej wartości liczbowej, a następnie uzupełnić ją bitami 0 do długości formatu kodu U2.

Przykład:

Wyznaczyć 8-mio bitowy kod U2 dla liczby dziesiętnej 27₍₁₀₎.

27₍₁₀₎ = 16 + 8 + 2 + 1 = 11011₍₂₎ = 00011011_(U2).

W przypadku wartości ujemnej mamy kilka możliwości postępowania, które opisujemy poniżej.

Zapamiętaj:

Sposób 1 - przeliczanie ujemnej liczby dziesiętnej na liczbę U2

Liczba ujemna musi mieć ustawiony na 1 bit znaku. Zatem nasze zadanie sprowadza się do znalezienia wartości pozostałych bitów. Bit znaku stoi na pozycji o wadze (-2^n-1), n - ilość bitów w formacie U2. Pozostałe bity zapisu liczby tworzą naturalny od dwójkowy. Wartość tego kodu musi być taka, aby po dodaniu jej do wagi pozycji znakowej otrzymać wartość kodowanej liczby. Zapiszmy to w formie równania:

kodowana liczba = waga bitu znakowego + wartość kodu pozostałych bitów

kodowana liczba = (-2^n-1) + wartość kodu pozostałych bitów

stąd

wartość kodu pozostałych bitów = 2^n-1 + kodowana liczba

Po wyznaczeniu wartości tego kodu tworzymy jego zapis w systemie dwójkowym, uzupełniamy w miarę potrzeby bitem 0 do długości formatu U2 - 1 i dodajemy bit znakowy 1. Konwersja jest gotowa.

Przykład:

Wyznaczyć 8-mio bitowy kod U2 dla liczby dziesiętnej (-45)₍₁₀₎.

Wyznaczamy moduł wagi pozycji znakowej. Dla n = 8, 2^n-1 = 2⁷ = 128 wartość kodu pozostałych bitów = 128 + (-45) = 83 = 1010011₍₂₎

Dodajemy bit znaku równy 1 i otrzymujemy:

(-45)₍₁₀₎ = 11010011_(U2).

Zapamiętaj:

Sposób 2 - przeliczanie ujemnej liczby dziesiętnej na liczbę U2

Wyznaczamy zapis dwójkowy liczby przeciwnej (czyli dodatniej).
Otrzymany kod dwójkowy uzupełniamy w miarę potrzeb do rozmiaru formatu U2.
Wyznaczamy liczbę przeciwną za pomocą jednej z opisanych wcześniej metod

Przykład:

Wyznaczyć 8-mio bitowy kod U2 dla liczby dziesiętnej (-45)₍₁₀₎.

Wyznaczamy kod binarny liczby przeciwnej: 45₍₁₀₎ = 101101₍₂₎

Kod uzupełniamy dwoma bitami 0 do wymaganej długości 8 bitów: 00101101.

Wyznaczamy liczbę przeciwną wg drugiej metody: 00101101_(U2) : 11010011_(U2).

Stąd (-45)₍₁₀₎ = 11010011_(U2).

Zapamiętaj:

Sposób 3 - przeliczanie ujemnej liczby dziesiętnej na zapis U2

Jeśli do liczby 2ⁿ (n - ilość bitów w formacie U2) dodamy przetwarzaną liczbę dziesiętną, to w wyniku otrzymamy wartość kodu dwójkowego równoważnego bitowo (tzn. o takiej samej postaci) kodowi U2 przetwarzanej liczby. Wynik dodawania wystarczy zapisać w postaci naturalnego kodu dwójkowego i konwersja jest zakończona.

Przykład:

Wyznaczyć 8-mio bitowy kod U2 dla liczby dziesiętnej (-45)₍₁₀₎.

2⁸ + (-45) = 256 - 45 = 211 = 11010011₍₂₎.

Stąd

(-45)₍₁₀₎ = 11010011_(U2).

Zakres n bitowych liczb U2

Największa liczba U2 powstaje dla bitu znaku równego 0, a pozostałych bitów równych 1. Ponieważ pozostałe bity przedstawiają wartość w naturalnym kodzie binarnym i jest ich n-1, to

max_(U2) = 2^n-1 - 1

Z kolei najmniejszą wartość liczby U2 otrzymamy dla bitu znaku równego 1, a pozostałych bitów równych 0. W tym przypadku wartość liczby jest równa wadze pozycji znakowej, czyli

min_(U2) = (-2^n-1)

Zapamiętaj:

Zakres n bitowej liczby w kodzie U2 wynosi

Z_(U2) = -2^n-1 ... 2^n-1- 1

Zakres liczb U2 jest niesymetryczny - liczb ujemnych jest o jedną więcej niż liczb dodatnich.

Przykład:

4 bitowe liczby U2 posiadają zakres:

od	-2³	=	-8	= 1000_(U2)
do	2³ - 1	=	7	= 0111_(U2)

8 bitowe liczby U2 posiadają zakres:

od	-2⁷	=	-128	= 10000000_(U2)
do	2⁷ - 1	=	127	= 01111111_(U2)

16 bitowe liczby U2 posiadają zakres:

od	-2¹⁵	=	-32768	= 1000000000000000_(U2)
do	2¹⁵ - 1	=	32767	= 0111111111111111_(U2)

Dodawanie liczb U2

System zapisu U2 liczb ze znakiem jest dzisiaj powszechnie stosowany we wszystkich komputerach IBM, ponieważ jego arytmetyka jest bardzo zbliżona do arytmetyki liczb w naturalnym kodzie binarnym. Dzięki temu procesory mogą wykonywać operacje arytmetyczne na liczbach NBC i U2 za pomocą tych samych układów elektronicznych. A to przekłada się bezpośrednio na pieniążki - niższe koszty opracowania i produkcji procesorów.

Liczby U2 dodajemy wg poznanych zasad dla naturalnego systemu dwójkowego. Przeniesienia poza bit znaku ignorujemy (w rzeczywistości takie przeniesienia czy pożyczki mogą być wykorzystywane przez procesor do dodawania liczb o tzw. wielokrotnej precyzji).

Przykład:

3 + 3

	0011
+	0011
	0110

5 + (-4)

	0101
+	1100
1	0001

(-3) + (-2)

	1101
+	1110
1	1011

(-5)

Nadmiar i niedomiar w kodzie U2

W trakcie wykonywania działań arytmetycznych wynik operacji może przekroczyć dozwolony zakres liczb zarówno powyżej górnej granicy (nadmiar - ang. overflow) jak i poniżej dolnej (niedomiar - ang. underflow). Cechą charakterystyczną nadmiaru/niedomiaru jest zmiana znaku wyniku w sytuacji, gdy nie powinna ona nastąpić. Załóżmy, iż operujemy na 4 bitowych liczbach w kodzie U2 i chcemy wykonać proste dodawanie:

0 111 + 0 001		7 + 1
1 000		-8

Otrzymany wynik jest niepoprawny w tym kodzie. Spowodowane to jest tym, iż liczba 8 będąca sumą 7 i 1 wykracza poza górny zakres wartości 4 bitowego kodu U2 (równy 7) i nie można jej poprawnie przedstawić - musielibyśmy przeznaczyć na zapis liczby więcej bitów.

Podobną sytuację zastaniemy przy próbie dodania dwóch liczb ujemnych, np. -6 i -3:

1 010 + 1 101		-6 + -3
10 111		7

Liczba -9 jest mniejsza od dolnego krańca 4 bitowych liczb w kodzie U2 (równego -8) i z tego powodu nie może być poprawnie przedstawiona w tym kodzie.

Zapamiętaj:

Wystąpienie nadmiaru lub niedomiaru jest wskazówką dla programisty, iż źle dobrał typ danych dla przetwarzanej informacji - liczby są reprezentowane zbyt małą ilością bitów i nie można poprawnie zapisywać wyniku operacji. Najprostszym rozwiązaniem będzie zwiększenie długości formatu U2 (np. z 16 bitów na 32 bity).

Informatyka dla klas II – Liczby bez znaku i ze znakiem

Dodawanie dwójkowe

Uwaga, pułapka:

System U2

Zapamiętaj:

Zapamiętaj:

Zapamiętaj:

Przeliczanie liczb dziesiętnych na liczby U2

Zapamiętaj:

Zapamiętaj:

Zapamiętaj:

Zakres n bitowych liczb U2

Zapamiętaj:

Dodawanie liczb U2

Nadmiar i niedomiar w kodzie U2

Zapamiętaj: