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

Поскольку одно и то же число может быть записано в различных системах счисления, встает вопрос о переводе представления числа из одной системы (р) в другую (q) - будем обозначать такое преобразование Z_p → Z_q. Теоретически возможно произвести его при любых q и р. Однако подобный прямой перевод будет затруднен тем, что придется выполнять операции по правилам арифметики недесятичных систем счисления. По этой причине более удобными с практической точки зрения оказываются варианты преобразования с промежуточным переводом Z_p → Z_r → Z_q с основанием r, для которого арифметические операции выполнить легко. Такими удобными основаниями являются r =1 и r = 10, т.е. перевод осуществляется через унарную или десятичную систему счисления.

Преобразование Z_p → Z₁ → Z_q

Идея алгоритма перевода предельно проста: положим начальное значение Z_q:= 0; из числа Z_p вычтем 1 по правилам вычитания системы р, т.е. Z_P: = Z_P – 1* и добавим ее к Z_q по правилам сложения системы q, т.е. Z_q:= Z_q + 1; будем повторять эту последовательность действий, пока не достигнем Z_p = 0.

* Знак «:=» используется здесь и далее в смысле «присвоить» («считать равным»).

Правила сложения с 1 и вычитания 1 могут быть записаны следующим образом:

Промежуточный переход к унарной системе счисления в данном случае осуществляется неявно - используется упоминавшееся выше свойство независимости значения числа от формы его представления. Рассмотренный алгоритм перевода может быть легко реализован программным путем, в частности, машиной Тьюринга (см. п.7.3.3).

Вернуться в оглавление: Теоретические основы информатики