• единственность от противного.
• Пусть \(\exists\) два разных представления
• \[X_1 = \sum_{i=0}^n a_i P^i ; \; X_2 = \sum_{i=0}^m b_i P^i\]
• \[ X_1 = X_2 \]

• если \(m>n\), то \(X_2 > X_1\)
• оценим \(X_2\) снизу: \(b_m=1\), \(b_{i\neq m} = 0\).
• оценим \(X_1\) сверху: \(a_i = P-1\). Получим:
• \[X_1 \leq (P-1) \sum_{i=0}^n P^i ; \; X_2 \geq P^m\]

• По формуле первых n членов геометрической прогрессии,

• \[X_1 \leq P^{n+1}-1 < P^{n+1}\]

• Если \(m>n\), то \(P^m \geq P^{n+1}\), следовательно, \(X_2 > X_1\), что противоречит \(X_2 = X_1\). Следовательно, \(m=n\).

• Пусть \(\exists k \le n: \forall i\in [k-1,n],\, a_i=b_i;\; a_k\neq b_k\).
• Оценим разность \(X_1 - X_2\) по модулю снизу.

\[ | X_1 - X_2 | \geq 1\]

• \(X_1 \neq X_2\)
• Противоречие предположению, что \(X_1 = X_2\)
• следовательно, \(\forall i: a_i = b_i\)
• представления \(X_1\) и \(X_2\) эквивалентны

• В теории доказывается другая теорема: любое неотрицательное вещественное число можно представить (не обязательно единственным образом) в виде \[ X = \sum_{i=-\infty}^n a_i P^i. \]
• Пример неоднозначного представления: \(0.1(9) = 0.2\)
• Числа, представление которых содержит отрицательные степени \(P\) будем называть P-ичными дробями.

• несколько интересных следствий
• о правилах арифметических операций
• о преобразовании чисел между системами счисления.

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

\[ 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\). Тогда

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

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

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

Таблицы сложения

Пример:

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

\[ Y = X_1 \cdot X_2, \]

• Обозначим \(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\))
• промежуточные результаты складываются

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

• по условиям, \(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 \le P-1\)
• \(a_{j+1} b_i + p_j \le P^2 - 2P + 1 + P-1\) \(= P^2-P < P^2\) может быть рассмотрен аналогично.

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

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

Таблицы умножения

Пример

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

• абсолютно аналогичны правилам в десятичной системе счисления
• максимальная цифра ограничивается основанием системы счисления \(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\) с остатком, то получим

• \(a_0\) – остаток
• \((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\) в остатке.
• каждый раз в остатке получаем следующий по старшинству разряд

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

• особенность PQ-ичных систем счисления, в которых основание \(Q = P^k\), \(k\in\mathbb{N}\)
• \[ X = \sum_{i=0}^n a_i P^i;\; X = \sum_{j=0}^{m} b_j Q^j.\]

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

\[ 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\) цифр.

• ячейки будем называть разрядами.
• под хранение информации отводится конечное число разрядов.
• Группы разрядов фиксированного размера называются регистрами.
• Забегая вперед, двоичный разряд хранит количество информации, называемое бит (от binary digit)
• Регистр, состоящий из \(n\) разрядов называется \(n\)-битным

Беззнаковое представление

• не допускает отрицательных чисел.
• числа представляются в памяти аналогично двоичным
• Одно из состояний разряда считается эквивалентным нулю, другое – единице.
• Тогда последовательно записанное в двоичной системе целое число очевидным образом транслируется на состояние регистра.

Пример:

• количество разрядов в регистре ограничено
• есть ограничение на максимально представимое число
• Минимально представимое число для беззнакового – всегда 0.
• например, в 8 разрядах максимально представимое \(11111111_2 = FF_{16} = 255_{10}\)
• Общая формула для максимально представимого числа в \(n\) разрядах \(I_{max} = 2^{n} - 1\)

Некоторые распространенные примеры:

Типовый вывод:

unsigned char 8
unsigned short 16
unsigned int 32
unsigned long 64
unsigned long long 64

• важное следствие конечности числа разрядов
• при попытке представить число больше максимально представимого – целочисленное переполнение
• старшие разряды отбрасываются
• Одно из ключевых следствий – в \(n\) разрядах число \(2^n\) представляется так же, как \(0\)
• На основе этого свойства строится представление отрицательных чисел.