Системи числення: задачі з покроковими розв’язками

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

У повсякденному житті ви рахуєте в десятковій системі, з основою 10. Вона має десять цифр, від 0 до 9, і кожен розряд коштує вдесятеро більше за розряд праворуч.

У числі 352 цифра 3 означає 300, цифра 5 — 50, а цифра 2 — 2. Розряди коштують 1, 10, 100, якщо йти справа.

Комп’ютер зберігає все як перемикачі, що ввімкнені або вимкнені. Тому він рахує в двійковій системі, з основою 2, лише з цифрами 0 і 1.

Одна двійкова цифра — це біт. Група з 8 бітів — це байт.

Правило однакове в усіх системах числення: кожна цифра дорівнює своєму значенню, помноженому на степінь основи.

2Двійкова й шістнадцяткова системи

У двійковій системі розряди коштують 1, 2, 4, 8, 16 і так далі, справа наліво. Кожен розряд коштує вдвічі більше за розряд праворуч.

Для 8-бітного числа розряди коштують 128, 64, 32, 16, 8, 4, 2 і 1.

Щоб прочитати двійкове число, додайте вагові значення розрядів усіх бітів, що дорівнюють 1. Для 0011 0010 це 32 + 16 + 2 = 50.

Довгі ряди бітів важко читати. Програмісти часто записують їх натомість у шістнадцятковій системі (hex), з основою 16.

Шістнадцяткова система потребує 16 цифр. Вона використовує 0–9, а далі літери A = 10, B = 11, C = 12, D = 13, E = 14 і F = 15.

Розряди шістнадцяткового числа коштують 1, 16, 256 і 4096, справа наліво. Шістнадцяткове число часто пишуть із 0x попереду, наприклад 0x2F.

Одна шістнадцяткова цифра — це рівно 4 біти, тож 0011 0010 — це 0x32: 0011 — це 3, а 0010 — це 2.

3Від’ємні числа: доповняльний код

Байт, у якому всі розряди додатні, зберігає від 0 до 255. Це називають беззнаковим числом.

Щоб зберігати від’ємні числа, комп’ютери використовують доповняльний код (two’s complement). Єдина зміна: крайній лівий біт дорівнює −128 замість +128.

Отже, 1000 0011 — це −128 + 2 + 1 = −125. Крайній лівий біт називають знаковим бітом: коли він дорівнює 1, число від’ємне.

8-бітне число в доповняльному коді — від −128 (1000 0000) до +127 (0111 1111).

Щоб записати від’ємне число −x, візьміть +x у двійковій системі, інвертуйте кожен біт (0 стає 1, 1 стає 0) і додайте 1.

Приклад для −5: 5 — це 0000 0101. Інвертоване — 1111 1010. Додавши 1, отримуємо 1111 1011.

Той самий шаблон, прочитаний як беззнаковий, має значення 256 − x. Для −5 це 251, і справді 1111 1011 — це 128 + 64 + 32 + 16 + 8 + 2 + 1 = 251.

4Метод крок за кроком

Двійкове чи шістнадцяткове число в десяткове:

1. Запишіть вагу розряду під кожною цифрою: степені 2 для двійкових, степені 16 для шістнадцяткових, починаючи з 1 справа.
2. У шістнадцятковій системі замініть кожну літеру її значенням: від A = 10 до F = 15.
3. Помножте кожну цифру на вагу її розряду й додайте все.

Доповняльний код:

1. Щоб прочитати шаблон, надайте крайньому лівому біту значення −128 (у 8 бітах) і додайте ваги всіх одиничних бітів.
2. Щоб записати −x, запишіть +x у 8 бітах, інвертуйте кожен біт і додайте 1.
3. Беззнакове значення цього шаблону дорівнює 256 − x. Користуйтеся ним, щоб перевірити біти.

Біти, діапазони й пам’ять:

1. n бітів дають 2ⁿ різних шаблонів.
2. Беззнакові вони зберігають від 0 до 2ⁿ − 1. У доповняльному коді — від −2ⁿ⁻¹ до 2ⁿ⁻¹ − 1.
3. Щоб дати k елементам власні коди, знайдіть найменше b, для якого 2^b ≥ k.
4. Для пам’яті помножте кількість елементів на кількість бітів на елемент, потім поділіть на 8 для байтів і на 1024 для KiB.

5Розв’язаний приклад

Простежте кожен крок. Спробуйте передбачити наступний, перш ніж його відкрити.

6Типові помилки

• Забути додати 1 після інвертування бітів. Результат виходить на одиницю менший.
• Читати шаблон доповняльного коду як беззнаковий, наприклад 1111 1111 як 255 замість −1.
• Вважати знаковий біт знаком мінус перед рештою бітів. У доповняльному коді він має вагу −128.
• Розташовувати розряди в хибному порядку. Розряд із вагою 1 завжди справа.
• Брати A = 11 у шістнадцятковій системі. Літери починаються з A = 10.
• Плутати біти й байти в задачах на пам’ять. Поділіть кількість бітів на 8.

7Як виглядають екзаменаційні запитання

• Легкі: двійкові та шістнадцяткові числа в десяткові. Перетворіть 8-бітне двійкове або 3-цифрове шістнадцяткове число в десяткове.
• Середні: доповняльний код. Прочитайте значення знакового 8-бітного шаблону або запишіть від’ємне число як шаблон і дайте його беззнакове значення.
• Складні: біти, діапазони й пам’ять. Найбільше або найменше (найбільш від’ємне) значення, що вміщується в n бітів, кількість бітів для k кодів або пам’ять, яку займає зображення.

Приклад складного запитання: зображення 256 × 256 із 24 бітами на піксель займає 256 · 256 · 24 / 8 / 1024 = 192 KiB.