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

Арифметические операции в традиционных системах счисления

Рассмотрим два числа, \[ X_1 = \sum_{i=0}^n a_i P^i, \] \[ X_2 = \sum_{i=0}^m b_i P^i \]

Правила сложения

Правила сложения выводятся очевидным образом:

\[ Y = X_1 + X_2, \] \[ Y = \sum_{i=0}^{\mathrm{max}(m,n)} (a_i+b_i) P^i = \sum_{i=0}^{p} c_i P^i \]

Теперь, по условиям теоремы, \(0\leq c_i < P\). Поскольку так же \(0\leq a_i < P\), \(0\leq b_i < P\), то \(0\leq a_i+b_i \leq P+P-2\). Таким образом, имеем два варианта для каждого разряда:

1. \(a_i + b_i < P\). Тогда \(c_i = a_i + b_i\) удовлетворяет условиям теоремы.
2. \(P\leq a_i+b_i < 2P-1\). Тогда \[ Y = \ldots + (a_{i+1} + b_{i+1}) P^{i+1} + (a_i+b_i) P^i + \ldots,\] \[ Y = \ldots + (a_{i+1} + b_{i+1}) P^{i+1} + (a_i+b_i-P+P) P^i + \ldots,\] \[ Y = \ldots + (a_{i+1} + b_{i+1}) P^{i+1} + P^{i+1}+ (a_i+b_i-P) P^i + \ldots,\] \[ Y = \ldots + (a_{i+1} + b_{i+1}+1) P^{i+1} + (a_i+b_i-P) P^i + \ldots,\] и тогда \(c_i = a_i+b_i-P < P-1\) удовлетворяет условиям теоремы, а \(a_{i+1}+b_{i+1} +1 < 2P\) может быть рассмотрено аналогично.

Получаем правила сложения: числа складываются поразрядно, начиная с младшего. Если в результате сложения получается число меньшее основания системы счисления, переходим к следующему разряду. Иначе, из результата вычитается основание системы счисления \(P\) и “переносится” как 1 в следующий разряд.

Для облегчения задачи сложения, можно использовать так называемые таблицы сложения. Таблицы сложения составляются достаточно легко для любой P-ичной системы счисления. Рассмотрим несколько примеров.

Пример:

\(\begin{matrix} & A & 4 & D & {}_{16} \\ + & & 8 & C & {}_{16} \\ \hline{} &&&&{}_{16} \end{matrix}\qquad\) \(\begin{matrix} & A & 4 & D & {}_{16} \\ + & & 8 & C & {}_{16} \\ \hline{} &&\overset{1}{}&9&{}_{16} \end{matrix}\qquad\) \(\begin{matrix} & A & 4 & D & {}_{16} \\ + & & 8 & C & {}_{16} \\ \hline{} &&\overset{1}{C}&9&{}_{16} \end{matrix}\qquad\) \(\begin{matrix} & A & 4 & D & {}_{16} \\ + & & 8 & C & {}_{16} \\ \hline{} &A&\overset{1}{C}&9&{}_{16} \end{matrix}\qquad\) \(\begin{matrix} & A & 4 & D & {}_{16} \\ + & & 8 & C & {}_{16} \\ \hline{} &A&\overset{1}{C}&9&{}_{16} \\ \hline{} &A&D&9&{}_{16} \end{matrix}\qquad\)

Правила умножения

\[ Y = X_1 \cdot X_2, \] \[ Y = \left(\sum_{i=0}^n a_i P^i\right) \cdot \left(\sum_{i=0}^m b_i P^i\right) \]

Раскрывая вторые скобки, получаем:

\[ Y = \sum_{i=0}^m b_i P^i \left(\sum_{j=0}^n a_j P^j\right) \]

Внося \(P^i\) в скобку,

\[ Y = \sum_{i=0}^m b_i \left(\sum_{j=0}^n a_j P^{j+i}\right) \]

Обозначим \[ Y_i = b_i \cdot \sum_{j=0}^n a_j P^j \]

Тогда \[ Y = \sum_{i=0}^m Y_i P^i \]

Таким образом, каждый разряд \(b_i\) умножается на число \(X_1\), результат смещается на \(i\) разрядов влево (умножается на \(P^i\)), затем все промежуточные результаты складываются (правила сложения нам уже известны).

Рассмотрим теперь умножение на один разряд:

\[ Y_i = b_i \cdot \sum_{j=0}^n a_j P^j = \sum_{j=0}^n a_j b_i P^j = \sum_{j=0}^n c_j P^j .\]

По условиям теоремы, \(0\le c_j < P\). В то же время, \(0 \le a_j b_j \le (P-1)^2\). \((P-1)^2 = P^2 - 2P + 1 < P^2\).

Тогда, имеем два варианта:

1. \(a_j b_i<P\). Тогда \(c_j = a_j b_i\) удовлетворяет условиям теоремы.
2. \(P \le a_j b_i \le (P-1)^2\). Тогда можем разложить \(a_j b_i = p_j P + c_j\). В разложении не может быть больше двух членов, поскольку \(a_j b_i < P^2\). \(c_j\) очевидно удовлетворяет условиям теоремы, а следующий разряд получает “перенос” \(p_j\): \(a_j b_i + p_j \le P^2 - 2P + 1 + P-1 = P^2-P < P^2\) и может быть рассмотрен аналогично.

Получаем правила умножения: Каждый разряд второго операнда умножается на первый операнд, причем результат смещается на положение этого разряда. Первый операнд умножается на разряд второго поразрядно, начиная с младшего, причем, если результат больше основания системы счисления P, то, записанный в P-ичной системе счисления результат будет иметь два разряда, младший из которых определит текущий разряд промежуточного результата \(Y_i\), а старший будет аддитивно перенесен в следующий.

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

Пример:

\(\begin{matrix} & & A & E & {}_{16} \\ \times & & 3 & E & {}_{16} \\ \hline{} \end{matrix}\qquad\) \(\begin{matrix} & & A & \underline E & {}_{16} \\ \times & & 3 & \underline E & {}_{16} \\ \hline{} & & C & 4 & {}_{16} \end{matrix}\qquad\) \(\begin{matrix} & & \underline A & E & {}_{16} \\ \times & & 3 & \underline E & {}_{16} \\ \hline{} & & C & 4 & {}_{16} \\ + & 8 & C & & {}_{16} \end{matrix}\qquad\) \(\begin{matrix} & & A & \underline E & {}_{16} \\ \times & & \underline 3 & E & {}_{16} \\ \hline{} & & C & 4 & {}_{16} \\ + & 8 & C & & {}_{16} \\ + & 2 & A & & {}_{16} \\ \end{matrix}\qquad\) \(\begin{matrix} & & \underline A & E & {}_{16} \\ \times & & \underline 3 & E & {}_{16} \\ \hline{} & & & C & 4 & {}_{16} \\ + & & 8 & C & & {}_{16} \\ + & & 2 & A & & {}_{16} \\ + & 1 & E & & & {}_{16} \\ \end{matrix}\qquad\) \(\begin{matrix} & & A & E & {}_{16} \\ \times & & 3 & E & {}_{16} \\ \hline{} & & & C & 4 & {}_{16} \\ + & & 8 & C & & {}_{16} \\ + & & 2 & A & & {}_{16} \\ + & 1 & E & & & {}_{16} \\ \hline{} & \overset{1}{1} & \overset{2}{8} & 2 & 4 & {}_{16} \\ \hline{} & 2 & A & 2 & 4 & {}_{16} \end{matrix}\qquad\)

Правила вычитания и деления

Правила вычитания и деления, как можно понять, абсолютно аналогичны правилам вычитания и деления в столбик в десятичной системе счисления, с той поправкой, что максимальная цифра ограничивается основанием системы счисления \(P\).

Для вычитания можно использовать таблицы сложения, а для деления – таблицы умножения и сложения.

Пример вычитания:

\(\begin{matrix} & A & 4 & D & {}_{16} \\ - & & 8 & C & {}_{16} \\ \hline{} &&&&{}_{16} \end{matrix}\qquad\) \(\begin{matrix} & A & 4 & D & {}_{16} \\ - & & 8 & C & {}_{16} \\ \hline{} &&&1&{}_{16} \end{matrix}\qquad\) \(\begin{matrix} & \dot A & 4 & D & {}_{16} \\ - & & 8 & C & {}_{16} \\ \hline{} &&C&1&{}_{16} \end{matrix}\qquad\) \(\begin{matrix} & \dot A & 4 & D & {}_{16} \\ - & & 8 & C & {}_{16} \\ \hline{} &9&C&1&{}_{16} \end{matrix}\qquad\)

Пример деления:

\(\begin{matrix} 8 & D & 6 & {}_{16} \\ & & & \end{matrix}\begin{array}{|llll} D_{16} & \\ \hline{} & \\ \end{array}\)

\(\begin{matrix} & 8 & D & 6 & {}_{16} \\ - & 8 & 2 & & \\ \hline{} & & B & 6 \end{matrix} \begin{matrix} \begin{array}{|llll} D & {}_{16} & \\ \hline{} A \end{array} \\ & \end{matrix}\)

\(\begin{matrix} & 8 & D & 6 & {}_{16} \\ - & 8 & 2 & & \\ \hline{} & & B & 6 \\ & - & B & 6 \\ \hline{} &&& 0 \end{matrix} \begin{matrix} \begin{array}{|llll} D & {}_{16} & \\ \hline{} A & E & {}_{16} \end{array} \\ & \\ & \\ & \end{matrix}\)

Правила преобразования чисел между системами счисления.

Другим интересным следствием теоремы о единственности представления чисел является преобразование чисел между системами счисления.

Преобразование чисел в десятичную систему счисления

Если дано число \(X\) в P-ичной системе счисления, то для его перевода в десятичную, достаточно записать представление в виде числового ряда в десятичной системе и вычислить получившееся выражение. Другими словами, каждую цифру перевести в десятичную систему, домножить на ее “вес” (в десятичной системе) и сложить полученные числа.

Например:

\[ ACE_{16} = 10 \cdot 16^2 + 12 \cdot 16 + 14 = 2560 + 192 + 14 = 2766 \]

\[ 10100101110110_2 = 2 + 4 + 16 + 32 + 64 + 256 + 2048 + 8192 = 10614 \]

Преобразование чисел из десятичной системы счисления

Рассмотрим разложение числа \(X\) в P-ичной системе счисления:

\[ X = a_n P^n + \ldots + a_1 P^1 + a_0 \]

Если разделить \(X\) на \(P\) с остатком, то получим

\[ \frac{X}{P} = \frac{a_n P^n + \ldots + a_1 P^1 + a_0}{P} \] \[ \frac{X}{P} =a_n P^{n-1} + \ldots + a_1 + \frac{a_0}{P}, \]

то есть \(a_0\) – остаток, а \((a_n P^{n-1} + \ldots + a_1)\) – частное. Если теперь разделить частное на \(P\), получим:

\[\frac{a_n P^{n-1} + \ldots + a_1}{P}= a_n P^{n-2} + \ldots + a_2 + \frac{a_1}{P}.\]

Ясно, что мы можем повторить эту процедуру \(n\) раз, и в результате получим \(0\) в частном и \(a_n\) в остатке.

Таким образом, мы можем получить значения всех разрядов в P-ичном числе, пользуясь его десятичным представлением.

Пример:

\[ 9283_{10} = {?}_2 \] \[ 9283/2 = 4641\;(1)\] \[ 4641/2 = 2320\;(1)\] \[ 2320/2 = 1160\;(0)\] \[ 1160/2 = 580\;(0)\] \[ 580/2 = 290\;(0)\] \[ 290/2 = 145\;(0)\] \[ 145/2 = 72\;(1)\] \[ 72/2 = 36\;(0)\] \[ 36/2 = 18\;(0)\] \[ 18/2 = 9\;(0)\] \[ 9/2 = 4\;(1)\] \[ 4/2 = 2\;(0)\] \[ 2/2 = 1\;(0)\] \[ 1/2 = 0\;(1)\]

Получаем, \[ 9283_{10} = 10010001000011_2 \]

Аналогично, \[ 9283_{10} = {?}_{16} \] \[ 9283/16 = 580\;(3)\] \[ 580/16 = 36\;(4)\] \[ 36/16 = 2\;(4)\] \[ 2/16 = 0\;(2)\] \[ 9283_{16} = 2443_{16}\]

Смешанные системы счисления

Смешанная система счисления

это система счисления с основанием \(Q\), в которой для записи цифр используются числа в системе счисления с основанием \(P\).

Пример смешанного двоично-шестнадцатиричного числа: \[ {[1011_2][1110_2][1110_2][1111_2]}_{16} \]

Пример смешанного десятично-шестнадцатиричного числа:

\[ {[11][14][14][15]}_{16} \]

Интересная особенность проявляется в PQ-ичных системах счисления, в которых основание Q – это степень основания P.

Рассмотрим две системы счисления с основаниями \(P\) и \(Q\), причем \(Q = P^k\), где \(m\in\mathbb{N}\). Тогда число \(X\) можно разложить как \[ X = \sum_{i=0}^n a_i P^i, \] \[ X = \sum_{j=0}^{m} b_j Q^j.\]

Приравняв оба представления и подставив \(Q = P^k\),

\[ \sum_{i=0}^n a_i P^i = \sum_{j=0}^{m} b_j P^{kj}\] \[ a_n P^n + \ldots + a_{2k-1} P^{2k-1} + \ldots + a_{k} P^{k} + a_{k-1} P^{k-1} + \ldots + a_0 = b_m P^{km} + \ldots + b_1 P^k + b_0\] \[ a_n P^n + \ldots + \left( a_{2k-1} P^{k-1} + \ldots + a_{k}\right) P^{k} + a_{k-1} P^{k-1} + \ldots + a_0 = b_m P^{km} + \ldots + b_1 P^k + b_0.\]

Пользуясь методом неопределенных коэффициентов, можем сказать, что

\[b_0 = a_{k-1} P^{k-1} + \ldots + a_0,\] \[b_1 = a_{2k-1} P^{k-1} + \ldots + a_k,\] \[\ldots\]

Получаем, что каждая Q-ичная цифра соответствует P-ичному числу из \(k\) цифр, и наоборот.

Эта связь позволяет легко переводить числа между системами счисления с основаниями \(P\) и \(Q\), если \(Q = P^k\).

Для перевода из P-ичной в Q-ичную, число разбивается на группы по \(k\) P-ичных цифр, и каждая из групп переводится в Q-ичную систему счисления.

Для перевода из Q-ичной в P-ичную, каждая Q-ичная цифра переводится в P-ичную систему счисления, и при необходимости дополняется слева нулями до \(k\) цифр.

Пример:

\[ BEEF_{16} = {?}_{2} \] \[ B_{16} = 1011_{2} \] \[ E_{16} = 1110_{2} \] \[ F_{16} = 1111_{2} \] \[ BEEF_{16} = {[1011_2][1110_2][1110_2][1111_2]}_{16} = {1011\,1110\,1110\,1111}_{2} \]

Автоматическое составление таблиц сложения и умножения

Несложно оказывается написать программу, которая автоматически строит таблицы сложения и умножения.

Некоторые примеры:

• Haskell
• C++
• Python
• JavaScript
• PHP
• Онлайн-версия (исходник)