osn_progr_final

X Ar pr Ar 1 pr 1 ... A0 p0 A 1 p 1 ... ,

тоді саме число у вигляді послідовності букв алфавіту записується як

X Ar Ar 1 Ar 2 ...A1 A0 .A 1 A 2...

Уцій послідовності крапка відокремлює цілу частину числа від дробової, тобто коефіцієнти при позитивних степенях основи, включаючи нуль, від коефіцієнтів при негативних степенях.

Технічно реалізувати десяткову систему числення на комп'ютері вкрай складно: для збереження десяткової цифри потрібно пристрій з десятьма стійкими станами.

Укомп'ютерах застосовують позиційні системи числення з недесятковою основою: двійкову, вісімкову, шістнадцяткову. Технічно досить просто реалізувати двійковий елемент: є сигнал – немає сигналу. Крім того, у двійковій системі найбільш просто реалізуються всі арифметичні операції: наприклад, двійкова таблиця множення складається усього з чотирьох рядків:

0 х 0 = 0

0 х 1 = 0

1 х 0 = 0

1 х 1 = 1.

При вивченні принципів роботи комп'ютера обійтися без двійкової системи числення, звичайно, не вдасться.

Для двійкової системи числення число X Am Am 1 Am 2...A1 A0 .A 1 A 2...

можна записати в наступному вигляді:

X Am 2m Am 1 * 2m 1 ... A1 * 21 A0 * 20 A 1 * 2 1 ... ,

де Ai або 0, або 1.

У вісімковій системі вживаються вісім цифр: 0, 1, 2, 3, 4, 5, 6, 7. Для вісімкової системи представлення числа X виглядає в такий спосіб:

X Am *8m Am 1 *8m 1 ... A1 *81 A0 *80 A 1 *8 1 ... ,

де коефіцієнти Ai приймають значення від 0 до 7.

Аналогічне представлення справедливе і для шістнадцяткової системи. Алфавіт складається з 16 букв: десяти цифр і шести букв –

A, B, C, D, E, F, що позначають числа 10, 11, 12, 13, 14, 15 відповідно.

У наступній таблиці наведена відповідність чисел у різних системах числення.

Десяткова	Двійкова	Вісімкова	Шістнадцяткова
00	0000	00	0

131

01	0001	01	1
02	0010	02	2
03	0011	03	3
04	0100	04	4
05	0101	05	5
06	0110	06	6
07	0111	07	7
08	1000	10	8
09	1001	11	9
10	1010	12	A
11	1011	13	B
12	1100	14	C
13	1101	15	D
14	1110	16	E
15	1111	17	F

Розглянемо процес представлення числа в різних системах числення.

6.2ПРАВИЛА ПЕРЕВЕДЕННЯ ЧИСЕЛ З ОДНІЄЇ СИСТЕМИ

ЧИСЛЕННЯ В ІНШУ.

Для переходу з двійкової системи в десяткову, зручно скористатися сумуванням по степенях двійки. Наприклад:

(10100)2 = 1*24 + 0*23 + 1*22 + 0*21 + 0 *20 = 16+4 = (20)10

У загальному вигляді, при некратних основах, перехід додатних чисел із системи з основою p в систему з основою s зводиться до виконання наступного алгоритму:

Поділ цілої і дробової частин числа в системі з основою p ;

Послідовний цілочисельний поділ із залишком цілої частини і цілих часток, що утворяться, на основу нової системи s числення доти, доки частка не стане меншою цієї основи;

Запис цілої частини числа в новій системі числення, причому в старший розряд записується остання частка, а потім послідовно, у зворотному порядку, записуються отримані залишки;

Послідовне множення дробової частини числа і дробових частин добутків, що виходять, на основу нової системи s числення доти, доки не вийти цілий добуток, або не буде отримана необхідна кількість цифр для запису дробу в системі з основою s (або не буде виявлений період);

132

Запис дробової частини числа в новій системі числення, причому записуються всі отримані цілі частини добутків так, щоб остання ціла частина потрапила в молодший розряд, а перша в старший;

Об'єднання цілої і дробової частини в новій системі числення за допомогою запису в потрібному місці десяткової

крапки.

При виконанні множення та ділення основа нової системи числення s записується цифрами вихідної системи числення p .

Таким чином, бачимо, що зворотний перехід робиться шляхом послідовного ділення на основу системи, наприклад число 2. Розглянемо конкретний приклад. Переведемо число 20 записане в десятковій системі числення у двійкову систему.

В результаті одержимо двійкове число

(20)10 = (10100)2.

Аналогічно здійснюється перехід з десяткової у вісімкову і шістнадцяткову системи числення.

Існує більш простий спосіб переведення десяткових чисел у двійкову форму. Для переведення десяткового числа X у двійкову форму необхідно знайти найближчий до цього числа менший степінь двійки, тобто знайти таке n , що 2n X і відняти 2n від числа X , при цьому в старший розряд записується одиниця. Далі розглядається число 2n 1 , якщо воно більше отриманого залишка, то в наступний розряд записується 0, а якщо менше, то воно віднімається від залишка, утворити новий залишок, і в наступний розряд записується 1. Потім розглядається степінь n 2 і т.д. Процес продовжується доти, доки в залишку не виявиться нуль або не буде отримана необхідна кількість значущих цифр числа. Для дробових чисел крапка ставиться після двійки в нульовому степені, перед від’ємними степенями. Наприклад, переведемо число 10.5:

23 = 8, 8 < 10.5 записуємо 1 у старший розряд і 10.5 - 8 = 2.5 22 = 4, 4 > 2.5 записуємо в наступний розряд 0

133

21 = 2, 2 < 2.5 записуємо в наступний розряд 1 і 2.5 - 2 = 0.5 20 = 1, 1 > 0.5, записуємо в наступний розряд 0, 2-1 = 0.5, записуємо в наступний розряд 1 і 0.5 - 0.5 = 0

6.3 ПРАВИЛО ВИЗНАЧЕННЯ ТОЧНОСТІ ПРЕДСТАВЛЕННЯ.

Припустимо, що задано десяткове число, яке у вигляді десяткового дробу представляється з точністю до N знаків. Для того, щоб відповідне двійкове число було тієї ж точності, у ньому необхідно записати M - знаків, так що б

2M 10N .

Запишемо алгоритм перетворення:

Вхідні дані алгоритму: Через A будемо позначати вихідний правильний десятковий дріб, що записаний в десятковій формі. Нехай цей дріб містить N знаків.

Алгоритм

Крок 1. Визначимо кількість необхідних двійкових знаків M з нерівності 2M 10N .

Крок 2. Здійснюємо переведення цілої частини числа.

Крок 3: Цикл обчислення цифр двійкового представлення дробової частини числа. Номер цифри після десяткової крапки будемо позначати символом К.

1.K 1

2.Якщо 2 K A

то в запис двійкового числа на K -е місце записуємо нуль

інакше

у запис двійкового числа на K -е місце записуємо 1 А = А - 2-К

3.К = К + 1

4.Якщо K M

то робота алгоритму завершена

інакше переходимо на пункт 2.

Вихідні дані: запис числа в двійковому представленні.

Розглянемо приклад. Перевести число 5.401 у двійкову систему числення.

Ціла частина представляється двійковим числом 101. А дробову частину розкладемо по степенях 2. З правила точності маємо. Нам необхідно одержати стільки знаків M двійкового представлення, щоб 103 було менше ніж 2M . Тобто

134

X Ar pr Ar 1 pr 1 ... A0 p0 A1 p 1 .... Тоді в двійковому роз- кладі в нас повинно бути не менше десяти знаків, тому що 29 = 512 і тільки 210 = 1024.

Крок 1: 2-2 = 0,25; 0,401 - 0,25 = 0,151. - це залишок.

Крок 2: Зараз необхідно степенем двійки представити 0,151.

Зробимо це: 2-3 = 0,125; 0,151 - 0,125 = 0,026

Крок 3: . Найближча до цього числа 0,026 степінь двійки 2-6 = 0,015625; 0,026 - 0,015625 = 0,010375 тепер наше більш точне двійкове число має вид: 0,011001. Після коми вже шість знаків, але цього поки що недостатньо, тому виконуємо ще один крок.

Крок 4: Зараз працюємо з числом 0,010375. Найближча до цього числа ступінь двійки 2-7 = 0,0078125;

0,010375 - 0,0078125 = 0,0025625.

Крок 5: Зараз працюємо з числом 0,0025625. Найближча до цього числа степінь двійки 2-9 = 0,001953125;

0,0025625 - 0,001953125 = 0,000609375.

Останній залишок меншій, ніж 2-10 і якби ми бажали продовжувати наближення до вихідного числа, то нам би знадобилося 2-11, але це вже перевершує необхідну точність, а отже розрахунки можна припинити і записати остаточне двійкове представлення дробової частини:

0,401 = 0,011001101.

І остаточно маємо

5.401=101,011001101. .

Розглянемо правила перетворення систем числення з кратними основами на прикладі двійкової, вісімкової та шістнадцяткової систем. Основи вісімкової та шістнадцяткової систем є цілі степені числа

два:

8 = 23 , 16 = 24 .

На цьому факті ґрунтується наступний підхід.

Для перекладу вісімкового чи шістнадцяткового числа в двійкову форму досить замінити кожну цифру цього числа відповідним трьохрозрядним чи чотирирозрядним двійковим числом, при цьому відкидаючи незначущі нулі в старших розрядах.

Переведемо числа 513.7(8) й 3E7.B(16) у двійкову систему числен-

ня:

( 5 1 3. 7 )8 = (101001011.111)2

135

101 001 011		111
( 3	E	7.	B )16 = (1111100111.1011)2
0011 1110		0111	1011

Перехід від двійкової до вісімкової (чи шістнадцяткової) системи здійснюють у такий спосіб: рухаючись від десяткової крапки вліво і вправо, розбивають двійкове число на групи по три розряди для вісімкової і по чотири для шістнадцяткової системи, доповнюючи до необхідної кількості (три чи чотири), при необхідності, нулями крайні ліву і праву групи. Потім кожну групу заміняють відповідною восімковою чи шістнадцятковою цифрами. Наприклад, переведемо двійкове число 10011101.110 у вісімкове:

010	011	101 .	110 =	(235.6)8,
2	3	5	6
а потім у шістнадцяткове:
1001		1101	. 1100	= ( 9D.С)16.
	9	D	C

Розглянемо ще приклади.

Перевести дане число в десяткову систему числення.

а) 1000001(2).
1000001(2)=1× 26+0× 25+0× 24+0×	23+0× 22+ 0× 21+1×
20 = 64+1=65 .
(10)
б) 1000011111,0101(2).
1000011111,0101(2)=1×29 + 1×24 + 1×23 + 1×22 + 1×21 + 1×20 +
1×2-2 + 1×2-4 = 512 + 16 + 8 + 4 + 2 + 1 + 0,25 + 0,0625 = 543,3125 .
	(10)
в) 1216,04(8).
1216,04 =1×83+2×82+1×81+6×80+4× 8-2	= 512+128+8+6+0,0625 =
(8)

654,0625(10).

г) 29A,5(16).

29A,5(16) = 2×162+9×161+10×160+5×16-1 = 512+144+10+0,3125 = 656,3125(10).

ЗАВДАННЯ ДЛЯ САМОСТІЙНОЇ РОБОТИ.

1.Переведіть десяткові числа у двійкові, вісімкові та шістнадця-

ткові.

а) 3.8 б) 17.0162 в) 0.313 г) 7.127 д) 13.0015

2.Переведіть шістнадцяткові в десяткові, двійкові, вісімкові

136

а)AC2F.F; б) FF.F; в) A3B.12

3. Переведіть двійкове у вісімкове та шістнадцяткове а)10011011.1101; б)101011100.001101; в)1110001.010101

6.4 ДВІЙКОВА АРИФМЕТИКА.

До арифметичних відносяться операції додавання, віднімання, множення і ділення. Розглянемо, як вони виконуються з двійковими числами.

Наведемо таблицю операцій, потім розглянемо їхнє детальне виконання.

Таблиця двійкового	Таблиця двійко-	Таблиця двійко-
додавання	вого	вого
	віднімання	множення
0 + 0 = 0	0 - 0 = 0	0 * 0 = 0
0 + 1 = 1	1 - 0 = 1	0 * 1 = 0
1 + 0 = 1	1 - 1 = 0	1 * 0 = 0
1 + 1 = 0 і одиниця пере-	10 -1 = 1	1 * 1 = 1
носу в старший розряд

6.4.1 Додавання двійкових чисел.

Операція додавання виконується порозрядно зліва направо, як і при додаванні десяткових чисел. При одержанні розрядного переповнення додаємо один старший розряд.

Розглянемо приклади.

Приклад 1. Обчислити 10011 + 10001. Маємо

	1	0	0	1	1
	1	0	0	0	1
1	0	0	1	0	0

Розглянемо виконання операції додавання порозрядно. Нумеруємо розряди зліва направо.

Перший розряд: 1+1 = 2. Одержали число, більше ніж 1, тому записуємо 0 і 1 переносимо в старший розряд.

Другий розряд: 1+0+1 (переносу) =2. Записуємо 0 і 1 переносимо в старший розряд.

137

Третій розряд: 0+0+1(запам”ятована одиниця) = 1. Записуємо 1. Четвертий розряд: 0+0=0. Записуємо 0.

П'ятий розряд: 1+1=2. Записуємо 0 і додаємо до шостим розрядом 1.

Таким чином, одержали число 100100. Разом

10011+10001=100100.

Приклад 2.

Обчислити 1010.01+1011.10

1010.01	(10.25)
+
1011.10	(11.05)
10101.11	(21.75)

Маємо

	1	0	1	0	.	0	1
	1	0	1	1	.	1	0
1	0	1	0	1	.	1	1

6.4.2 Представлення від’ємних чисел.

З метою спрощення виконання арифметичних операцій застосовують спеціальні коди для представлення чисел. Операція віднімання (алгебраїчного додавання) зводиться до арифметичного додавання кодів. Для представлення цілих чисел зі знаком у комп'ютері застосовують прямий, зворотний і додатковий коди.

Загальна ідея побудови кодів така. Код трактується як число без знака, а діапазон чисел, що представляються кодами без знака розбивається на два піддіапазони. Один з них представляє додатні числа, а інші – від’ємні. Коди формуються так, щоб значення старшого розряду вказувало на знак чисел, що представляються.

6.4.2.1 Прямий код.

Прямий код двійкового числа A , що представляється в n- розрядній сітці, визначається як:

A , якщо A 0 ;

a A , якщо A 0 ,

138

де a - величина, що дорівнює вазі старшого розряду сітки: для дробів a 1, а для цілих a 2n 1 . Діапазон чисел, що представляються прямим кодом: 0 A a .

Ознакою представлення додатних чисел є наявність нуля в старшому розряді. Наявність у цьому розряді 1 говорить про те, що число від’ємне. Таким чином, прямий код двійкового числа збігається по зображенню з записом самого числа, але в розряді знака стоїть 0 чи 1 відповідно для додатних чи від’ємних чисел. Наприклад, для чотирирозрядної сітки маємо:

0101	(5)
1101	(-5)

Додавання в прямому коді чисел, що мають однакові знаки здійснюється досить просто. Числа додаються і сумі присвоюється знак доданків. Однак для операції додавання чисел з різними знаками прямий код незручний. У цьому випадку доводиться визначати більше по модулю число, здійснювати віднімання, а потім різниці присвоювати знак більшого по модулю числа.

Операція віднімання зводиться до операції арифметичного додавання за допомогою оберненого і додаткового кодів.

6.4.2.2 Обернений код.

Обернений код двійкового числа A , що представляється в n- розрядній сітці, визначається як

I=A, якщо A 0 ; I= b A , якщо A 0

де b - величина найбільшого числа без знака, що розміщується в n- розрядній сітці: для дробових чисел b 2 2 (n 1) , а для цілих b 2n 1. Діапазон чисел, що представляються зворотним кодом, такий самий, як і для чисел прямого коду: 0 I a . За означенням, зворотний код

від’ємного числа являє собою доповнення модуля вихідного числа до найбільшого числа без знака, що міститься в розрядній сітці. У зв'язку з цим одержання зворотного коду двійкового від’ємного числа зводиться до одержання інверсії n-розрядного коду абсолютної величини цього числа. Оскільки модуль чисел, що представляються у n- розрядній сітці, I a , то в старшому (знаковому) розряді зворотного

коду в додатних чисел буде 0, а у від’ємних 1. У цифрових розрядах зворотного двійкового коду представляється або модуль числа (для додатних чисел), або його інверсія (для від’ємних).

139

Розглянемо операцію алгебраїчного додавання

0101		(5)
+		+
1101		(-2)
10010
1
0011		( 3)

Перенос, що виникає у знаковому розряді, при використанні зворотного коду повинний додаватися в молодший розряд суми. Такий перенос називається круговим чи циклічним.

При виконанні розрахунків на машині може виникнути як "додатний", так і "від’ємний" нуль. Додатний нуль у прямому і зворотному коді має вигляд:

(+0) = 00000.....00; для прямого представлення;

(+0) = 00000.....00; для зворотного представлення. Від’ємний нуль зображується відповідно для прямого і зворот-

ного коду:

(-0) = 100000...00; для прямого представлення (-0) = 111111...11; для зворотного представлення.

Для того, щоб уникнути ситуації виникнення двох нулів, застосовують додатковий код.

6.4.2.3 Додатковий код.

Перейдемо тепер до питання представлення від’ємних чисел. Для визначеності розглянемо представлення чисел, у якому будь-яке число займає рівно вісім біт. З запису в двійковій системі числення рівності ( 1) 1 0 легко знайти, який вигляд повинне мати невідоме

нам поки що двійкове представлення xxxxxxxx числа 1: xxxxxxxx + 00000001 = 00000000

Ясно, що на місці символів xxxxxxxx повинне бути розташоване число 11111111. Правильним результатом додавання при цьому, звичайно, варто було б вважати 100000000, а не 00000000, але ми маємо справу з восьмибітовим представленням і оскільки результат зобов'язаний розміститися в байті, то старша одиниця відкидається.

Отже, число 1 повинне кодуватися як 11111111. Далі вже зовсім просто: для одержання -2 потрібно –1 зменшити на одиницю, що дасть 11111110; число –3 представляється як 11111101 і т.д.

140