Конвертирование десятичных чисел в двоичные¶

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

Целые числа - очень распространённые элементы данных. Они постоянно используются в компьютерных программах и вычислениях. Мы изучаем их на уроках математики и, конечно, представляем в десятичной системе счисления (по основанию 10). Десятичное число \(233_{10}\) и связанный с ним эквивалент \(11101001_{2}\) соответственно интерпретируются как:

\(2\times10^{2} + 3\times10^{1} + 3\times10^{0}\)

и

\(1\times2^{7} + 1\times2^{6} + 1\times2^{5} + 0\times2^{4} + 1\times2^{3} + 0\times2^{2} + 0\times2^{1} + 1\times2^{0}\)

Но как нам легко конвертировать целые значения в бинарные числа? Ответ заключается в алгоритме под названием “Разделяй на 2”, который использует стек для запоминания цифр двоичного результата.

Алгоритм “Разделяй на 2” подразумевает, что мы начинаем с целого большего, чем нуль. Затем простыми итерациями последовательно делим десятичное число на два и записываем остаток. Первое деление пополам даёт информацию о том, является ли число чётным или нечётным. Чётное число будет иметь в остатке нуль и цифру 0 на первом месте. Нечётное значение будет иметь в остатке единицу и цифру 1 на первом месте. Мы думаем о построении нашего двоичного числа как о последовательности цифр; первый вычисленный нами остаток фактически будет последней цифрой в последовательности. Как показано на Рисунке 5, мы снова наблюдаем свойство разворота входных данных, сигнализирующее, что, вполне вероятно, подходящей структурой для решения задачи будет стек.

Рисунок 5: Преобразование числа из десятичного в бинарное

Код на Python в ActiveCode 6 реализует алгоритм “Разделяй на 2”. Функция <code>divideBy2</code> принимает десятичное число в качестве аргумента и последовательно делит его пополам. В строке 7 используется встроенный оператор остатка от деления %, чтобы выделить остаток и в строке 8 поместить его в стек. После того, как процесс деления закончится нулём, в строках 11-13 собирается бинарная последовательность. Строка 11 создаёт пустую строку. Из стека по одной выталкиваются двоичные цифры и добавляются к ней справа. В итоге возвращается бинарный результат.

Алгоритм бинарного преобразования может быть легко расширен для конвертации по любому основанию. В информатике широко используется несколько различных кодировок. Наиболее распространены двоичная, восьмеричная и шестнадцатиричная.

Десятичное число \(233\) и связанные с ним восьмеричный и шестнадцатиричный эквиваленты \(351_{8}\) и \(E9_{16}\) интерпретируются как:

\(3\times8^{2} + 5\times8^{1} + 1\times8^{0}\)

и

\(14\times16^{1} + 9\times16^{0}\)

Функция divideBy2 может быть модифицирована, чтобы принимать не только десятичные значения, но и основание для предназначенного преобразования. Идея “Разделяй на 2” просто заменяется на более общую “Разделяй на основание”. Новая функция под названием baseConverter, показанная в ActiveCode 7, принимает в качестве параметров десятичное число и любое основание между 2 и 16. Остатки по-прежнему помещаются в стек до тех пор, пока конвертируемое значение не станет равным нулю. Аналогичная техника конструирования слева направо может использоваться с одним небольшим изменением. От основания 2 до 10 для чисел нужно максимум 10 цифр, так что обычные символы 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9 работают нормально. Проблемы возникают, когда мы выходим за основание 10. Мы больше не можем использовать остатки, поскольку они сами представляются как двуциферные десятичные числа. Вместо них мы должны создать свой набор цифр, которые можно использовать для представления таких остатков за пределами 9.

Решением этой задачи будет расширить набор цифр включением некоторых алфавитных символов. Например, шестнадцатиричная система счисления использует десять десятичных цифр вместе с первыми шестью буквами алфавита для своих шестнадцати цифр. Чтобы воплотить это, создаётся цифровая строка (см. строку 4 в Листинге 6), как хранилище цифр на соответствующих позициях. 0 - на позиции 0, 1 - на позиции 1, А - на позиции 10, В - на позиции 11 и так далее. Когда остаток удаляется из стека, он может быть использован в качестве индекса в цифровой строке, и к концу ответа добавляется правильная итоговая цифра. Например, если из стека удаляется остаток 13, в результирующую строку добавляется цифра D.