Системы счисления: задачи с пошаговыми решениями

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.