Материал: Інформатика_1 (методи побудови алгоритмівта та їх аналіз)

41

За аналогією з вісімковою системою числення можна зроби-ти висновок, що кожній цифрі шістнадцяткової системи чис­лення відповідає тетрада двійкових цифр.

Зверніть увагу на те, як ми позначили символи шістнад-цяткової системи числення, які більші за 9. Крім того, зверніть увагу на співвідношення 2' = 16, пригадайте, що 2³ = 8, і прове-діть аналогію.

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

Наприклад, АВ9С1₁₆ = 1010 1011 1001 1100 0001₂.

ІДля переведения чисел із двійкової системи числення у ШІСТ-надцяткову треба розбити задане число на тетради справа наліво і замінити кожну тетраду відповідною шістнадцятко-вою цифрою.

Розглянемо вже знайомий приклад: 10100110000011101₂ = 0001 0100 1100 0001 1101₂ = 14C1D₁₆.

Проаналізувавши наведені правила, можна відповісти на таке запитання: скільки потрібно двійкових цифр для того, щоб зобразити будь-яку цифру системи числення з основою 32 у двійковій системі? Справді, п'ять, адже 2⁵ - 32.

Шдсумовуючи все вищесказане, можна відповісти на за­питання: яке відношення мають системи числення до основ алгоритмізації? А відповідь буде такою.

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

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

По-третє, тепер зрозуміло, чому порції інформації, якими при роботі обмінюються різні компоненти комп'ютера, скла-даються саме з 8, 16 та 32 бітів. Пригадайте про розрядність комп'ютерів!

Чи можна реалізувати на комп'ютері переведения чисел з однієї системи числення в іншу для випадку, коли їхні основи є степенями числа 2? Зрозуміло, що така можливість існує. Представимо фрагмент програми, що реалізує переведения чисел із вісімкової системи числення у двійкову і навпаки:

function _8_2 (у: string): string; begin

ify = '0'then_8_2:='000';

42

if у if у if у if у if у if у if у end; function begin

if У

ify ify ify ify ify ify ify end;

_2_8 (y: string): string;

'000'then _2_8 •001'then _2_8 '010'then _2_8 '011' then _2_8 ' 100'then _2_8 401'then _2_8 '110'then _2_8 '111'then 2 8

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

writefx = '); readln(x); i := length(x);

if (ch = '2') and (i mod 3 <> 0) then if i mod 3 = 1

then x := '00' + x elsex := '0' + x;

Виклик функцій, що забезпечують переведения чисел із двійкової системи числення у вісімкову і навпаки, можна орга-нізувати так:

i := length(x);

у:=";

while i >= 1 do . case ch of

'1': begin у :=_8_2(x[i]) + y; dec(i, 1)end; | '2': begin у := _2_8 (copy(x, i - 2, 3)) + y; dec(i, 3) end; end;

Аналогічним чином можна реалізувати переведения чисел із двійкової системи числення у шістнадцяткову і навпаки.

ОДНОРОЗРЯДНИЙ СУМАТОР

Ми вже підкреслювали важливість двійкової системи чис­лення для роботи комп'ютера і знаємо, яким чином виконують-

43

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

Виявляється, що всі арифметичні дії в комп'ютері зведені до однієї дії додавання і виконує її спеціальний електронний пристрій — однорозрядний суматор.

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

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

Пригадаємо, що при додаванні у стовпчик результат до­давання завжди розбиваемо на дві частини: кількість одиниць і кількість десятків. Перша цифра записується у тому самому розряді результату, а друга запам'ятовуеться, щоб врахувати и при додаванні у наступному розряді. Це означав, що в роботі завжди буде п'ять величин: два розряди, які додаємо (a, b), кількість десятків, яку запам'ятали від додавання у попе-редньому розряді (с), та кількість одиниць і десятків, що одер-жуються в результаті додавання в даному розряді числа (п, т).

Для пояснения розглянемо невеличкий приклад:

1111

+

ПО

????

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

а = 1,6 = 0,с = 0.

Виконуючи дію додавання в цьому розряді (1 + 0 - 1), ви-значимо кількість одиниць (л) і десятків (т) в отриманому ре­зультат!:

п = 1, т = 0.

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

+ 0

4-

пи

+

ПО

???1

44

2-й крок. Бачимо, що а = 1, Ь = 1, а трете значения с, почи-наючи з другого кроку, дорівнює значению т на попередньому кроці, тобто с = т » 0. Тепер можемо записати додавання на другому кроці 1 + 1 + 0 = 10.

Тобто отримаемо п = 0, т. = 1:

+ 1 І

1111

+ 110

??01

3-й крок. Оскільки а = 1,Ь = 1,с = т = 1,то1 + 1 + 1 = 11. Отримуємо п - 1 і т = 1:

+ 1

І

1111

+ 110

?101

4-й крок. На оетанньому кроці а = 1, 6 = 0, с = т = 1, 1 + 0 +

+ 1-10.

Запишемо результат додавання у цьому розряді:

+ 1 І

1111

+ 110

0101

5-й крок. Оскільки цифри в доданках уже вичерпані, то за-лишилося проаналізувати значения с = т. Якщо воно дорів-нює 0, то попередній крок був останнім і знайдений результат є відповіддю. Якщо ж с = 1, то в результаті отримується число на порядок більше від найбільшого з двох доданків і найстаршою цифрою в ньому буде 1. Так було і в нашому прикладі:

1111

+ 110

10101

Який же висновок можна зробити з цього прикладу? На кожному кроці ми додавали три величини а, Ь, с і отримували дві величини птат. Значениями цих величин завжди є двійко-ві цифри. Умовно можна сказати, що ми визначили закон пе-ретворення значень трьох величин у значения двох величин у двійковій системі числення. Схематично це можна зобразити так (мал. 2).

45

Мал. 2

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

Таблиця3

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

Ми вже згадували про те, що операція віднімання в ком-п'ютері зведена до операції додавання. Розглянемо правило, яке використовується для отримання різниці між двома числа­ми. Нехай треба виконати дію 100₁₀ - 64₁₀. ЇЇ можна розглянути і в такому вигляді:

100₁₀ + (-64)₁₀.

Тому треба знайти аналог числа 64 у від'ємній область Спочатку переведемо це число у двійкову систему числення:

64₁₀ - 1000000₂.

Під час робота комп'ютера обробляються восьмирозрядні, шістнадцятирозрядні, тридцятидвохрозрядні порції інфор-мації, тому отриманий двійковий аналог числа 64₁₀ доповнимо до восьми цифр:

1000000₂ = 01000000,.

46

Наступний крок полягає в отриманні інверсії останнього эображення. Тобто всі цифри 1₂ необхідно замінити на 0₂ і нав-паки:

ІНВЄОСІЯ

01000000₂ « * 10111111₂.

Тепер додамо до результату інверсії число 1₂:

10111111,

+ ²

h

11000000₂

Цей результат і є двійковим значениям числа -64₁₀. Переві-римо це звичайним чином. Для десяткової системи числення справедлива рівність 64₁₀ + (-64)₁₀ ■ 0₁₀.

Такий самий результат повинні отримати і в двійковій си­стем! числення:

01000000₂

11000000₂

100000000₂

Оскільки в отриманому результат! старша цифра, тобто 1, внйшла за межі обумовленої на початку розрядності (восьми розрядів), то вона буде втрачена. Це означае, що підтверджено справедливість нашого результату.

• Запитання для самоконтролю

1. Що таке система числення?

2. Що розуміють під основою системи числення?

3. Які основні причини виникнення різних систем числення? За-лишки яких систем числення зустрічаються сьогодні?

4. На які два типи можна поділити всі існуючі системи числення? Дайте їм означения та наведіть приклади.

5. Які існують арифметичні операції в різних системах числення?

6. Сформулюйте правило переведения чисел з 10-Ї системи чис­лення в систему числення з основою Р і навпаки.

7. У чому полягає зв'язок між системами числення з основою 2*?

8. Сформулюйте правило переведения двійкових чисел у вісімкову та шістнадцяткову системи числення.

9. Яке призначення однорозрядного суматора? За яким законом він працює?

Завдання

1. Виконайте арифметичну дію:

1)354₆ + 121_в; 3) 10001₈ + 7777₈;

2) 6666. + 1₇; 4) 2222₃ + 2222₃;

5. 758₉ - 632„;

6. 312₄ - 123₄; 7)55555₈-17777₈; 8) 40002₅ - 33333₅; 9)12₃-2₃;

10) 64205, • 4₇;

11)78₉-11₉;

12)352₈-101₈;

13)24₆:2₆;

14. 153₇: 3₇;

15. 2002₅: 4₅; 16)11111₄:2₄.

2. Переведіть число з однієї системи числення в іншу:

1) 1996₁₀ - ?₅; 2)1838,,, = ?,; 3)80486₁₀ = ?₈; 4)321₁₀ = ?₂; 5)5555 -?

10'

10'

6) 10040₅ - ?₁₀ 7)1838₉ = ?₁₀; 8) 20103_в-? 9)324₈-?з 10)1010₆=.?₅ 11)7777₈«?₉ 12) 5004₇ - ?₂

13)1000011110111100001₂- ?₈ - ?

14. 111000110001111₂ = ?₈ = ?₁₆;

15. 101010101010₂ - ?₈ = ?₁₆;

16. 100001110001100₂ = ?₈ = ?₁₆; 17)56124₈ = ?₂ = ?,₆; 18) 7777777₈ = ?₂ = ?₁₆; 19)10001₈-?₂ = ?₁₆; 20)12131₈ = ?₂ = ?₁₆; 21)1A9DE,₆ = ?₂ = ?₈;

22. FFFFF₁₆ - ?₂ = ?₈;

23. ABCDEF9₁₆ = ?₂ = ?₈;

24. 202020₁₆ = ?2 = ?₈.

II

48

3. Заповніть порожні клітинки таблиці множення.