bulgakov

09. Разряды и двоичная запись

Почему восемь битов позволяют хранить только 256 разных значений? Чтобы понять границы типов и запись чисел в памяти, разберём, как из отдельных цифр получается число. Начнём с привычной десятичной системы и перенесём тот же принцип на двоичную.

Почему место цифры важно

В числе 472 цифра 4 означает четыре сотни, 7 — семь десятков, 2 — две единицы:

472=4⋅100+7⋅10+2⋅1472 = 4\cdot100 + 7\cdot10 + 2\cdot1

Числа 100, 10, 1 — веса разрядов. Справа налево каждый следующий вес в десять раз больше предыдущего.

Целое деление и остаток позволяют работать с этими разрядами в C. Полная программа получает цифры трёхзначного положительного числа:

C
#include <stdio.h>

int main(void)
{
    int number = 472;
    int hundreds = number / 100;
    int tens = number / 10 % 10;
    int units = number % 10;

    printf("%d %d %d\n", hundreds, tens, units);
    return 0;
}

Вывод:

4 7 2
  • 472 / 100 даёт 4: дробная часть отброшена.
  • 472 / 10 даёт 47; остаток 47 % 10 равен 7.
  • 472 % 10 даёт 2: последнюю цифру.

В двоичной системе — тот же принцип

Доступны только цифры 0 и 1. Поэтому веса разрядов увеличиваются в два раза:

Вес:    16   8   4   2   1
Цифра:   1   0   1   1   0
Вклад:  16   0   4   2   0

Складываем вклады: 16 + 4 + 2 = 22. Таким образом, 10110₂ — двоичная запись десятичного числа 22. Маленькая двойка обозначает основание системы; она не входит в число.

У каждого бита два варианта: 0 или 1. Два бита дают 2 × 2 = 4 комбинации: 00, 01, 10, 11. Каждый дополнительный бит удваивает количество вариантов; восемь битов дают 28=2562^8=256 комбинаций. Для беззнакового целого это значения от 0 до 255.

Для обратного перевода делим 22 на 2, каждый раз сохраняя остаток:

Делимое Целое частное Остаток
22 11 0
11 5 1
5 2 1
2 1 0
1 0 1

Первый остаток отделяет крайнюю правую цифру. Например, 22=2⋅11+022=2\cdot11+0: остаток 0 — цифра при весе 1, а в частном 11 остаётся число без этой цифры. Следующее деление 11=2⋅5+111=2\cdot5+1 отделяет цифру при весе 2 исходного числа. Так мы последовательно получаем разряды справа налево.

В таблице остатки записывались сверху вниз, начиная с крайней правой цифры. Само число пишется с левого разряда, поэтому читаем остатки снизу вверх: 10110.

Сложение и вычитание по разрядам

Как в десятичном сложении 9 + 1 создаёт перенос, в двоичном его создаёт 1 + 1. Результат — 10₂: в текущем разряде пишем 0, единицу переносим в следующий.

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

Идём справа налево: 1 + 0 = 1; затем 1 + 1 даёт 0 и перенос. В следующем разряде 0 + 1 + перенос снова даёт 0 и перенос. Затем 1 + 0 + перенос — ещё один 0; оставшаяся единица становится новым старшим разрядом.

При вычитании заём из соседнего разряда приносит две единицы текущего:

   10110₂    (22)
 - 00111₂    (7)
 --------
   01111₂    (15)

Справа 0 − 1 невозможно: заём у соседней 1 даёт 2 − 1 = 1, а соседняя 1 становится 0. Во втором разряде справа происходит то же самое: заём и результат 1. В третьем разряде заём проходит через соседний 0: он получает от старшей 1 две единицы своего разряда, одну передаёт вправо (там снова 2 − 1 = 1), другую оставляет себе. Поэтому третий и четвёртый разряды справа тоже дают 1, а старший — 0: 01111₂. Это тот же заём, что при вычитании в десятичном столбике.

Как это записывается в C

Фрагмент внутри main:

C
int decimal = 22;
int octal = 026;
int hexadecimal = 0x16;
printf("%d %d %d\n", decimal, octal, hexadecimal);

Вывод — 22 22 22. Начальный 0 задаёт восьмеричную запись, 0x — шестнадцатеричную. Восьмеричная использует цифры 0…7, шестнадцатеричная — 0…9 и A…F, где A означает 10, а F — 15.

В 026 значащие цифры 2 и 6 дают 2 × 8 + 6 = 22. В 0x16 цифры 1 и 6 дают 1 × 16 + 6 = 22. Префиксы сообщают основание, а не добавляют разряды к значению. Учебная запись 10110₂ с маленькой двойкой — математическое обозначение, её нельзя так же вставить в программу. А просто 10110 без префикса в исходнике означает десятичное число десять тысяч сто десять.

printf с %d выводит десятичную запись, независимо от того, как число было записано в исходнике. Не добавляйте ноль к целому литералу для красоты: 010 означает восемь, а не десять. Префикс 0b для двоичной записи не входит в стандарт C17.

ПрактикаЗагружаем тест…