Введення у світ програмування

Бібліотека сайту rus-linux.net

На головну -> MyLDP -> Електронні книги з ОС Linux
назадВведення у світ програмування Глава 2. Архітектура комп'ютераВперед

Осередки пам'яті та позиційні системи числення

Пам'ять комп'ютера являє собою послідовність осередків пам'яті фіксованого розміру.Комірка пам'яті - це мінімальна одиниця пам'яті, до якої можна звертатися з програми.Розмір однієї комірки пам'яті залежить від моделі комп'ютера (наприклад, DEC PDP-15 працював із комірками пам'яті, що містили по 18 біт у кожній). У персональних ЕОМ зазвичай використовуються осередки пам'яті, які з 8 біт. Такі осередки можуть бути названі 8-розрядними, тобто такими, що містять по вісім двійкових розрядів (поняття "розряд числа" застосовується в позиційних системах числення і позначає структурний елемент представлення числа). Осередок цього розміру може містити, наприклад, значення 01010010 .

За допомогою 8-розрядного двійкового числа можна представляти десяткові числа від 0 до 255. Наприклад, якщо взяти двійкове число 01111101 і перевести його в десяткове, то вийде: 2 0 + 0 1 + 2 2 + 2 3 + 2 4 + 2 5 + 2 6 + 07 = 125 . Якщо ж потрібно перевести десяткове число в двійкове, це теж не складе проблем. Вся справа в тому, що і двійкова і десяткова і шістнадцяткова системи числення (найчастіше використовувані в програмах на асемблері) є позиційними (значення кожного знака в числі, записаному в такій системі, залежить від якого розряду [місцю] він відповідає). Уміння швидко здійснювати переведення чисел з однієї позиційної системи числення до іншої є однією з суттєвих характеристик хорошого програміста. Тому зупинимося на цьому питанні докладніше.

Усний переведення числа з однієї позиційної системи числення до іншої

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

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

Перехід від десяткової системи до двійкової та навпаки

По-перше, слід запам'ятати що будь-яке десяткове число можна розбити на суму доданків, кожне з яких можна виразити ступенем числа два. Наприклад: 23 = 16 + 4 + 2 + 1 = 2 4 + 2 2 + 2 1 + 2 0 .

По-друге, треба знати напам'ять (або хоча б мати при собі) таблицю ступенів два числа. Як мінімум, ви повинні пам'ятати, що:

По-третє, будь-яке, навіть найбільше, десяткове число може бути представлене як сума ступенів числа два єдиним чином! Наприклад, якщо взяти відносно велике число 395 , то його можна розкласти так: 39510 = 256 + 128 + 8 + 2 + 1 = 2 8 + 2 7 + 2 3 + 2 1 + 2 0 = 1100010112 .І ніяк інакше!

Таким чином, для швидкого переведення десяткового числа в двійкове потрібно згадати значення ступеня числа два, що представляє собою маскимально велике доданок, що переводиться (це і буде перше доданок). Наприклад, якщо взяти десяткове число 1079 , то ми можемо сміливо брати як перший доданок 2 10 , тобто 1024 . Далі потрібно відняти 1024 з 1079 : 1079-1024 = 55 . Потім – знайти максимально великечисло, менше, ніж 55 і є ступенем числа 2. Це буде 32, тобто 25. Продовжувати потрібно до тих пір, поки не будуть знайдені всі доданки, на які можна розкласти десяткове число для того, щоб швидко перевести його в двійковий формат запису.

У нас вийшло: 1079 = 1024+32+16+4+2+1. Пам'ятаєте, що ми вже розкладали 23 на доданки, які зручно переводити у двійкову виставу? У цьому прикладі ми маємо такі самі результати!

Цікавий читач може запитати:які складові зручно переводити в двійкове уявлення?. Звичайно ж ті, які є ступенями числа два. Чому? Згадайте, що двійкова система є позиційною . Це означає, що значення ступеня доданку дозволяє визначити його місце (розряд) у двійковому числі (якщо доданок більше нуля, то відповідний розряд двійкового числа дорівнюватиме одиниці). Наприклад, 1079 = 1024 + 32 + 16 + 4 + 2 + 1 = 2 10 + 2 5 + 2 4 + 2 2 + 2 1 + 2 0 = 100001101112. Ми отримали 11-розрядне двійкове число, розряди якого встановлені в одиничне значення в тому випадку, якщо їх порядковий номер (починаючи з правого краю) збігається зі значенням ступеня складової суми, на яку (єдиним чином!) можна розкласти число 1079.

Попрактикувавши запропонований метод (дуже схожий на "метод різниць") деякий час, ви навчитеся усно і дуже швидко переводити навіть великі числа з десяткової системи числення в двійкову і навпаки (наприклад, 1001010112 = 2 8 + 2 5 + 2 3 + 2 1 + 20 = 256 + 32 + 8 + 2 + 1 = 29910).

Інші варіанти переходу між системами числення

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

Ось як це може виглядати: 4435 = 4 * 5 2 + 4 * 5 1 + 3 * 5 0 = 12310 = 2 6 + 2 5 + 2 4 + 2 3 + 2 1 + 2 0 = 11110112.

У свою чергу, для роботи з шістнадцятковою системою числення найзручніше використовувати двійкову як основу (будь-яке 16 число може бути отримане послідовним перетворенням чотирирозрядних груп двійкового числа). Наприклад, 100101002 є вісім двійкових розрядів. Починаючи з правого краю перекладатиме чотирирозрядні групи двійкових розрядів спочатку в десяткові числа, а потім у шістнадцяткові розряди. Таким чином: 100101002 = 9416. Або, наприклад, 10111101012 = 2F516 =0010111101012 (зверніть увагу, що в цьому двійковому числі десять розрядів: ті розряди, які необхідні для формування трьох груп по чотири розряди в кожній, ми заповнюємо нулями).

Автоматизований переведення числа з однієї позиційної системи числення до іншої

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

По-перше, видно, що це ніякий не асемблер (поки що!), а справжнісінький Pascal (програма може бути скомпільована за допомогою GNU Pascal , див: http://www.gnu-pascal.de/gpc/h- index.html). Вона може працювати з 2, 3, 4, 5, 6, 7, 8, 9, 10системами числення.

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

Далі функція val перевіряє, чи вводиться значення цілим позитивним числом. Якщо не є, видається відповідне повідомлення про помилку і програма завершує роботу.

Якщо вказана користувачем основа системи числення є допустимою, програма запитує введення числа, яке необхідно проаналізувати (перевести в інші системи числення). Цей запит знову виконується функцією readln, яка приймає введення користувача та записує його в змінну k:readln(k).

А ось тепер починається найцікавіше. Якщо основа системи числення, в якій представлено аналізоване число дорівнює 10, то виконується блок коду, що здійснює переведення цього числа в інші системи числення, що підтримуються програмою (2-у, 3-ю, 4-у, 5-у, 6-у , 8-ту, 9-ту).

Давайте розберемо цей блок коду рядково.

Змінна Newbase містить основу цільової системи числення (тою, в яку ми переводимо число, задане у відповідь на запит програми "Provide a number to be analysed" - "Вкажіть число для аналізу"). Цикл для новогобаза:=2 до 9 до початку . end; дозволяє послідовно провести переведення значення змінної x спочатку в двійкову, потім у трійкову і так далі аж до 9-річної системи числення.

Нагадаємо, що значення x ми задали у відповідь на запит "Provide a number to be analysed".

Цикл while (opnum div newbase) > 0 do begin. end; використовує дві додаткові змінні: opnum та i . Видно, що i є індексом для звернення довмісту масиву left[] та інкрементується (тобто збільшується на одиницю) при кожному черговому етапі циклу while .

Не забувайте, що в мові Паскаль, на відміну, наприклад, від мови Сі, індекси масиву можуть мати значення починаючи з одиниці, а не з нуля. Саме тому запис початкового значення змінної i здійснюється так: i:=1 .

Але навіщо нам потрібний масив left[]? І чому він називається саме так, а не інакше? Цей масив застосовується для проміжного зберігання розрядів числа в цільовій системі числення (newbase). Кожен черговий розряд цього числа, що додається в масив left [], виявляється ліворуч від попереднього (у позиційній системі числення кожен розряд має свою вагу).

Давайте тепер звернемо увагу на вираз opnum div newbase. Його результат має бути більшим за нуль, інакше цикл while (opnum div newbase) > 0 do begin. end; перестане виконуватися і вміст масиву left[] набуде закінченого вигляду.

Як видно, оператор div приймає два операнди: opnum (аналізоване число) і newbase (цільова система числення). Пропозиція мови Паскаль opnum div newbase перетворюється компілятором GNU Pascal (або будь-яким іншим) і стає частиною виконуваного об'єктного файлу a.out (за промовчанням), який придатний для завантаження в пам'ять комп'ютера і безпосереднього виконання центральним процесорним пристроєм. Результатом виконання пропозиції opnum div newbase є ціла частина від розподілу значення змінної opnum на значення змінної newbase (наприклад, якщо 11 розділити на 4, то цілою частиною від розподілу буде число 2).

Перейдемо до пропозиції opnum mod newbase. Навіщо воно? Оператор mod застосовується з метою знаходження залишку від поділу двох чисел (наприклад, 25 mod 7 = 4). Але навіщо цепотрібно? Потім, що він (залишок) завжди буде менше підстави цільової системи числення, а отже, виходячи з логіки всієї програми, буде записаний в масив left [] , будучи значенням одного з розрядів числа цільової системи числення. Інакше кажучи: left[i]:=opnum mod newbase .

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

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

Пропозиція for j:=i downto 1 do write(left[j]); виводить на друк (тобто стандартний пристрій виведення) вміст масиву left[] .

Сесія роботи з програмою, розібраною вище, може бути наступною.

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

Стандартна функція length(k) повертає довжину рядка (кількість розрядів в аналізованому числі), що містить число, що аналізується. Цикл for l:=length(k) downto 1 do begin . end; виконується до тих пір, покизмінна l стане рівної одиниці.

Усередині циклу виконується блок коду, ключовим рядком якого є j: = j + z * (y pow (l-1)); . У ній проводиться зведення вихідної основи системи числення, що зберігається в змінній y в ступінь, яка на одиницю менша за кількість розрядів в аналізованому числі (це потрібно, щоб було можливим працювати з розрядом, значення якого дорівнює підставі вихідної системи числення в нульовому ступені).

Ключовий рядок, представлений вище, дозволяє програмно переводити число з вихідної системи числення до десяткового, тобто робити те саме, що ми робили з числом 4435: 4435 = 4*5 2 + 4*5 1 + 3*5 0 .

Ось тепер справді все. Сподіваємося, нам вдалося показати читачеві те, яким чином можна обробляти числа, що зберігаються в осередках пам'яті.