Частный случай

Общий алгоритм перевода числа N из системы с основанием P в систему с основанием Q состоит в том, чтобы перевести N из системы P в десятичную систему, затем полученный результат перевести в систему Q.

В частном случае задачу можно существенно упростить. Когда? В том случае, если системы связаны соотношением: P = Q^m. Этому соотношению удовлетворяют такие пары как (2, 4), (3, 9),

(3, 27), (4, 16). Более важно, что этому условию удовлетворяют такие пары, как (2, 8) и (2, 16). Это означает, что для двоичной, восьмеричной и шестнадцатеричной системы счисления, - систем, наиболее употребительных в компьютерной науке, перевод делается достаточно просто.

Сформулируем правила перевода. Пусть системы счисления связаны соотношением:

P = Q^m

Для перевода числа N из системы P в систему Q достаточно каждую цифру числа N независимо перевести в систему Q, записав эту цифру с использованием m цифр системы Q. Старшие незначащие нули в полученной записи следует отбросить.

Пример: Перевести число N = FDC₁₆ из шестнадцатеричной системы в двоичную систему:

F₁₆ = 1111₂ D₁₆ = 1101₂ C₁₆ = 1100₂ N = 111111011100₂

Пример: N = 111₁₆

1₁₆ = 0001₂ N = 000100010001₂ = 100010001₂

N = 317₈ 3₈ = 011₂ 1₈ = 001₂ 7₈ = 111₂ N = 01100111₂ N = 1100111₂

Сформулируем теперь правило перевода из Q в P (P = Q^m)

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

Пример: N = 1010101111₂ Перевести N в шестнадцатеричную систему:

N = 10 1010 1111 = 0010 1010 1111 = 2AF₁₆

N = 1 010 101 111 = 001 010 101 111 = 1257₈

Осталось понять, почему эти правила справедливы и всегда применимы, когда P = Q^m. Вспомним базисное соотношение записи числа в позиционной системе:

N = c_k * q^k + c_k-1 * q^k-1 + … + c₁ * q¹ + c₀ * q⁰

Будем считать, что эта запись сделана в системе Q (Q < P). Перепишем это соотношение, разбивая запись на группы из m слагаемых.

N = c_k * q^k + c_k-1 * q^k-1 + … + c₁ * q¹ + c₀ * q⁰

Будем считать, что эта запись сделана в системе Q (Q < P). Перепишем это соотношение, разбивая запись на группы из m слагаемых.

N = (c₀ + c₁ * q + c₂ * q² + … + c_m-1 * q^m-1) + (c_m + c_m+1 * q + c_m+2 * q² + … + c_2m-1 * q^m-1)q^m + … + (…) (q^m)^k

Каждая круглая скобка устроена одинаково и представляет некоторое число в системе Q. Каков диапазон этих чисел? Минимальное число получается, когда все цифры c_j равны нулю. Тогда и число равно нулю. Максимальное число получается, когда все цифры c_j равны максимальной цифре, а ее значение в системе Q равно q-1.

Обозначим это значение как Max и посчитаем его:

Max = (q – 1) * (1 + q + q² + … + q^m-1) = q^m – 1 = p – 1

Следовательно, Max – это максимальная цифра в системе P, и каждой скобке в системе Q соответствует некоторая цифра в системе P.

Так что из разложения N в системе Q следует разложение в системе P

N = d₀ + d₁ * p + d₂ * p² + … + d_k * p^k,

Где d_j – цифры системы P, заменяющие скобки.

Задачи для самостоятельной работы