Системи числення та двійкова арифметика

Чому програмісту важливо знати двійкову арифметику

Ви вже вмієте оголошувати змінні, писати цикли, використовувати функції. Але ось питання: що насправді відбувається, коли ви пишете int x = 42? Яке значення зберігається в пам'яті? Чому int займає 4 байти, а char — 1? Чому результат 255 + 1 у типі uint8_t дорівнює 0? Чому побітові операції (&, |, ^, >>, <<) такі потужні і де вони використовуються?

Відповідь на всі ці питання починається з одного фундаментального факту: комп'ютер зберігає і обробляє дані виключно у двійковій системі числення — послідовностях нулів і одиниць. Усе інше — це рівні абстракції над цим фактом.

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

Система числення (numeral system) — це спосіб запису і представлення чисел за допомогою символів (цифр) відповідно до певних правил.

Ключовий параметр будь-якої позиційної системи числення — основа (base, або radix): кількість різних символів (цифр), що використовуються. У позиційній системі значення цифри залежить від її позиції (розряду) у записі числа.

Загальна формула для числа у системі з основою B:

Число = dₙ × Bⁿ + dₙ₋₁ × Bⁿ⁻¹ + ... + d₁ × B¹ + d₀ × B⁰

де dᵢ — цифра на позиції i, B — основа системи.

Ми користуємось цим принципом щодня, навіть не замислюючись. Наприклад, число 342 у десятковій системі:

342 = 3 × 10² + 4 × 10¹ + 2 × 10⁰
    = 3 × 100 + 4 × 10  + 2 × 1
    = 300     + 40       + 2
    = 342

Саме так само будується будь-яка інша позиційна система — лише основа інша.

Системи числення у програмуванні

У програмуванні регулярно зустрічаються чотири системи числення:

Таблиця відповідностей

Двійкова система числення

Чому комп'ютер «думає» двійково

Фізична природа комп'ютера — транзистор, який може перебувати в одному з двох станів: провідний (є струм → 1) або непровідний (немає струму → 0). Один такий стан — це біт (bit, binary digit). Вісім бітів утворюють байт (byte).

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

Читання двійкового числа

Двійкове число 1011 0110 читається так (справа ліворуч, позиції 0..7):

1 0 1 1   0 1 1 0
↑ ↑ ↑ ↑   ↑ ↑ ↑ ↑
7 6 5 4   3 2 1 0  ← позиція (степінь двійки)

= 1×2⁷ + 0×2⁶ + 1×2⁵ + 1×2⁴ + 0×2³ + 1×2² + 1×2¹ + 0×2⁰
= 128   + 0    + 32   + 16   + 0    + 4    + 2    + 0
= 182

Переведення з десяткової у двійкову

Метод послідовного ділення на 2 з записом залишків:

182 ÷ 2 = 91  залишок 0
 91 ÷ 2 = 45  залишок 1
 45 ÷ 2 = 22  залишок 1
 22 ÷ 2 = 11  залишок 0
 11 ÷ 2 = 5   залишок 1
  5 ÷ 2 = 2   залишок 1
  2 ÷ 2 = 1   залишок 0
  1 ÷ 2 = 0   залишок 1
             ↑
       читати знизу вгору: 1011 0110

Перевірка: 0b10110110 у C++ — це 182. ✅

Шістнадцяткова система числення

Чому шістнадцяткова — це «стислий двійковий»

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

Двійкове:       1011   0110
Групуємо по 4:  1011 | 0110
Переводимо:      B   |  6
Шістнадцяткове: 0xB6

Саме тому адреси пам'яті, кольори (#FF5733), маски бітів і вміст байтів у hex-дампах записують у шістнадцятковій системі — це зручно для читання людиною і пряме відображення бінарного вмісту.

Переведення: hex ↔ десяткова

З шістнадцяткової в десяткову:

0xFF = 15×16¹ + 15×16⁰ = 240 + 15 = 255
0x2A = 2×16¹  + 10×16⁰ = 32  + 10 = 42

З десяткової в шістнадцяткову — метод ділення на 16:

255 ÷ 16 = 15  залишок 15 (F)
 15 ÷ 16 = 0   залишок 15 (F)
                    ↑ знизу вгору: FF

Запис у C++

#include <iostream>

int main()
{
    int decimal     = 182;
    int binary      = 0b10110110; // C++14
    int octal       = 0266;
    int hexadecimal = 0xB6;

    // Усі чотири змінні містять одне й те саме значення!
    std::cout << decimal     << "\n"; // 182
    std::cout << binary      << "\n"; // 182
    std::cout << octal       << "\n"; // 182
    std::cout << hexadecimal << "\n"; // 182

    // Виведення у різних форматах
    std::cout << std::hex << decimal << "\n"; // b6
    std::cout << std::oct << decimal << "\n"; // 266
    std::cout << std::dec << decimal << "\n"; // 182

    return 0;
}

Вісімкова система числення

Вісімкова система використовує цифри від 0 до 7. Сьогодні вона найчастіше зустрічається у правах доступу до файлів у UNIX/Linux:

chmod 755 script.sh

Тут 755 — три вісімкові цифри, кожна з яких задає права для власника, групи і всіх інших. Чому вісімкова? Тому що три біти (rwx) — саме стільки потрібно для кодування трьох прав — дають 8 комбінацій (000..111), що точно відповідає одній вісімковій цифрі.

7 = 111 (двійк.) = rwx (read + write + execute)
5 = 101 (двійк.) = r-x (read + execute)
4 = 100 (двійк.) = r-- (тільки read)

Арифметика в різних системах числення

Загальний принцип: перенесення розряду

Додавання в будь-якій системі числення працює за одним принципом: коли сума цифр у розряді досягає або перевищує основу системи, виникає перенесення (carry) в наступний розряд.

  347
+ 285
-----
  632

Одиниці: 7+5=12 → пишемо 2, переносимо 1
Десятки: 4+8+1=13 → пишемо 3, переносимо 1
Сотні:   3+2+1=6  → пишемо 6

  1011  (= 11)
+ 0110  (=  6)
------
 10001  (= 17)

Позиція 0: 1+0=1
Позиція 1: 1+1=10 → 0, перенесення 1
Позиція 2: 0+1+1=10 → 0, перенесення 1
Позиція 3: 1+0+1=10 → 0, перенесення 1
Позиція 4: 0+0+1=1

  A7   (= 167)
+ 5B   (=  91)
----
 102   (= 258)

Одиниці: 7+B=7+11=18=16+2 → 2, переносимо 1
Шістнадцятки: A+5+1=10+5+1=16=16+0 → 0, переносимо 1
256: 0+0+1=1

Арифметичні операції у двійковій системі

Таблиця додавання бітів

Двійкове додавання ґрунтується на чотирьох базових випадках:

Якщо є ще й вхідне перенесення Cᵢₙ:

Покроковий приклад: 43 + 29

  43  →  0010 1011
+ 29  →  0001 1101
-----------------------
  72  →  0100 1000

Позиція 0: 1+1 = 10 → 0, перенос=1
Позиція 1: 1+0+1(пер) = 10 → 0, перенос=1
Позиція 2: 0+1+1(пер) = 10 → 0, перенос=1
Позиція 3: 1+1+1(пер) = 11 → 1, перенос=1
Позиція 4: 0+1+1(пер) = 10 → 0, перенос=1
Позиція 5: 1+0+1(пер) = 10 → 0, перенос=1
Позиція 6: 0+0+1(пер) = 01 → 1, перенос=0
Позиція 7: 0+0        = 00 → 0

Результат: 0100 1000 = 72 ✅

Двійкове віднімання

Метод 1 — пряме: аналогічно десятковому, але «позичаємо» 2 (а не 10):

  1011  (11)
- 0110  ( 6)
------
  0101  ( 5)

Позиція 0: 1-0=1
Позиція 1: 1-1=0
Позиція 2: 0-1 → позичаємо: 10-1=1, наступний розряд зменшується на 1
Позиція 3: 1-1-1(позика)=1-1-1 → позичаємо знову: 10+1-1-1=1

Метод 2 — через доповнення до двох (саме так роблять процесори — перетворюють A - B на A + (−B)). Це тема наступного розділу про представлення від'ємних чисел.

Двійкове множення

Таблиця множення бітів проста:

Множення двійкових чисел — це зсуви і додавання (саме так реалізують множення у «залізі»):

  1011  (11)
× 0101  ( 5)
----------
  1011  ← 1011 × 1 (позиція 0)
 0000   ← 1011 × 0 (позиція 1, зсув на 1)
1011    ← 1011 × 1 (позиція 2, зсув на 2)
----------
0110111 (= 55) ✅

Демонстрація у C++

#include <iostream>
#include <bitset>   // для двійкового виводу

int main()
{
    int a = 43;  // 0010 1011
    int b = 29;  // 0001 1101

    std::cout << "a      = " << std::bitset<8>(a) << " (" << a << ")\n";
    std::cout << "b      = " << std::bitset<8>(b) << " (" << b << ")\n";
    std::cout << "a + b  = " << std::bitset<8>(a + b) << " (" << a + b << ")\n";
    std::cout << "a - b  = " << std::bitset<8>(a - b) << " (" << a - b << ")\n";
    std::cout << "a * b  = " << std::bitset<16>(a * b) << " (" << a * b << ")\n";
    std::cout << "a / b  = " << std::bitset<8>(a / b)  << " (" << a / b  << ")\n";

    return 0;
}

Переповнення: що відбувається, коли число «не вміщається»

Це наслідок двійкової арифметики, про який обов'язково треба знати:

#include <iostream>
#include <cstdint>
#include <bitset>

int main()
{
    uint8_t maxValue = 255;  // 1111 1111
    uint8_t next     = maxValue + 1;

    std::cout << "255      = " << std::bitset<8>(maxValue) << "\n";
    std::cout << "255 + 1  = " << std::bitset<8>(next) << " (" << (int)next << ")\n";

    return 0;
}

255 + 1 у типі uint8_t дає 0 — перенесення «вивалюється» за межі восьми бітів і губиться. Це не баґ компілятора — це математика: 1111 1111 + 0000 0001 = 1 0000 0000, але дев'ятого біту в uint8_t немає.

Резюме