Краткие сведения из курса двоичной арифметики

Как вам должно быть известно, человечество для своих целей в основном использует 10-ую систему счисления, которая содержит 10 цифр (0-9), а число 10 называется основанием системы счисления. Наша система счисления - позиционная, то есть число зависит от позиций содержащихся в нем цифр (пример непозиционной системы счисления - римская). Рассмотрим число 12345.

12345₁₀ = 1 * 10⁴ + 2 * 10³ + 3 * 10² + 4 * 10¹ + 5 * 10⁰

Следовательно, любое 10-ое число можно разложить на составляющие. Для этого достаточно сложить произведения всех цифр на 10 (основание системы счисления) в степени позиции цифры в числе, где позиции отсчитываются от 0 справа налево. Данное правило справедливо для любой позиционной системы счисления.

К данному моменту вам должно быть также известно, что компьютер оперирует 2-ой системой счисления, содержащей 2 цифры 0 и 1. К этой системе счисления (она таки позиционная) применимо описанное выше правило. Например,

101010₂ = 1 * 2⁵ + 0 * 2⁴ + 1 * 2³ + 0 * 2² + 1 * 2¹ + 0 * 2⁰ = 42₁₀

Но для человека оперировать 2-ой системой счисления неудобно, так как она слишком громоздкая. Поэтому в программировании чаще всего используется более компактная система счисления по основанию 16 (реже используется система счисления по основанию 8). 16-ая система счисления содержит 10 цифр (0-9) и 6 чисел, которые кодируются буквами латинского алфавита (A-F). Для хранения 16-ой цифры требуется log₂16 = 4 двоичных разряда (для 8-ой системы счисления, соответственно, 3 разряда).

Примечание: для тех, кто собирается связать свое будущее с программированием необходимо помнить следуюшую таблицу:

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

Частный случай - системы счисления по основанию степени двойки

Системы счисления, основание которых является степенью двойки (4-ая, 8-ая, 16-ая и т. д.), легко преобразуются одна в другую через двоичную систему счисления.

Пример перевода числа из 2-ой СС в 16-ую СС. Для перевода необходимо брать по 4 разряда числа, отсчитывая справа налево, и кодировать их 16-ой цифрой. В случае если разрядов не хватает, перед числом дописывают нули.

10100101101₂ = 0101 0010 1101₂ = 52D₁₆

Пример перевода числа из 2-ой СС в 8-ую СС. Для перевода необходимо брать по 3 разряда числа, отсчитывая справа налево, и кодировать их 8-ой цифрой. В случае если разрядов не хватает, перед числом дописывают нули.

10100101101₂ = 010 100 101 101₂ = 2455₈

Процесс перевода чисел из СС, основанием которой является степень двойки, в двоичную аналогичен. Для этого необходимо каждую цифру числа заменить на соответствующий ей двоичный код. Пример:

1AC4₁₆ = 0001 1010 1100 0100₂ = 1101011000100₂

Общий случай - системы счисления по любому основанию

Для перевода числа из любой СС в 10-ую есть два способа. Пусть B - основание СС, d - цифра числа, X - число, n - количество цифр в числе.

Математический способ:

X₁₀ = d₁ * B^n-1 + d₂ * B^n-2 + ... + d_n

1AC4₁₆ = 1 * 16³ + 10 * 16² + 12 * 16¹ + 4 * 16⁰ = 6852₁₀

Итерационный способ:

X₁₀ = ((d₁ * B + d₂) * B + d₃) * B + ... + d_n

1AC4₁₆ = ((1 * 16 + 10) * 16 + 12) * 16 + 4 = 6852₁₀

Для перевода из 10-ой СС в любую другую можно предложить следующий алгоритм:

1. Делим 10-ое число X на B (основание СС, в которую осуществляется перевод) нацело. Получаем новое число X и остаток P. Запоминаем остаток.
2. Продолжаем выполнение шага 1 до тех пор пока число X != 0.
3. Собираем запомненные остатки в обратном порядке и получаем число X в системе счисления B.

Пример:

12345₁₀ = 3039₁₆

Примечание: При переводе в 2-ую СС из 10-ой рациональнее будет перевести число в 16-ую СС (меньше операций деления), а затем из 16-ой СС перевести в 2-ую с помощью ранее описанного способа.