Числа в разных системах

Компьютер «думает» двоичными числами — $0$ и $1$. Для компактной записи адресов и кодов программисты используют шестнадцатеричную систему; в задачах ЕГЭ встречается и восьмеричная. Задания 5 и 14 напрямую требуют уверенного перевода между системами с основаниями $2$, $8$, $10$ и $16$.

Алфавиты систем счисления:

СистемаОснованиеЦифры
Двоичная$2$$0, 1$
Восьмеричная$8$$0, 1, \ldots, 7$
Десятичная$10$$0, 1, \ldots, 9$
Шестнадцатеричная$16$$0$–$9$, $\text{A}$–$\text{F}$

В шестнадцатеричной системе A = $10$, B = $11$, …, F = $15$.

Перевод из десятичной в двоичную

Стандартный метод — последовательное деление на $2$: делите, записывайте остатки, читайте снизу вверх.

Пример: переведём $42_{10}$ в двоичную.

$$42 \div 2 = 21,\quad \text{ост. } 0$$
$$21 \div 2 = 10,\quad \text{ост. } 1$$
$$10 \div 2 = 5,\quad \text{ост. } 0$$
$$5 \div 2 = 2,\quad \text{ост. } 1$$
$$2 \div 2 = 1,\quad \text{ост. } 0$$
$$1 \div 2 = 0,\quad \text{ост. } 1$$

Читаем остатки снизу вверх: $42_{10} = 101010_2$.

Проверка: $2^5 + 2^3 + 2^1 = 32 + 8 + 2 = 42$. ✓

flowchart TD A[Число N] --> B{N > 0?} B -- Да --> C[остаток := N mod 2] C --> D[N := N div 2] D --> B B -- Нет --> E[Читаем остатки снизу вверх] E --> F[Готово: двоичное число]
flowchart TD
    A[Число N] --> B{N > 0?}
    B -- Да --> C[остаток := N mod 2]
    C --> D[N := N div 2]
    D --> B
    B -- Нет --> E[Читаем остатки снизу вверх]
    E --> F[Готово: двоичное число]
Алгоритм перевода числа из десятичной системы в двоичную методом последовательного деления на 2
Quick recall
При переводе десятичного числа в двоичное методом деления на 2 остатки читаются ___

Быстрый переход: двоичная ↔ шестнадцатеричная и восьмеричная

Группируйте двоичные цифры справа налево по 4 бита — каждая четвёрка даёт одну шестнадцатеричную цифру.

$$\underbrace{1010}_{A}\,\underbrace{1111}_{F} \;\Rightarrow\; \text{AF}_{16} = 10 \cdot 16 + 15 = 175_{10}$$

Для перехода двоичная ↔ восьмеричная — группы по 3 бита:

$$\underbrace{101}_{5}\,\underbrace{010}_{2} \;\Rightarrow\; 52_8 = 5 \cdot 8 + 2 = 42_{10}$$

Переход через десятичную в таких задачах медленнее — лучше использовать группировку.

Check yourself
Переведите $25_{10}$ в двоичную систему счисления. Запишите результат и проверьте его.
Quick recall
Почему можно преобразовывать число напрямую из двоичной системы в шестнадцатеричную, не переходя через десятичную?

Двоичная арифметика

Таблица сложения двух бит:

$$0 + 0 = 0, \quad 0 + 1 = 1, \quad 1 + 0 = 1, \quad 1 + 1 = 10_2$$

При сложении $1 + 1$ получается $0$ и перенос единицы влево. Пример:

$$1011_2 + 0110_2 = 10001_2$$

Проверка: $11 + 6 = 17$, и $2^4 + 2^0 = 16 + 1 = 17$. ✓

Натренируйтесь на 3–4 примерах, чтобы перенос «шёл» автоматически — на экзамене это экономит время.

Quick recall
Что получается при сложении 1₂ + 1₂ в двоичной арифметике?

Логические операции

Задания 2 и 8 требуют работы с булевой алгеброй. Переменные принимают значения «истина» ($1$) или «ложь» ($0$).

Пять ключевых операций:

ОперацияОбозначениеКогда равна $1$
Конъюнкция (И)$A \land B$только если оба $1$
Дизъюнкция (ИЛИ)$A \lor B$если хотя бы один $1$
Отрицание (НЕ)$\lnot A$всегда инвертирует значение
Исключающее ИЛИ$A \oplus B$только если значения различны
Импликация$A \to B$ложна лишь при $A=1,\; B=0$
Стандартные условные обозначения логических элементов И, ИЛИ, НЕ и исключающее ИЛИ, применяемые в информатике.Source: geekgu.ru

Таблица истинности для $A \land B$ и $A \lor B$:

$A$$B$$A \land B$$A \lor B$
$0$$0$$0$$0$
$0$$1$$0$$1$
$1$$0$$0$$1$
$1$$1$$1$$1$

Полезное тождество: $A \to B \;\equiv\; \lnot A \lor B$. Когда в задаче нужно найти, при каких значениях переменных выражение истинно — ищите условия, при которых оно было бы ложным, и методом «от обратного» сужайте варианты.

Check yourself
Логическое выражение $A \land \lnot B$ истинно. Каковы возможные значения $A$ и $B$?

Кодирование информации

Задания 5 и 7 — это «арифметика информации». Три формульных блока, которые нужно знать наизусть.

Текст

$$V_{\text{текст}} = N_{\text{симв}} \times b_{\text{код}}$$

где $b_{\text{код}}$ — бит на символ, $N_{\text{симв}}$ — количество символов. Часто используемые кодировки:

  • КОИ-8, Windows-1251, CP-866 — $8$ бит ($1$ байт), $256$ символов;
  • Unicode UTF-16 — $16$ бит ($2$ байта) на символ;
  • Unicode UTF-32 — $32$ бита ($4$ байта).

Графика

$$V_{\text{граф}} = W \times H \times b_{\text{цвет}}$$

где $W \times H$ — разрешение в пикселях, $b_{\text{цвет}}$ — глубина цвета в битах. Для палитры из $K$ цветов:

$$b_{\text{цвет}} = \log_2 K$$

Типичные значения: $256$ цветов → $8$ бит; True Color ($16\,777\,216 = 2^{24}$ цветов) → $24$ бита; RGBA → $32$ бита.

Звук

$$V_{\text{звук}} = f_{\text{д}} \times b_{\text{р}} \times N_{\text{кан}} \times t$$

где $f_{\text{д}}$ — частота дискретизации (Гц), $b_{\text{р}}$ — разрядность (бит), $N_{\text{кан}}$ — $1$ (моно) или $2$ (стерео), $t$ — время в секундах.

Пример: стерео, $44\,100$ Гц, $16$ бит, $60$ с:

$$V = 44100 \times 16 \times 2 \times 60 = 84\,672\,000 \text{ бит} = 10\,584\,000 \text{ байт} \approx 10{,}1 \text{ МБ}$$
Check yourself
Растровое изображение $800 \times 600$ пикселей, $256$ цветов. Каков его объём в байтах (без сжатия)?

Частые ошибки

  • Биты и байты: указывайте единицы явно на каждом шаге — ошибка на множитель $8$ типична и снимает весь балл.
  • Направление чтения при переводе в двоичную: остатки читаются снизу вверх, не сверху вниз.
  • Основание логарифма: в формулах кодирования всегда $\log_2$, не $\log_{10}$.
  • Импликация — самая «коварная» операция. Запомните единственное исключение: $1 \to 0 = 0$; во всех остальных трёх случаях $A \to B = 1$.

См. также