osn_progr_final

A 0 ;

A , що представляється в n-

Від’ємні числа завжди мають у своєму двійковому представленні одиницю в самому старшому розряді, який називають знаковим. Абсолютна величина числа, що кодується, отримується як двійкове доповнення інших біт (нулі потрібно замінити на одиниці і навпаки), збільшене на одиницю. Таке представлення називається додатковим кодом.

Додатковий код двійкового числа розрядній сітці, визначається як

I=А, якщо

I= c A , якщо A<0

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

пливає, що старший (знаковий) розряд коду додатнього числа дорівнює 0, а в коду від’ємного числа –1. Додатковий код від’ємного числа зручно одержувати через зворотний код.

Додатковий код від’ємного числа може бути отриманий зі зворотного додаванням 1 до молодшого розряду зворотного коду. Наприклад, для чотирирозрядної сітки:

0101 (5)

1011 (-5)

Або для переведення числа в додатковий код можна рекомендувати наступний алгоритм:

Крок 1. У двійковому представленні абсолютної величини числа всі одиниці замінити нулями і навпаки;

Крок 2. До отриманого результату додати одиницю.

Застосуємо наведений алгоритм до числа -5. Нехай нас цікавить стандартне 16-розрядне значення. Спочатку представимо модуль числа в двійкового вигляді, доповнивши його нулями ліворуч до необхідної кількості розрядів. Тоді десяткове число 5 перетвориться до виду 0000 0000 0000 0101. Зробимо заміну нулів і одиниць; одержимо 1111 1111 1111 1010 . Додаємо одиницю й одержуємо відповідь: 1111

1111 1111 1011.

При визначенні величини числа знаковий розряд не використовується, так що числа зі знаком мають максимальне значення, що складається з 15 двійкових розрядів.

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

141

Властивість 1. Повторне застосування розглянутих вище правил перетворень у додатковий код повертає вихідне число.

Властивість 2. Додавання вихідного числа з його додатковим кодом завжди дає нульовий результат, тому що X + (-X) = 0.

Узагальнюючи цю властивість, можна стверджувати, що замість віднімання завжди можна скористатися додаванням зменшуваного та додаткового коду від'ємника.

6.4.3 ВІДНІМАННЯ ДВІЙКОВИХ ЧИСЕЛ .

Спочатку розглянемо операцію віднімання для простого двійкового представлення. Щораз, коли цифра в розряді від’ємника більша за цифру в тому ж же розряді зменшуваного, запозичується 1 з наступного, старшого розряду. Ця запозичена одиниця дорівнює двом одиницям поточного розряду. Наприклад, якщо потрібно з одного двійкового числа відняти інше:

Приклад 3.

1 1 0 1 1 1 0 1 1 1

Перший розряд: 1 - 0 =1. Записуємо 1.

Другий розряд: 0 - 1. Запозичуємо одиницю в старшому розряді. Одиниця зі старшого розряду переходить у молодший, як дві одиниці, тому при вирахуванні одержимо 1.

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

Приклад 4. Виконати 10101.11-1010.01

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

142

Розглянемо віднімання через додатковий код. Його можна замінити на додавання, якщо від'ємник замінити на число в додатковому коді.

Маємо:

a b a add ( b) a b 1

де add () позначена функція одержання додаткового коду, b - число отримане інверсією числа b .

Наприклад:

	0	1	0	1	(5)
	1	1	0	1	(-3)
1	0	0	1	0	(2).

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

10.

Необхідно пам'ятати, що результат алгебраїчного додавання доданків, представлених у додатковому коді, виходить у тому ж коді, що і доданки. Для того, щоб змінити знак числа необхідно:

у прямому коді змінити знаковий розряд числа на протилежний;

у зворотному коді інвертувати код;

у додатковому коді інвертувати код і додати 1 у молодший

розряд.

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

1100000011.011

-

101010111.1

110101011.111

6.4.4 МНОЖЕННЯ ДВІЙКОВИХ ЧИСЕЛ.

Операція множення в двійковій системі числення цікава своєю реалізацією. Для того, щоб помножити двійкове число на 2 (десяткова двійка це 10 у двійковій системі) досить до числа, що множиться справа приписати один нуль.

Приклад 1. 10101 * 10 = 101010

Ми знаємо, що будь-яке двійкове число розкладається по степенях двійки, тому множення в двійковій системі числення зводиться до множення на 10 (тобто на десяткову 2), а отже, множення –це ряд

143

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

Приклад 2.

Помножити два числа 1011 і 101.

Це множення можна звести до суми трьох порязрядних множень:

1011 * 1 + 1011 * 0 + 1011 * 100 = 1011 +101100 = 110111 .

У стовпчик це ж саме можна записати так:

		1	0	1	1
	*		1	0	1
		1	0	1	1
	0	0	0	0
1	0	1	1
1	1	0	1	1	1

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

а) 1101 * 1110 б) 1010 * 110 г) 1011 * 11

д) 101011 * 1101 е) 10010 * 1001

6.4.5 ДІЛЕННЯ ДВІЙКОВИХ ЧИСЕЛ.

Нехай нам необхідно розділити два десяткових числа, наприклад 234 розділити на 7. Як ми це робимо? У діленому спочатку виділяємо справа від старшого розряду таку кількість цифр, щоб число, що вийшло, було мінімальним і в той же час більшим дільника. У даному прикладі необхідне нам число 23. Потім ділимо отримане число на дільник із залишком.

Описану операцію повторюємо доти, поки отриманий залишок не виявиться меншим дільника. Тоді число, отримане під рискою результату– це частка, а останній залишок - це залишок операції.

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

144

Приклад 1. 10010111 / 101

1 0 0 1 0 1 1 1 1 0 1

Шукаємо число, рухаючись від старшого розряду, яке перше було б більше дільника. Це чотирирозрядне число 1001. Тепер необхідно знайти цілочисельний результат ділення виділеного числа на дільник. І тут ми знову виграємо в порівнянні з десятковою системою. Справа в тім, що число, яке підбирається, це обов'язково цифра, а цифри в нас тільки дві. Оскільки 1001 явно більше 101, то тут усе зрозуміло: це 1. Виконаємо крок операції.

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

Отже, залишок від виконаної операції 100. Це менше ніж 101, тому щоб виконати другий крок , необхідно дописати до 100 наступну цифру, це цифра 0. Тепер маємо наступне число:

1 0 0 1 0 1 1 1 1 0 1

-		1	0	1					1

1 0 0 0

1000 більше 101 тому на другому кроці ми знову допишемо в частку цифру 1 і одержимо наступне.

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

Після декількох ітерацій маємо наступне:

145

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

Отриманий залишок 10 менше 101, але в нас закінчилися цифри в діленому, тому 10 це остаточний залишок, а 1110 –це шукана частка.

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

а) 1101 * 110 б) 1010 * 10 г) 1011 * 11

д) 101011 * 101 е) 10010 * 1001

6.5ОЗНАКА ПЕРЕПОВНЕННЯ РОЗРЯДНОЇ СІТКИ ПРИ

АРИФМЕТИЧНИХ ОПЕРАЦІЯХ.

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

При алгебраїчному додаванні двох двійкових чисел з використанням додаткового (зворотного) коду для їхнього представлення ознакою переповнення розрядної сітки є наявність переносу в знаковий розряд суми при відсутності переносу з нього (додатне перепов-

146

нення). Аналогічно - наявність переносу зі знакового розряду суми при відсутності переносу в нього (від’ємне переповнення). Якщо і у знаковий, і зі знакового розряду суми є переноси чи переносів немає , то переповнення відсутнє. При додатному переповненні результат операції додатний, при від’ємному - від’ємний. Розглянемо додатне

та від’ємне переповнення:
а)			б)
0	101		1	011
+		+
0	101		1	011
1	010	1	0	110.

Приклад а) демонструє додатне переповнення, приклад б) – від’ємне.

Завдання для самостійної роботи:

а) 11001 + 101 б) 11001 + 11001 с) 1001 - 111 д) 10011 + 101 е) 11011 - 1111

ж) 11111 + 10011 з) 1101001011.011 – 101010111.01

6.6 ПРЕДСТАВЛЕННЯ ЦІЛИХ ЧИСЕЛ

Як вказувалось вище, що в мові C є базовий тип int для представлення цілих чисел зі знаком. Також можна використовувати модифікатори short та long для представлення цілих чисел зі знаком (і отримуємо типи short int чи просто short та long int чи скорочено long ) а також unsigned для представлення беззнакових цілих (утворюються типи unsigned int , unsigned short int та unsigned long int). Можна вико-

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

У пам'яті комп'ютера дані зберігаються в послідовно розташованих байтах. Для даних різних типів використовується різна кількість байт. Розглянемо наступну таблицю (один байт складає 8 біт).

Таблиця 1

147

Повна назва		Скорочена	назва	Розмір	в	Діапазон значень
типу		типу		байтах
Signed char		Char		1		від -128 до 127
Signed int		Signed,int		~
Signed	short	Short, Signed short		2		від -32768 до 32767
int		Long, Signed long		4		від -2 147 483 648 до
Signed	long	Unsigned char		1		2 147 483 647
int		Unsigned short		2		від 0 до 255
Unsigned		Unsigned long		4		від 0 до 65535
char		Unsigned		~		від 0 до 4 294 967
Unsigned						295
short int
Unsigned
long int
Unsigned int
~-розмір залежить від типу комп`ютера

Відмітимо, що розмір пам’яті для даних типу int, unsigned int визначається довжиною машинного слова, що є різною для різних комп’ютерів. Для 16-розрядних розмір машинного слова–2 байта, 32- х розрядних-4 байта.

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

За загальноприйнятими правилами, при представленні чисел зі знаком, крайній лівий біт старшого байта 0 використовується для представлення знака плюс і 1 - для мінуса.

Легко бачити, що при цьому самим маленьким від’ємним числом, що належить типу char, є число –128 - двійкове представлення 10000000, а найбільшим - число 127 (представлення 01111111). Зверніть увагу на наступне: якщо до числа 01111111 додати одиницю, то вийде 10000000, що означає наступне: 127+1=-128.

Отже, множину елементів типу char можна уявляти собі у вигляді згорнутого в кільце відрізка [ 128;127].

Відмітимо, що для елементів множини цілих чисел, що представляються типом char, не виконується властивість цілих чисел x 1 x . Нерозуміння цього факту може призвести до різних вкрай неприємних результатів.

148

Приведемо таблицю машинних значень діапазону цілих типів.

	Тип	Діапазон значень	Машинне представлення
	char	-128..127	10000000 …
			01111111
	short int	-32768..32767	00000000	10000000 …
			11111111	01111111
			00000000 00000000 00000000
	long int	-	10000000…
		2147483648..2147483647	11111111 11111111 11111111
			01111111
	unsigned char	0..255	00000000 …
			11111111
	unsigned	0..65535	00000000	00000000 …
	short int		11111111	11111111
			00000000 00000000 00000000
	unsigned long	від 0 до 4 294 967 295	00000000
	int		11111111 11111111 11111111
			11111111

6.7 ПРЕДСТАВЛЕННЯ ДІЙСНИХ ЧИСЕЛ.

На відміну від представлення цілих чисел, що відрізняється бсолютною точністю, з дійсними числами не все так просто. Для представлення дійсних чисел в мові С++ використовуються типи float, double, long double (у деяких реалізаціях мови long double відсутній).

Величина типу float займає 4 байти. З них 1 байт приділяється для знака, 8 біт для характеристики і 23 біта для мантиси. Відзначимо, що старший біт мантиси завжди дорівнює 1, тому він не заповнюється, у зв'язку з цим діапазон значень змінної з плаваючою крапкою приблизно дорівнює від 3.14E-38 до 3.14E+38.

Величина типу double займає 8 байт у пам'яті. Її формат аналогічний формату float. Біти пам'яті розподіляються в такий спосіб: 1 біт для знака, 11 біт для характеристики і 52 біта для мантиси. З врахуванням опущеного старшого біта мантиси діапазон значень дорівнює від

1.7E-308 до 1.7E+308.Дані типу long double займають 80 біт, 15 біт для характеристики і 64 для мантиси.Діапазон значень– від 3.4 x 10-

4932 до 1.1 x 10+4932

Таблиця 3

149

	Тип	Розмір	типу, Розмір	мантиси, Розмер	порядка,
		байт	біт	бит
	float	4	23	8
	double	8	52	11
	long	10	64	15
	double

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

Поширено два види представлення дійсних чисел: а) з порядком

	знак чис-			поря-		знак поряд-		манти-
	ла			док		ку		са
і б) з характеристикою.
		знак	чи-		характеристи-		мантиса
		сла			ка

Введення характеристики не вимагає виділення одного біту для знака порядку і спрощує виконання операцій порівняння (<,>,<=,>=) і арифметичних операцій над дійсними числами.

Найбільш розповсюдженим способом реалізації дійсних чисел у комп'ютері є використання представлення з характеристикою, що отримується з порядку додаванням такого зсуву, щоб характеристика була додатною. Нехай, наприклад, на характеристику виділяється 8 біт. У 8 розрядах вміщаються двійкові числа від 00000000 до 11111111 (від 0 до 255 в десятковій системі). Всього маємо 256 значень. Розумно ці значення порівну розподілити між від”ємними та додатніми значеннями порядку числа: від –127 до 128. Мінімальному значенню порядка повинно відповідати нульове значення характеристики. Отже, отримуємо зміщення, що дорівнює 127.

Таким чином, для обчислення істинного порядку числа можна використовувати наступну формулу:

150