МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
"Внутрішнє представлення в пам’яті комп’ютера статичних даних"
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 1
з дисципліни
" Програмування. Частина III.
Структури даних та алгоритми "
для студентів напряму
6.050102 “Комп’ютерна інженерія”
Львів – 2009
Методичні вказівки до лабораторної роботи "Внутрішнє представлення в пам’яті комп’ютера статичних даних" з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми" для підготовки студентів напряму 6.050102 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2009 – 27 с.
Укладач: Лисак Т.А., ст. викладач каф.ЕОМ
Відповідальний
за випуск: Мельник А.О., д-р техн. наук, проф.
Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ
Юрчак І.Ю., доцент кафедри САПР, к.т.н.
1. МЕТА РОБОТИ
Дослідження внутрішнього представлення в пам’яті комп’ютера даних статичної структури.
2. ТЕОРЕТИЧНІ ВІДОМОСТІ
2.1. Класифікація типів даних
Основна мета будь-якої програми полягає в обробці даних. Дані різних типів зберігаються в пам’яті комп’ютера і обробляються по-різному. Згідно з концепцією типів даних, кожний тип даних однозначно визначає:
множину значень, які може приймати змінна заданого типу;
операції та функції, які можна застосовувати до змінної заданого типу;
внутрішнє представлення змінної у пам'яті комп'ютера.
Нагадаємо, що пам'ять виділяється не для типу даних, а для розміщення змінних або констант певних типів.
В мові С++ розрізняють наступні категорії типів:
базові типи даних;
похідні типи даних.
Базові типи мають імена, які є ключовими словами мови. До базових типів відносяться: скалярні типи і порожній тип (void).
Скалярні типи діляться на цілочисельні і дійсні типи (float, double, long double). Логічний тип (bool), символьні (char, wchar_t) та цілі (short, int, long) типи даних відносяться до цілочисельних типів. Для них визначені всі операції роботи з цілими числами.
Похідні типи визначаються на основі базових типів. Похідні типи діляться на скалярні і структуровані (або агрегатні).
До скалярних похідних типів відносяться:
переліки (enum) ;
вказівники (ім'я_типу *);
посилання (ім'я_типу &).
До структурованих похідних типів відносяться:
масиви;
структури (struct);
об'єднання (union);
класи (class).
В структурах, об'єднаннях і класах можуть використовуватись бітові поля.
В мові С++ існує також чотири спеціфікатора типів, які можна використовувати разом із зазначеними базовими типами:
Спеціфікатори short (короткий) і long (довгий) застосовуються до цілих. У таких оголошеннях слово int можна опускати, що зазвичай й робиться. Найчастіше для представлення цілого, описаного з спеціфікатором short, виділяється 16 біт, із спеціфікатором long - 32 біта, а значенню типу int - або 16, або 32 біта.
Спеціфікатори signed (зі знаком) або unsigned (без знака) можна застосовувати до будь-якому цілочисельного типу. Вони вказують, як інтерпретується нульовий біт змінної, тобто, якщо зазначено ключове слово unsigned, то нульовий біт інтерпретується як частина числа, у противному випадку нульовий біт інтерпретується як знаковий. У випадку відсутності ключового слова unsigned змінна вважається знаковою.
2.2. Базові типи даних
Порожній тип
Порожній тип (void) синтаксично поводиться як базовий тип. Однак використовувати його можна тільки як частину похідного типу, оскільки об'єктів типу voіd не існує. Він використовується для того, щоб вказати, що функція не повертає ніякого значення, або як базовий тип для вказівників на об'єкти невідомого типу.
void f() // функція f не повертає ніякого значення
void* pv; // вказівник на объект невідомого типу
Логічний тип даних
Логічний тип (bool) характеризується двома значеннями даних: false (хибність) і true (істина). Змінні цього типу займають 1 байт у пам'яті комп'ютера. В мові C++ значення змінних типу int можна асоціювати з логічними значеннями: нулю відповідає значення false, всім іншим числам відповідає значення true.
В арифметичних і логічних виразах логічні значення перетворюються в цілі числа. Арифметичні та бітові логічні операції виконуються над перетвореними величинами. Якщо результат приводиться знову до логічного типу, то 0 перетворюється в false, а ненульове значення перетворюється в true.
Приклад 1.
void f()
{ bool x = true;
bool y = true;
bool a = 2*x+y; // Значення виразу 2*x+y дорівнює 3, тому змінна a
// отримує значення true. В пам’яті комп’ютера змінна a
} // буде зберігатись як наступна послідовність біт : 0000 0011
Символьні типи даних
Ідентифікатором символьного типу на мові програмування С++ є ключове слово char. Значеннями даних типу char є множина символів таблиці ASCII. У пам’яті комп’ютера дані цього типу зазвичай займають 1 байт. В цей байт записується порядковий номер символа в таблиці ASCII.
Таблиця символів ASCII наведена в Таблиці 1. В ній прийняті такі позначення: DEC – код в десятковій системі числення; HEX – код в шістьнадцятковій системі числення; CH – символ.
Таблиця 1
DEC
HEX
CH
DEC
HEX
CH
DEC
HEX
CH
DEC
HEX
CH
DEC
HEX
CH
DEC
HEX
CH
DEC
HEX
CH
DEC
HEX
CH
0
0
32
20
64
40
@
96
60
`
128
80
А
160
A0
а
192
C0
└
224
E0
р
1
1
☺
33
21
!
65
41
A
97
61
a
129
81
Б
161
A1
б
193
С1
┴
225
El
с
2
2
☻
34
22
“
66
42
B
98
62
b
130
82
В
162
A2
в
194
C2
┬
226
E2
т
3
3
♥
35
23
#
67
43
C
99
63
c
131
83
Г
163
A3
г
195
C3
├
227
E3
у
4
4
♦
36
24
$
68
44
D
100
64
d
132
84
Д
164
A4
д
196
C4
─
228
E4
ф
5
5
♣
37
25
%
69
45
E
101
65
e
133
85
Е
165
A5
е
197
C5
┼
229
E5
х
6
6
♠
38
26
&
70
46
F
102
66
f
134
86
Ж
166
A6
ж
198
C6
╞
230
E6
ц
7
7
•
39
27
'
71
47
G
103
67
g
135
87
З
167
A7
з
199
C7
╟
231
E7
ч
8
8
◘
40
28
(
72
48
H
104
68
h
136
88
И
168
A8
и
200
C8
╚
232
E8
ш
9
9
○
41
29
)
73
49
I
105
69
i
137
89
Й
169
A9
й
201
C9
╔
233
E9
щ
10
A
◙
42
2A
*
74
4A
J
106
6A
j
138
8A
К
170
AA
к
202
CA
╩
234
EA
ъ
11
B
♂
43
2B
+
75
4B
K
107
6B
k
139
8B
Л
171
AB
л
203
CB
╦
235
EB
ы
12
C
♀
44
2C
,
76
4C
L
108
6C
1
140
8C
М
172
AC
м
204
CC
╠
236
EC
ь
13
D
♪
45
2D
-
77
4D
M
109
6D
m
141
8D
Н
173
AD
н
205
CD
═
237
ED
э
14
E
♫
46
2E
.
78
4E
N
110
6E
n
142
8E
О
174
AE
о
206
CE
╬
238
EE
ю
15
F
☼
47
2F
/
79
4F
O
111
6F
o
143
8F
П
175
AF
п
207
CF
╧
239
EF
я
16
10
◙
48
30
0
80
50
P
112
70
p
144
90
Р
176
B0
░
208
D0
╨
240
F0
Ё
17
11
◄
49
31
1
81
51
Q
113
71
q
145
91
С
177
В1
▒
209
Dl
╤
241
Fl
ё
18
12
↕
50
32
2
82
52
R
114
72
r
146
92
Т
178
B2
▓
210
D2
╥
242
F2
Є
19
13
‼
51
33
3
83
53
S
115
73
s
147
93
У
179
B3
│
211
D3
╙
243
F3
є
20
14
¶
52
34
4
84
54
T
116
74
t
148
94
Ф
180
B4
┤
212
D4
╘
244
F4
Ї
21
15
§
53
35
5
85
55
U
117
75
u
149
95
Х
181
B5
╡
213
D5
╒
245
F5
ї
22
16
▬
54
36
6
86
56
V
118
76
v
150
96
Ц
182
B6
╢
214
D6
╓
246
F6
І
23
17
↨
55
37
7
87
57
W
119
77
w
151
97
Ч
183
B7
╖
215
D7
╫
247
F7
і
24
18
↑
56
38
8
88
58
X
120
78
x
152
98
Ш
184
B8
╕
216
D8
╪
248
F8
°
25
19
↓
57
39
9
89
59
Y
121
79
y
153
99
Щ
185
B9
╣
217
D9
┘
249
F9
•
26
1A
→
58
3A
:
90
5A
Z
122
7A
z
154
9A
Ъ
186
BA
║
218
DA
┌
250
FA
·
27
1B
←
59
3B
;
91
5B
[
123
7B
{
155
9B
Ы
187
BB
╗
219
DB
█
251
FB
√
28
1C
∟
60
3C
<
92
5C
\
124
7C
|
156
9C
Ь
188
BC
╝
220
DC
▄
252
FC
№
29
ID
(
61
3D
=
93
5D
]
125
7D
}
157
9D
Э
189
BD
╜
221
DD
▌
253
FD
¤
30
1E
▲
62
3E
>
94
5E
^
126
7E
~
158
9E
Ю
190
BE
╛
222
DE
▐
254
FE
■
31
IF
▼
63
3F
?
95
5F
_
127
7F
159
9F
Я
191
BF
┐
223
DF
▀
255
FF
Всі символи таблиці ASCII пронумеровані від 0 до 255, а кожному номеру відповідає 8-розрядний двійковий код від 00000000 до 11111111. Цей код і є порядковим номером символу в двійковій системі числення.
Приклад 2.
За системою ASCI: символ ‘O’ має порядковий номер .
Отже, цей символ в пам’яті комп’ютера буде представлений як послідовність 0100 1111.
Принцип послідовного кодування алфавіту полягає в тому, що в кодовій таблиці ASCII латинські букви (прописні та строчні) розташовуються в алфавітному порядку. Розташування цифр також впорядковано по зростанню значень.
Стандартними в таблиці ASCII є тільки перші 128 символів, тобто символи з номерами від нуля (двійковий код 00000000) до 127 (01111111). Сюди входять букви латинського алфавіту, цифри, розділові знаки, дужки та деякі інакші символи. Решта 128 кодів, починаючи від 128 (двійковий код 10000000) і завершуючи 255 (11111111), використовуються для кодування букв національних алфавітів, символів псевдографіки та наукових символів.
Оскільки значенню char відводиться 8 бітів, то unsigned char має значення в діапазоні від 0 до 255, a signed char – від -128 до 127, але тільки величини від 0 до 127 мають символьний еквівалент. Чи є значення типу просто char знаковими чи беззнаковими, залежить від реалізації, але в будь-якому випадку коди друкованих символів завжди є додатніми.
Таблиця 2
Тип
Розмір пам'яті в байтах 16 (32)
Діапазон значень
[signed] char
1 (1)
-128..127
unsigned char
1 (1)
0..255
Для представлення символів українського алфавіту, спеціфікатор типу даних повинен мати вигляд unsigned char, тому що коди українських літер перевищують величину 127.
Протягом довгого часу поняття "байт" і "символ" були майже синонімами. Однак, з часом, стало зрозуміло, що 256 різних символів – це не так і багато. Математикам необхідно використовувати в формулах спеціальні математичні знаки, перекладачам необхідно створювати тексти, де можуть зустрічатися символи з різних алфавітів, економістам необхідні символи валют ($, £, ¥). Для вирішення цих проблем була розроблена універсальна система кодування текстової інформації – Unicode. В цьому кодуванні для кожного символу відводиться не один, а два байти, тобто шістнадцять біт. Таким чином, доступно 65536 (216) різних кодів. Цього вистарчить на латинський алфавіт, кирилицю, іврит, африканські і азіатські мови, різні спеціальні символи: математичні, економічні, технічні і багато іншого. Головний недолік системи Unicode полягає в тому, що всі тексти в цьому кодуванні стають в два рази довшими. В даний час стандарти ASCII і Unicode мирно співіснують.
Символьна константа може мати префікс L (наприклад, L'a'), який означає спеціальний розширений символьний тип (wchar_t), що застосовується для зберігання символів національних алфавітів, якщо вони не можуть бути представлені звичайним однобайтовим типом char, наприклад, Unicode. Розмір цього типу залежить від реалізації; як правило, він відповідає типу short і займає 2 байти пам'яті.
Символьні константи (символьні літерали) можна представляти як:
клавіатурні: '1','s','Y' – записуються як символи в одинарних лапках;
кодові: '\n','\\','\?', які використовуються для представлення деяких керуючих символів та символів-розділювачів – записуються як escape-послідовності (вони починаються з символу зворотної косої риски). Перелік кодових символьних літералів наведено в Таблиці 3.
Таблиця 3
Назва
С++
новий рядок
\n
горизонтальна табуляція
\t
забій
\b
вертикальна табуляція
\v
повернення каретки
\r
прогін аркуша
\f
дзвінок
\a
зворотна коса риса
\\
питання
\?
одиночні лапки
\'
подвійні лапки
\"
Не дивлячись на свій зовнішній вигляд, це одиночні символи.
3) кодові числові: '\0','\x5C','\124', які використовуються для представлення будь-яких ASCІІ-кодів символів – записуються у вигляді однієї, двох або трьох вісімкових цифр (з \ перед ними) або шістнадцятковим числом (з \х перед ним). На кількість шістнадцяткових цифр в послідовності немає обмежень. Послідовність вісімкових або шістнадцяткових цифр закінчується першим символом, який не є відповідно вісімковою або шістнадцятковою цифрою. Приклади таких представлень наведені в Таблиці 4.
Таблиця 4
Вісімкова
Шістнадцяткова
Десяткова
ASCІІ
'\7'
'\x7'
7
дзвінок
'\60'
'\x30'
48
'0'
'\062'
'\x32'
50
'2'
'\137'
'\x005f'
95
'_'
Цілі типи даних
Типи short, іnt і long призначені для представлення цілих чисел.
Цілі типи можуть бути знаковими (sіgned) і беззнаковими (unsіgned). В знакових типах самий лівий біт використовується для зберігання знака числа (0 – плюс, 1 – мінус). Решта бітів містять числове значення. В беззнакових типах всі біти використаються для числового значення. За замовчуванням всі цілочисельні типи вважаються знаковими.
Цілі типи розрізняються діапазоном значень, які можуть приймати цілочисельні змінні і розміром області пам'яті, виділеної під цю змінну, а конкретні розміри перерахованих типів залежать від конкретної реалізації. Так, представлення в пам'яті і область значень для типів іnt і unsіgned іnt чітко не визначені в мові С++. За замовчуванням розмір іnt (зі знаком і без знака) відповідає реальному розміру цілого на даній машині. Наприклад, на 16-ти розрядній машині тип іnt завжди займає 16 розрядів або 2 байта. На 32-х розрядній машині тип іnt завжди займає 32 розряди або 4 байта. Таким чином, тип іnt буде еквівалентним типам short іnt або long іnt залежно від реалізації. Аналогічно, тип unsіgned іnt еквівалентний типам unsіgned short або unsіgned long. Перелік типів наведено в Таблиці 5.
Оскільки, розміри типів іnt і unsіgned іnt є змінними, то програми, що залежать від специфіки розмірів іnt і unsіgned іnt можуть бути непереносимими. Переносимость коду можна поліпшити шляхом включення у вираз sіzeof операції.
Таблиця 5
Тип
Розмір пам'яті
в байтах 16 (32)
Діапазон значень
[signed] short [int]
2
-215 .. 215-1 = -32768 .. 32767
unsigned short [int]
2
0 .. 216-1 = 0 .. 65535
[signed] int
2 (4)
-215 .. 215-1 (-231 .. 231-1)
unsigned [int]
2 (4)
0 .. 216-1 (0 .. 232-1)
[signed] long [int]
4
-231 .. 231-1 = -2 147 483 648 .. 2 147 483 647
unsigned long [int]
4
0 .. 232-1 = 0 .. 4 294 967 295
Літерали цілих типів можна записати в десятковому, вісімковому або шістнадцятковому видах, наприклад: 20 (десяткове), 024 (вісімкове), 0х14 (шістнадцяткове). Якщо літерал починається з 0, він трактується як вісімковий, якщо з 0х або 0Х, то як шістнадцятковий. Звичний запис розглядається як десяткове число. За замовчуванням всі цілі літерали мають тип sіgned іnt. Можна явно визначити цілий літерал, що має тип long, приписавши в кінці числа букву L (використається як прописна L, так і рядкова l, однак для зручності читання не слід вживати рядкову: її легко переплутати з 1). Буква U (або u) в кінці числа визначає літерал як unsіgned іnt, а дві букви – UL або LU – як тип unsіgned long. Наприклад: 25u, 1015UL, 2L, 7Lu
Записи вісімкової і шістнадцяткової констант можуть завершуватися буквою L (для вказівки на тип long) і U (якщо потрібно показати, що константа беззнакова). Наприклад, константа 0XFUL має значення 15 і тип unsigned long.
Внутрішнє представлення змінної цілого типу — ціле число у двійковому коді. Згідно формату IEEE всі додатні цілі числа зберігаються в пам'яті комп'ютера в прямому коді, а всі від'ємні – в доповняльному коді. Цілі числа зберігаються в пам'яті комп'ютера у зворотньому порядку розміщення байт числа.
Приклад 3.
Додатнє число 25 типу int в пам'яті комп’ютера зберігається в прямому двійковому коді і займає 4 байти: 0000 0000 0000 0000 0000 0000 0001 1001
В пам’яті комп’ютера цілі числа зберігаються у зворотному порядку розміщення байт числа:
0001 10001 0000 0000 0000 0000 0000 0000
Результат в 16- ковій системі числення: 19 00 00 00.
Приклад 4.
Від'ємне число -3500 типу long int в пам'яті комп’ютера зберігається в доповняльному двійковому коді і займає 4 байти: - 350010 = - DAC16 = - 1101 1010 11002
0000 0000 0000 0000 0000 1101 1010 1100 - прямий код;
1111 1111 1111 1111 1111 0010 0101 0011 - обернений код;
+ 1
1111 1111 1111 1111 1111 0010 0101 0100 - доповняльний код;
F F F F F 2 5 4 - в 16- ковій системі числення
В пам’яті комп’ютера зберігається у зворотному порядку розміщення байт числа:
0101 0100 1111 0010 1111 1111 1111 1111
Результат в 16- ковій системі числення: 54 F2 FF FF.
Дійсні типи даних
Дійсні константи записуються у двох формах – з фіксованою десятковою крапкою або в експонентному виді. В першому випадку крапка використовується для поділу цілої і дробової частин константи. Як ціла, так і дробова частини можуть бути відсутніми (наприклад 1.2, 0.725, 1., .35, 0.). В трьох останніх випадках відсутня або дробова, або ціла частина. Десяткова крапка повинна обов'язково бути присутньою, інакше константа буде вважатись цілою.
Експонентна форма запису дійсної константи містить знак, мантису і десятковий порядок (експоненту). Мантиса – це будь-яка додатня дійсна константа у формі з фіксованою крапкою або цілою константою. Порядок вказує степінь числа 10, на яку домножується мантиса. Порядок відокремлюється від мантиси буквою 'E' або 'e' (від слова exponent). Порядок може мати знак плюс або мінус, у випадку додатнього порядку знак плюс можна опускати. Наприклад:
1.5e+6 - константа еквівалентна 1500000.0
1e-4 - константа еквівалентна 0.0001
-.75E3 - константа еквівалентна -750.0
У мові С++ дійсні типи або типи з рухомою комою представляються трьома розмірами, що характеризують точність представлення дійсних чисел:
float – одиничної точності;
double - подвійної точності;
long double – розширеної точності (у деяких реалізаціях тип long double може бути відсутній)
Константи з рухомою комою мають за замовчуванням тип double. Саме він є найбільш природнім для комп'ютера. У програмуванні треба по можливості уникати типу float, тому що його точність недостатня, а процесор однаково при виконанні операцій перетворить його в тип double. Один з випадків, де застосування типу float виправдане – тривимірна комп'ютерна графіка.
Можна явно вказати тип константи за допомогою суфіксів F, f (float) і L, l (long). Наприклад, константа 2E+6L буде мати тип long double.
В пам'яті комп'ютера змінна типу float займає 4 байти, в яких один біт виділяється під знак, 8 – під порядок, 23 – під мантису.
Розряди мантиси включають один розряд цілої частини, що завжди дорівнює одиниці, і фіксовану кількість розрядів дробової частини. Оскільки старший двійковий розряд мантиси завжди дорівнює одиниці, зберігати його необов'язково, і у двійковому коді він відсутній. Фактично двійковий код зберігає тільки розряди дробової частини мантиси. Отже, насправді, у типу float мантиса містить 24 розряди, але старший розряд завжди дорівнює одиниці, тому зберігати його не потрібно.
Тип double займає 8 байт, у яких один розряд виділяється під знак, 11 – під порядок, 52 – під мантису. Насправді в мантисі 53 розряди, але старший завжди дорівнює одиниці і тому не зберігається.
Тип long double займає 10 байт, в яких один розряд виділяється під знак, 15 – під порядок, інші 64 – під мантису. Записуються всі 64 розряди мантиси разом зі старшою одиницею.
Оскільки порядок може бути додатній і від'ємний, у двійковому коді він зберігається в зміщеному виді: до нього додається константа, яка рівна абсолютній величині максимального по модулю від'ємного порядку. У випадку типу float вона дорівнює 127, у випадку double – 1023, long double – 16383. Таким чином, максимальний по модулю від'ємний порядок представляється нульовим кодом.
Дійсні числа зберігаються в пам'яті комп'ютера у зворотньому порядку розміщення байт числа.
Таблиця 6
Назва
типу
Іденти-фікатор
Діапазон значень
Внутрішній формат
( s - знак, e - експонента,
m - мантиса)
Значення числа
Розмір пам’яті в байтах
Дійсне одинарної точності
float
від 3.410-38
до 3.41038
1 біт 8 біт 23 біта
s
e
m
(-1)S1,m2e -127
4
Дійсне подвійної точності
double
від 1.710-308
до 1.710308
1 біт 11 біт 52 біта
s
e
m
(-1)S1,m2e –1023
8
Дійсне підвищеної точності
long double
від 3.410-4932
до 3.4104932
1 біт 15 біт 1біт 63 біта
s
e
1
m
(-1)S1,m2e -16383
10
Приклад 5.
Розглянемо, як в пам'яті комп’ютера зберігається додатнє число 649,1989 типу float .
Перевід цілої частини:
⇒ 649 10 = 289 16
Перевід дробової частини:
0, 1989 * 16 = 3,1824
0, 1824 * 16 = 2,9184
0, 9184 * 16 = 14,6944 (1410 = E16)
0, 6944 * 16 = 11,1104 (1110 = B16)
⇒ 0,1989 10 = 0,32EB 16
Отже: 649,1989 10 = 289,32EB 16 = 0010 1000 1001 , 0011 0010 1110 1011 2
Нормалізація: 001 , 0 1000 1001 0011 0010 1110 1011 2 * 21001
Заокруглення:
1 , 0 1000 1001 0011 0010 1110 10│11
+ 1
1 , 0 1000 1001 0011 0010 1110 11
Визначення мантиси: m=0 1000 1001 0011 0010 1110 11
Визначення зміщеного порядку: е = 12710 + 910 = 136 10 = 88 16 = 1000 1000 2
Інший спосіб: 12710 = 111 1111 2
+ 1001
1000 1000 2
Визначення знакового розряду: s=0 (бо число додатнє).
Схема внутрішнього представлення:
s
e
m
1 біт
8 біт
23 біт
Зборка за схемою:
s
e
m
0
1000 1000
0 1000 1001 0011 0010 1110 11
В 16- ковій системі числення: 0100 0100 0010 0010 0100 1100 1011 10112 = 44 22 4С BB 16
В пам’яті комп’ютера буде зберігатися у зворотному