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

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

Целые числа - очень распространённые элементы данных. Они постоянно используются в компьютерных программах и вычислениях. Мы изучаем их на уроках математики и, конечно, представляем в десятичной системе счисления (по основанию 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”. Функция divideBy2 принимает десятичное число в качестве аргумента и последовательно делит его пополам. В строке 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.