ПАСКАЛЬ:ПОДАННЯ ЧИСЕЛ ТА ІНШИХ ЗНАЧЕНЬ

1. Позиційні системи числення

1.1. Запис натуральних чисел

Система числення – це система запису, або позначення, чисел. Найдосконалішими системами числення виявилися позиційні. У цих системах число, позначене цифрою, залежить від її місця (позиції) в записі числа. Наприклад, звичні нам записи 13 і 31 у десятковій системі складаються з однакових цифр (значків "1" і "3"), але позначають різні числа 1 10+3 і 3 10+1.

Позиційна система числення з основою P (P-кова) має P цифр C₀, C₁, … , C_P-1, що звичайно позначають натуральні числа від 0 до P-1. Ці записи та позначені ними числа – значення цих записів – називаються однорозрядними P-ковими.

Цифри десяткової системи 0, 1, 2, … , 9 називаються арабськими, хоча й були запозичені арабами в індусів.

У програмуванні широко застосовується шістнадцяткова система, в якій перші 10 цифр арабські, а наступні шість – A, B, C, D, E, F. Вони позначають числа, десятковий запис яких 10, 11, 12, 13, 14, 15 відповідно.

Число P у P-ковій системі позначається дворозрядним записом C₁C₀, число P+1 – записом C₁C₁ тощо до P P-1. Наприклад, 10, 11, ... , 99 у десятковій системі, 10, 11 у двійковій, 10, 11, … , 1F, 20, … , FF у 16-ковій. Число P P позначається вже трьома цифрами C₁C₀C₀, далі йде C₁C₀C₁ тощо. Наприклад, 100, 101, … , 999 у десятковій системі, 100, 101, 110, 111 у двійковій, 100, 101, … , FFF у 16-ковій. І взагалі, запис вигляду

(a_ka_k-1 a₁a₀)_P

позначає в P-ковій системі число, що є значенням полінома

a_k P^k+a_k-1 P^k-1+ +a_1 P+a₀.

Наприклад, двійковий запис (10011)₂ позначає число, яке в десятковому записі має вигляд 1 2⁴+0 2³+0 2²+1 2¹+1 2⁰=19. 16-ковий запис (1BC)₁₆ позначає десяткове 1 16²+11 16+12=444.

Найправіша цифра в запису числа позначає кількість одиниць і називається молодшою, найлівіша – кількість чисел P^k і називається старшою.

Ми звикли до десяткового подання чисел, і саме воно, головним чином, використовується в Паскаль-программах, але в комп'ютері числа, як правило, подаються в двійковій системі. Таким чином, виникає необхідність створювати двійкове подання числа за його десятковим записом і навпаки. Зауважимо до речі, що такі перетворення записів чисел з однієї системи в іншу здійснюються при виконанні процедур читання і запису readln і writeln.

За P-ковим записом (a_ka_{k-1 } a₁a₀)_P натурального числа N можна побудувати десяткове подання, обчисливши значення полінома за допомогою операцій множення та додавання в десятковій системі. Саме цим ми займалися двома абзацами вище.

Розглянемо, як одержати за натуральним числом N цифри його P-кового подання. Нехай N=(a_ka_{k-1 } a₁a₀)_P, і кількість цифр k+1 невідомі. Запишемо подання в такому вигляді:

N = a_k P^k+a_k-1 P^k-1+ +a_1 P+a₀ = (…(a_k P+a_k-1) P+ +a₁) P+a₀.

Звідси очевидно, що значенням a₀ є N mod P, a₁ – (N div P) mod P тощо. Таким чином, якщо поділити N на P у стовпчик, то остача від ділення буде значенням молодшої цифри. Потім можна так само поділити на P частку від першого ділення – остача буде виражати кількість "P-кових десятків" тощо поки остання частка не виявиться менше P. Вона й буде значенням старшої цифри. При P>10 ще треба перетворити числа більше 9 у цифри. Наприклад, одержимо цифри 16-кового подання десяткового числа 1022:

_1022 | 16 _63 | 16

96 63 48 3

_62 15

48

14

Виділені 14, 15 і 3 – це кількості 16-кових "одиниць", "десятків" і "сотень" відповідно. Позначимо їх 16-ковими цифрами E, F і 3 відповідно та одержимо запис 3FE.

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

while N > 0 do

begin

d:= N mod P ;

за значенням d побудувати P-кову цифру;

N := N div P

end

Якщо позначити цифрами A, B, … , Z числа від 10 до 35, то з використанням відповіді до задачі 10.5 за цим алгоритмом можна утворити подання чисел аж до 36-кової системи.

Для використання ще більших основ систем числення треба додатково розширити алфавіт цифр.

 

1.2. Дробові числа

P-кове подання чисел, менших 1, має вигляд 0.a_-1 a_{-2 } , де a_-i – P-кові цифри. Цей запис позначає дійсне число – значення виразу

a_-1 P^-1+a_-2 P^-2+ 

Наприклад, (0.1101)₂ позначає десяткове

1 2^-1+1 2^-2+0 2^-3+1 2^-4=0.5+0.25+0.0625=0.8125;

(0.21)₃ – 2 3^-1+1 3^-2=0.777…=0.(7); (0.BC)₁₆ – 11 16^-1+12 16^-2=0.734375.

За P-ковим поданням, у якому задано r старших цифр, десятковий запис числа утворюється обчисленням значення многочлена

a_-1 P^-1+a_-2 P^-2+ … +a_-r P^-r.

Нагадаємо, що якщо основа P має прості дільники, відмінні від 2 і 5, то число зі скінченним P-ковим записом зображується нескінченним, але періодичним десятковим дробом. Якщо ж простими дільниками P є тільки 2 і 5, то й десятковий дріб скінченний.

Розглянемо, як за дійсним значенням V одержати цифри його P-кового подання. Нехай V=(0.a_-1a_-2…)_P. Запишемо подання в такому вигляді:

V=P^-1 (a_-1+P^-1 (a_-2+ )).

Тоді V P=a_-1+P^-1 (a_-2+ ), звідки очевидно, що a_-1= V P , і P^-1 (a_-2+ ) = {V P}, де  V P та {V P} позначають цілу та дробову частини V P. Помноживши {V P} на P і узявши цілу частину, одержимо a_-2 тощо. Наприклад, при V=0.75, P=3 одержимо

a_-1= 0.75 3 =2, {0.75 3}=0.25, a_-2= 0.25 3 =0, {0.25 3}=0.75 тощо.

Таким чином, трійковим поданням 0.75 буде нескінченний періодичний дріб (0.(20))₃.

Маючи дійсне значення V, V<1, можна одержати r перших цифр його P-кового подання, виконавши алгоритм

for i := 1 to r do

begin

V := V*P;

d:= trunc ( V ) ;

за значенням d побудувати P-кову цифру;

V := V - trunc ( V )

end.

1.3. "1+1=10, 5 8=28"

Якщо додати 1 і 1, то одержимо 2. Але в двійковій системі це 10, тобто в двійковій системі 1+1=10. При додаванні в стовпчик це означає суму 0 і перенос 1 у наступний розряд. Наприклад, додамо в стовпчик 3 і 6 у двійковій системі:

+ 11

110

1001

У десятковій системі 10+13=23. Те ж саме в шістнадцятковій виглядає як A+D=17. Взагалі, додаючи дві або більше P-кові цифри, у результаті одержуємо

(їх сума) mod P

із переносом (їх сума) div P. Наприклад, у шістнадцятковій системі

+ 9D

FAE

104B

(неважко перевірити, що при додаванні в стовпчик D+E=1B, 1+9+A=14, 1+F=10).

Усі вчаться в школі не тільки додавати, але й множити. Коли ми множимо число в десятковій системі у стовпчик на число, записане одною цифрою X, то обчислюємо добуток чергової цифри числа та X. Остачу від ділення цього добутку на 10 додаємо до переносу від попереднього розряду й одержуємо суму S. Молодшу цифру S, тобто остачу від ділення на 10, записуємо в результат, а старшу, тобто S div 10, запам'ятовуємо як перенос. І так рухаємося від молодшої цифри співмножника до старшої. Знайомо, чи не так?

У P-ковій системі відбувається те ж саме, тільки остачі беруться від ділення не на 10, а на P. Наприклад, у шістнадцятковій системі 5 8 при діленні на 16 дає остачу 8 і частку 2, тобто 5 8=28. У вісімковій системі

 1234

7

11102

(4 7 при діленні на 8 дає 2 в остачі й 3 у переносі, 3 7+3 дає 0 і 3 тощо).

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

 77

123

275

176

77 .

12155

Аналогічно в шістнадцятковій системі

 FE

20A

9EC

1FC .

205EC

 

Задачі

1. За заданими P та P-ковими записами чисел N указати їх десяткове подання:

а) P = 16, N = F1, FF, FFFE;

б) P = 8, N = 377, 1200;

в) P = 2, N = 1000, 1111, 11111111, 100000000.

г) P=36, N=ZY, 100 (36-кові цифри A, B,  , Y, Z позначають десятковi числа 10, 11,  , 34, 35 відповідно).

2. За десятковим записом чисел 32, 48, 100, 255, 640, 1024, 32767 указати їх 2-, 8-, 16-кові подання.

3. * Записати P-кове подання десяткових дробів d, де

а) d = 0.5, P = 2, 3, 5, 8, 16, 20;

б) d = 0.1, P = 2, 3, 5, 8, 16, 20.

4. * За основами P та P-ковими записами дробів указати їх десяткове подання:

а) P = 2; 0. 0001; 0. 1111; 0. 11111111;

б) P = 3; 0. 001; 0.22; 0.11;

в) P = 16; 0.1; 0. FF; 0.8; 0. (7).

5. Написати процедуру друкування цифр P-кового запису числа N, де 1 < P < 37,

а) N типу integer (цифри друкуються у зворотному порядку);

б) N типу integer (цифри друкуються у прямому порядку);

в) N має тип real, N<1 (друкується не більше, ніж R цифр дробової частини, де 0<R<80).

Уважати, що за P=36 числа від 10 до 35 позначено відповідно літерами від A до Z.

6. Означити таблиці додавання та множення однорозрядних P-кових чисел при P=2, 4, 8, 16. Написати програму друкування таких таблиць за P від 2 до 20.

7. Написати програму друкування таблиці символів, їх двійкових, шістнадцяткових та десяткових номерів.

2. Внутрішнє подання даних стандартних типів

2.1. Біт, байт та інші

У комп'ютері числа зберiгаються та обробляються в двiйковiй системі числення. Двійкова цифра 0 або 1 відображається станом елемента пам'яті, який вважається неподільним і називається бiтом. Послідовність із 8 бітів називається байтом. Байт своїми станами відображає 2⁸=256 комбінацій із 0 та 1, а саме:

00000000

00000001

^

11111110

11111111

Множині цих комбінацій можна взаємно однозначно поставити у відповідність деякі множини значень: цілі числа від -128 до 127, або числа від 0 до 255, або пари 16-кових цифр, або символи від chr(0) до chr(255) чи якісь інші множини з 256 елементів.

У двох сусідніх байтах подаються 2^8 2⁸=65536 комбінацій із 0 та 1. Їм взаємно однозначно ставляться у відповідність цілі числа від 0 до 65535, або числа від -32768 до 32767 чи інші множини з 65536 елементів.

Аналогічно чотири сусідні байти відображають (2⁸)⁴=4294967296 комбінацій із 0 та 1, яким зiставляються числа від 0 до 4294967295, або числа від -2147483648 до 2147483647 чи інші множини з 4294967296 елементів.

Два байти утворюють одиницю пам'яті, яка називається словом. Іноді таке слово називається напівсловом, а словом – послідовність із чотирьох байтів.

Послідовність із 1024 байтів утворює одиницю виміру розмірів пам'яті комп'ютера. Цю одиницю позначають Kбайт, проте це "K" – латинська літера, що читається "кей" і позначає не тисячу, а 1024.

Послідовність із 1K Kбайтів, тобто 1048576 байтів, називається Mбайтом. Ці дві одиниці у світі програмістів і користувачів часто не зовсім точно називають відповідно "кілобайт" і "мегабайт", хоча це зовсім не тисяча і не мільйон байтів. До речі, 1Гбайт, хоча й читається "гігабайт", позначає не мільярд, а 1073741824 байти.

2.2. Подання цілих чисел, символів та бульових значень

Бульовi значення false та true подаються, як правило, в одному байтi комбінаціями відповідно 00000000 та 00000001.

Символи від chr(0) до chr(255) зображаються в одному байтi комбінаціями з нулів та одиниць відповідно від 00000000 до 11111111. Наприклад, символ chr(32), або ' ' (пропуск), зображається як 00100000, символ chr(48), або '0', – як 00110000 тощо.

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

7 … 0	…	7 … 0	7 … 0
8N-1 …		15 … 8	7 … 0

Беззнаковi числа займають певну кількість N байтiв, яка задає дiапазон (множину) цих чисел від 0 до 2^8N-1. Найчастiше N=1, 2 або 4, і діапазони чисел – від 0 до відповідно 255, 65535 та 4294967295. Байти записуються від молодших до старших справа наліво та нумеруються від 0 до N-1. Біти всередині байтiв так само записуються від молодших до старших справа наліво й нумеруються від 0 до 7 (рис. 11.1). Усього в N байтах є 8N бітів, які нумеруються справа наліво від 0 до 8N-1. Біти з номерами 8N-1,  , 8N-8 утворюють старший байт (він ліворуч), а з номерами 7,  , 0 – молодший (праворуч). Комбінація бітів x_8N-1,  , x₀ зображає в двійковій системі число

x_8N-1 2^8N-1+ x_1 2+x₀.

Наприклад, комбінація 00 00 задає число 0, комбінація 00 01 – "один", 00 10 – "два", 11 11 – число 2^8N-1.

Таблиця 11.1
число	код
28N-1 - 1	01 11
28N-1 - 2	01 10
	
1	00 01
0	00 00
-1	11 11
-2	11 10
	
-28N-1 + 1	10 01
-28N-1	10 00

Знаковi числа займають ті самі N , тобто 1, 2 або 4 байти. Найстарший біт зображає знак числа: 0 – знак '+', 1 – знак '-'. Додатні числа подаються так само, як i беззнакові, лише за рахунок знакового біта дiапазон їх менший – від 0 до 2^8N-1-1. За N=1, 2 або 4 це відповідно 127, 32767 та 2147483647. Таке подання називається прямим кодом. Наприклад, прямим кодом максимального цілого є 011 1.

Від'ємні числа подаються в коді, названому додатковим. Для від'ємного числа A він позначається D (A) й утворюється так:

1) за прямим кодом числа |A| заміною всіх 0 на 1 та всіх 1 на 0 будується обернений код R(A);

2) за R(A) як беззнаковим цілим числом обчислюється D(A)=R(A)+1.

Очевидно, що D(A)=R(|A|-1). Наприклад, побудуємо двобайтовий додатковий код числа –144. Прямим двобайтовим кодом числа 144 буде

0000'0000'1001'0000

(апострофи записано для наочності), оберненим –

1111'1111'0110'1111.

До нього додається 1:

1111'1111'0110'1111

1

1111'1111'0111'0000,

і ми одержуємо додатковий код числа -144. Він є також оберненим кодом числа -143.

За додатковим кодом від'ємне число "відновлюється" у зворотному порядку:

1) D(A) вважається беззнаковим цілим; обчислюється R(A)=D(A)-1;

2) код, обернений до R(A), є прямим кодом числа | A |.

Той самий результат можна дістати, якщо

1) побудувати код R(D(A)), обернений до D(A);

2) до R(D(A)) як до беззнакового додати 1.

Відповідність знакових цілих чисел та їх кодів наведено в табл. 11.1. Як бачимо, від'ємних чисел на одне більше, ніж додатних.

Елемент X довільного типу-переліку подається як беззнакове цiле число ord(X).

2.3. Принципи подання дійсних чисел

Дiйснi числа в більшості комп'ютерів подаються в N=4, 6, 8 або 10 байтах, поділених на поля (послідовності бітів):

<знак><порядок><мантиса>.

Поле <знак> має довжину 1, а довжини двох інших позначимо d і r відповідно. Зрозуміло, що 1+d+r=8N. Нехай s, e, m – значення цих полів як беззнакових цілих. Вони подають:

s = 0 – знак '+', s = 1 – знак '-';

e – його порядок t = e - (2^d-1-1);

m – мантису (дробову частину) m₁ = m 2^–r.

За значень e, відмінних від крайніх значень 0 та 2^d-1, поля <знак><порядок><мантиса> задають число, що є значенням виразу

(-1)^s (1+m₁) 2^t (11.2)

Оскільки 1 1+m₁<2, то кажуть, що число подається в нормалiзованому виглядi. Показник t називається справжнім порядком числа, а e – "зсуненим" (він на 2^d-1-1 більше від справжнього). Отже, значення e від 1 до 2^d-2 задають справжні порядки t від 1-(2^d-1-1)=2-2^d-1 до 2^d-2-(2^d-1-1)=2^d-1-1.

Наприклад, нехай d=5, r=10, що задає двобайтове подання. Зсув порядку 2^5-1-1=2⁴-1. Розглянемо зображення числа -12.375:

-12.375 = (-1100.011)₂ = (-1.100011)_2 2³ ,

тобто t=3, m₁=0.100011. Звідси s=1, e=3+(2⁴-1)=18=(10010)₂, m=1000110000, і число подається послідовністю бітів 1'10010'1000110000. Тут для наочності поля відокремлено апострофами.

Послідовність бітів 0'00001'0000000000 подає мінімальне додатне число, зображуване за d=5, r=10:

(1 + 0) 2^1-24+1 = 2^-14.

Наступним числом, що подається як 0'00001'0000000001, буде

(1+2^-10)  2^1-24+1=2^-14+2^-24.

Послідовність бітів 0'11110'11111111111 подає максимальне число

(1+(2¹⁰-1) 2^-10) 2^25-2-24+1 = (2-2^-10) 2¹⁵ =2¹⁶ - 2⁵ = 65504.

Попереднє перед ним число має подання 0'11110'11111111110 і є

(1+(2¹⁰-2) 2^-10) 2^25-2-24+1 = (2-2^-9) 2¹⁵ =2¹⁶ - 2⁶ = 65472.

Як бачимо, різниця між двома сусідніми числами міняється від 2^-24 до 2⁵=32.

За e=0 незалежно від s і m подається число 0. За e=2^d-1 подання числа використовуєтьсся спеціальним чином, про що ми говорити не будемо (докладніше про це див., наприклад, [Григ]).

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

Задачі

8. Нехай a і b – імена змiнних бульового типу. Довести еквівалентнiсть виразів у наступних парах:

а) a <= b та not a or b; б) a < true та not a.

9.* Указати внутрішнє подання символів, заданих виразами:

а) chr(0), chr(48), chr(57), chr(13), chr(10), chr(65), chr(97);

б) 20h, 30h, 1Ah, 1Bh,

де суфікс "h" указує на шістнадцятковий запис.

10. Написати програму, яка для комп'ютера з невідомою системою подання чисел дозволяє визначити максимальне та мінімальне цілі типу integer.

11.* Указати двобайтовий додатковий код чисел -1, -8, -9, -32767, -32768.

12.* Нехай при додаваннi та відніманнi чисел типу integer перенос із старшого розряду стає змістом знакового розряду, а перенос із знакового розряду втрачається. Чому дорівнює значення виразу:

а) maxint + 1; б) minint - 1,

де maxint та minint позначають максимальне та мінімальне числа типу integer?

13.* Обчислити мінімальне та максимальне за модулем скінченні дійсні числа, що подаються в

а) 4 байтах за d = 8, r = 23;

б) 8 байтах за d = 11, r = 52;

в) 10 байтах за d = 16, r = 63.

14. Нехай d і r з описання подання дійсних чисел невідомі. Написати програму

а) обчислення d і r;

б) друкування виразів, що задають мінімальне та максимальне додатні числа типу real;

в) друкування виразу різниці між двома сусідніми зображуваними числами з відрізка [2ⁱ; 2ⁱ⁺¹] за допустимих значень i.

3. Цілі та дійсні типи мови Турбо Паскаль

Базовий тип цілих integer утворено цілими, які займають 2 байти в знаковому поданні. Тепер уже зрозуміло, чому їх діапазон від -32768 до 32767. Крім цього типу, в мові Турбо Паскаль є ще кілька типів для подання цілих. Укажемо їх імена, спосіб (знаковий/беззнаковий) та розміри подання в байтах, а також їх діапазони.

Тип Byte – беззнакові в 1 байті, 0..255.

Тип Shortint – знакові в 1 байті, -128..127.

Тип Word – беззнакові в 2 байтах, 0..65535.

Тип Longint – знакові в 4 байтах, -2147483648..2147483647.

Для всіх цих типів означено всі операції, що й для типу Integer.

Числа базового типу Real займають 6 байтів. 1 біт зайнятий знаком числа, 39 – дробовою частиною, 8 – порядком. Нескладно підрахувати, що діапазон додатних чисел – від 2^-126 2.9 10^-39 до (2-2^-39) 2^127 10³⁸.

Значення типу Single займають 4 байти (дробова частина – 23 біти, порядок – 8). Діапазон додатних значень – від 2^-126 до (2-2^-23) 2^127 10³⁸.

Значення типу Double займають 8 байтів (дробова частина – 52 біти, порядок – 11). Відзначимо, що з урахуванням особливостей архітектури сучасних комп'ютерів краще користуватися цим типом, ніж типом real [Григ]. Діапазон додатних значень – від 2^-1022 10^-315 до (2-2^-52) 2^1023 10³¹⁵.

Значення типу Extended займають 10 байтів (дробова частина – 64 біти, порядок – 15). Діапазон додатних значень – від 2^-16382 10^-4931 до  2 2^16383 10⁴⁹³².

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

Значення типу Comp (скорочене compound – складений) займають 8 байтів. Ці значення є дійсними поданнями цілих чисел від -2⁶³ до +2⁶³-1. До них застосовні операції дійсних, а не цілих типів.

І останнє зауваження. Кількість байтів, які займаються значеннями будь-якого типу, можна дізнатися, викликавши функцію SIZEOF. Наприклад, із виклику sizeof(Longint) повертається 4, із виклику sizeof(Word) – 2.

Задачі

15. У діалекті Турбо Паскаль на цілих типах визначена операція "додавання за модулем 2" із знаком xor. Вона виконується шляхом побітового додавання операндів за правилами 0 0=1 1=0, 1 0=0 1=1, тобто без переносу 1 у наступний розряд. Наприклад, у типі Byte 220 xor 127 =163 – це добре видно в байтовім поданні:

 11011100

01111111

10100011

Довести її властивості: якщо a, b, c позначають довільні цілі операнди, то

a xor a = 0, a xor 0 = a, a xor b = b xor a,

(a xor b) xor c =a xor (b xor c), (a xor b) xor b = a.