Из доказанной в предыдущей лекции теоремы существуют несколько интересных следствий. В частности, о правилах арифметических операций в 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\). Таким образом, имеем два варианта для каждого разряда:
- \(a_i + b_i < P\). Тогда \(c_i = a_i + b_i\) удовлетворяет условиям теоремы.
- \(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-ичной системы счисления. Рассмотрим несколько примеров.
| 0 | 1 | |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 10 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 10 |
| 2 | 2 | 3 | 4 | 5 | 6 | 7 | 10 | 11 |
| 3 | 3 | 4 | 5 | 6 | 7 | 10 | 11 | 12 |
| 4 | 4 | 5 | 6 | 7 | 10 | 11 | 12 | 13 |
| 5 | 5 | 6 | 7 | 10 | 11 | 12 | 13 | 14 |
| 6 | 6 | 7 | 10 | 11 | 12 | 13 | 14 | 15 |
| 7 | 7 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | 10 |
| 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | 10 | 11 |
| 3 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | 10 | 11 | 12 |
| 4 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | 10 | 11 | 12 | 13 |
| 5 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | 10 | 11 | 12 | 13 | 14 |
| 6 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | 10 | 11 | 12 | 13 | 14 | 15 |
| 7 | 7 | 8 | 9 | A | B | C | D | E | F | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 8 | 8 | 9 | A | B | C | D | E | F | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 9 | 9 | A | B | C | D | E | F | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| A | A | B | C | D | E | F | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| B | B | C | D | E | F | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 1A |
| C | C | D | E | F | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 1A | 1B |
| D | D | E | F | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 1A | 1B | 1C |
| E | E | F | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 1A | 1B | 1C | 1D |
| F | F | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 1A | 1B | 1C | 1D | 1E |
Пример:
\(\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\).
Тогда, имеем два варианта:
- \(a_j b_i<P\). Тогда \(c_j = a_j b_i\) удовлетворяет условиям теоремы.
- \(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\), а старший будет аддитивно перенесен в следующий.
Для облегчения умножения, существуют таблицы умножения. Их составление немного сложнее, чем таблиц сложения, однако при наличии таблиц сложения оказывается тоже достаточно простым.
| 0 | 1 | |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 2 | 0 | 2 | 4 | 6 | 10 | 12 | 14 | 16 |
| 3 | 0 | 3 | 6 | 11 | 14 | 17 | 22 | 25 |
| 4 | 0 | 4 | 10 | 14 | 20 | 24 | 30 | 34 |
| 5 | 0 | 5 | 12 | 17 | 24 | 31 | 36 | 43 |
| 6 | 0 | 6 | 14 | 22 | 30 | 36 | 44 | 52 |
| 7 | 0 | 7 | 16 | 25 | 34 | 43 | 52 | 61 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
| 2 | 0 | 2 | 4 | 6 | 8 | A | C | E | 10 | 12 | 14 | 16 | 18 | 1A | 1C | 1E |
| 3 | 0 | 3 | 6 | 9 | C | F | 12 | 15 | 18 | 1B | 1E | 21 | 24 | 27 | 2A | 2D |
| 4 | 0 | 4 | 8 | C | 10 | 14 | 18 | 1C | 20 | 24 | 28 | 2C | 30 | 34 | 38 | 3C |
| 5 | 0 | 5 | A | F | 14 | 19 | 1E | 23 | 28 | 2D | 32 | 37 | 3C | 41 | 46 | 4B |
| 6 | 0 | 6 | C | 12 | 18 | 1E | 24 | 2A | 30 | 36 | 3C | 42 | 48 | 4E | 54 | 5A |
| 7 | 0 | 7 | E | 15 | 1C | 23 | 2A | 31 | 38 | 3F | 46 | 4D | 54 | 5B | 62 | 69 |
| 8 | 0 | 8 | 10 | 18 | 20 | 28 | 30 | 38 | 40 | 48 | 50 | 58 | 60 | 68 | 70 | 78 |
| 9 | 0 | 9 | 12 | 1B | 24 | 2D | 36 | 3F | 48 | 51 | 5A | 63 | 6C | 75 | 7E | 87 |
| A | 0 | A | 14 | 1E | 28 | 32 | 3C | 46 | 50 | 5A | 64 | 6E | 78 | 82 | 8C | 96 |
| B | 0 | B | 16 | 21 | 2C | 37 | 42 | 4D | 58 | 63 | 6E | 79 | 84 | 8F | 9A | A5 |
| C | 0 | C | 18 | 24 | 30 | 3C | 48 | 54 | 60 | 6C | 78 | 84 | 90 | 9C | A8 | B4 |
| D | 0 | D | 1A | 27 | 34 | 41 | 4E | 5B | 68 | 75 | 82 | 8F | 9C | A9 | B6 | C3 |
| E | 0 | E | 1C | 2A | 38 | 46 | 54 | 62 | 70 | 7E | 8C | 9A | A8 | B6 | C4 | D2 |
| F | 0 | F | 1E | 2D | 3C | 4B | 5A | 69 | 78 | 87 | 96 | A5 | B4 | C3 | D2 | E1 |
Пример:
\(\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} \]
Автоматическое составление таблиц сложения и умножения
Несложно оказывается написать программу, которая автоматически строит таблицы сложения и умножения.
Некоторые примеры: