Велика бібліотека української літератури
» » ПАСКАЛЬ:ПОДАННЯ ЧИСЕЛ ТА ІНШИХ ЗНАЧЕНЬ

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

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

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

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

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

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

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

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

(akak-1 a1a0)P

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

ak Pk+ak-1 Pk-1+ +a1 P+a0.

Наприклад, двійковий запис (10011)2 позначає число, яке в десятковому записі має вигляд 1 24+0 23+0 22+1 21+1 20=19. 16-ковий запис (1BC)16 позначає десяткове 1 162+11 16+12=444.

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

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

За P-ковим записом (akak-1  a1a0)P натурального числа N можна побудувати десяткове подання, обчисливши значення полінома за допомогою операцій множення та додавання в десятковій системі. Саме цим ми займалися двома абзацами вище.

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

N = ak Pk+ak-1 Pk-1+ +a1 P+a0 = (…(ak P+ak-1) P+ +a1) P+a0.

Звідси очевидно, що значенням a0 є N mod P, a1 – (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)2 позначає десяткове

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

(0.21)3 – 2 3-1+1 3-2=0.777…=0.(7); (0.BC)16 – 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))3.

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

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

Аналогічно чотири сусідні байти відображають (28)4=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 до 28N-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 – молодший (праворуч). Комбінація бітів x8N-1,  , x0 зображає в двійковій системі число

x8N-1 28N-1+ x1 2+x0.

Наприклад, комбінація 00 00 задає число 0, комбінація 00 01 – "один", 00 10 – "два", 11 11 – число 28N-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 до 28N-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 - (2d-1-1);

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

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

(-1)s (1+m1) 2t (11.2)

Оскільки 1 1+m1Значення типу Extended займають 10 байтів (дробова частина – 64 біти, порядок – 15). Діапазон додатних значень – від 2-16382 10-4931 до  2 216383 104932.

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

Значення типу Comp (скорочене compound – складений) займають 8 байтів. Ці значення є дійсними поданнями цілих чисел від -263 до +263-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.
© 2014 - 2019 BigLib.info — это сокращение от Big Library (большая библиотека).
Целью создания этого сайта было сделать украинскую литературу доступной для всех, кто желает ее читать.
Использование любых материалов сайта без согласования с администрацией запрещено.
Обратная связь