1.        Позиционные и непозиционные системы счисления

1.1.           Основные определения

Для записи информации о количестве объектов мы пользуемся числами. Числа записываются при помощи особых знаковых систем, называемых системами счисления. Система счисления - совокупность правил для записи чисел из символов исходного алфавита. Алфавит - конечный набор (множество) символов. Элементы алфавита мы будем называть цифрами. Можно составить любую комбинацию из символов исходного алфавита. Здесь и далее мы будем предполагать, что мы можем представить любое число, используя символы алфавита системы счисления. Системы счисления бывают позиционные и непозиционные. В позиционной системе счисления позиция цифры в числе влияет на ее значение, в непозиционных, соответственно, не влияет.

1.2.         Непозиционные системы счисления

Примером непозиционной системы счисления является унарная (единичная) система счисления. Основное ее применение - обучение детей счету. В ее алфавит входит единственная цифра - 1, а количество единиц соответствует количеству объектов. Так, число 111 в унарной системе счисления обозначает число 3 в десятичной. В числе 111 встречаются три цифры 1, и каждая из них обозначает одну величину - число “один”.

Еще одним классическим примером непозиционной системы счисления является римская система счисления (использовалась в Древнем Риме). Несмотря на то, что Римская империя рухнула многие сотни лет назад, римская система счисления применяется до сих пор, например,  в нумерации глав. Ее алфавит состоит из следующего набора цифр (здесь и далее в скобках указаны соответствующие цифры десятичной системы счисления):

 {I(1),V(5), X(10), L(50),C(100), D(500), M(1000)}.

Число составляется по следующим правилам:

1. Если меньшая цифра стоит слева от большей, то меньшая цифра вычитается из большей.
2. Если меньшая цифра стоит справа от большей, то обе цифры складываются. Одинаковые цифры так же складываются.

Примеры:

1. IX = 9.
2. MMXI = 1000 + 1000  +10  + 1 = 2011.
3. MCMXCVIII = 1000 +(-100 + 1000) + (-10 + 100) + 5 + 1 + 1 + 1 = 1999.

Очевидным недостатком непозиционных систем счисления является трудность записи больших чисел, они слишком длинные и при их записи легко допустить ошибку. Для простоты обозначения больших чисел постоянно вводились новые цифры. Кроме того, в той же самой римской системе счисления трудно совершать арифметические операции, т.к. не существует четких алгоритмов их вычисления.  Запись дробных и отрицательных чисел невозможна.

1.3.         Позиционные системы счисления

Вышеперечисленные недостатки решают позиционные системы счисления. Классическим примером позиционной системы счисления является десятичная (арабская) система счисления. В позиционных системах счисления количественное значение цифры зависит от того, какую позицию в числе она занимает. Основание позиционной системы счисления показывает, сколько чисел в алфавите системы счисления, а также определяет, во сколько раз различаются значения одинаковых цифр в соседних позициях числа. Основание системы счисления записывают нижним индексом рядом с числом. К примеру, число 11₁₀, 12₃, А₁₆. Позиционную систему счисления с основанием P принято называть P-ичной. Примерами позиционной системы счисления могут служить двоичная, троичная, восьмеричная, шестнадцатеричная и т.д (табл. 1).

 

Таблица  SEQ Таблица \* ARABIC 1. Примеры позиционных систем счисления.

Позиция цифры в числе называется разрядом. Для целых чисел разряды нумеруются справа налево, началом отсчета является 0.

Например, для числа 5710049₁₀ разряды нумеруются следующим образом:

Различают свернутую и развернутую форму записи числа. В нашем примере запись 5710049₁₀ является свернутой формой записи. В развернутой форме число запишется следующим образом:

5710049₁₀ = 5 * 10⁶ + 7 * 10⁵ + 1 * 10⁴ + 0 * 10³ + 0 * 10² + 4 * 10¹ + 9 * 10⁰

Т.е. для того, чтобы определить количественное значение цифры, мы умножаем ее на число, равное основанию системы счисления в степени, равной разряду рассматриваемой цифры. Это правило действует и для дробей. Счет разряда дробной части ведется слева направо, начиная от запятой. Для развернутой формы записи дробных частей используются отрицательные значения степеней.

Пример:

Число 45,367₁₀

45,367₁₀ = 4 * 10¹ + 5 * 10⁰ + 3 * 10^-1 + 6 * 10^-2 + 7 * 10^-3

В общем виде свернутая и развернутая запись числа A_Р  с n целых разрядов и m дробных выглядят следующим образом:

AP=i=-mn-1ai∙ Pi=an-1∙Pn-1+⋯+a0∙P0+a-1 ∙P-1+⋯+a-m∙P-m

 

Примеры:

101₂ = 1 * 2² + 0 * 2¹  + 1 * 2⁰

0,222₃ = 0 * 3⁰ + 2 * 3^-1 + 2 * 3^-2 + 2 * ^-3

347,4₈ = 3 * 8²+ 4 * 8¹ + 7 * 8⁰ + 4 * 8^-1

3A,B7₁₆ = 3 * 16¹  +10 * 16⁰ + 11 * 16^-1  +7 * 16^-2

Очень часто позиционные системы разделяются на однородные (P-ичные) и смешанные.

2.        Единственность представления чисел в Р-ичных системах счисления

Пусть Р – произвольное натуральное число, большее 1. Существует и единственно представление любого натурального числа А в виде:

А=an∙Pn+an-1∙Pn-1+⋯+a0,

Где 0≤ai<P, 0<i<n, an≠0

Доказательство:

Существование.В качестве доказательства приведем алгоритм построения с пояснениями. Числа Р⁰, Р¹, Р²… образуют монотонную возрастающую числовую последовательность. Из этого следует, что найдется такое число n, что

Pn≤A≤Pn+1,

Рассмотрим интервал [Pⁿ,Pⁿ⁺¹). Для начала разделим его на (P-1) равных частей. Получим интервалы [Pⁿ,2∙Pⁿ), [2∙Pⁿ,3∙Pⁿ), [3∙Pⁿ,4∙Pⁿ), …,[(P-1)∙Pⁿ,P∙Pⁿ). Длина каждого из этих интервалов равна P.

Из того, что

Pn≤A≤Pn+1,

Следует, что существует такое m, что

mPn≤A<(m+1)Pn+1,

Тогда  положим a_n = m. a_n≠0 по построению. Для нахождения a_n-1 повторим описанные выше  действия для числа (A - a_n∙Pⁿ). Найдем коэффициент a_n-1.

A’ = (A – a_n Pⁿ) Если это число меньше либо равно P, то a_n-1 = A’ и процесс останавливается. Если же нет, то находим a_h по описанной выше схеме, а затем применяем алгоритм уже к числу

A”=(A’ – a_h P^h)

Для тех номеров, которые находятся между n и h (h<i<n), полагаем a_i = 0.  Процесс завершится, т.к. каждый раз мы рассматриваем число меньшее, чем было изначально, а именно, когда

А-an∙Pn-an-1∙Pn-1-⋯-a0=0,

Единственность. Рассмотрим получившееся разложение

А=an∙Pn+an-1∙Pn-1+⋯+a0,

Пусть существует еще одно разложение числа А

А=a'k∙Pk+a'k-1∙Pk-1+⋯+a'0,

В первую очередь докажем, что n=k. Пусть это не так, и n>k. Оценим разложение

А=an∙Pn+an-1∙Pn-1+⋯+a0,

Снизу наименьшим возможным числом (старший разряд a_n = 1, остальные - 0).

A≥Pn

Разложение

А=a'k∙Pk+a'k-1∙Pk-1+⋯+a'0,

Оценим сверху максимально возможным числом (все разряды равны P-1).

А≤P-1∙Pk+P-1∙Pk-1+⋯+P-1=Pk+1- 1<Pk+1

Т.к. у нас n≥(k+1), то Pn≤A<Pk+1 . Из чего и из n>k следует, что n=k. Т.е. второе разложение имеет вид

А=a'n∙Pn+a'n-1∙Pn-1+⋯+a'0,

Теперь докажем, что все коэффициенты a’_i=a_i, для любого 0≤i≤n.Пусть в некотором разряде j (0≤j≤n)это не так, а для j<i≤n равенство выполняется. Рассмотрим числа

B=A- an∙Pn-…-aj+1∙Pj+1=aj∙Pj+aj-1∙Pj-1+⋯+a0,

B'=A- a'n∙Pn-…-a'j+1∙Pj+1=a'j∙Pj+a'j-1∙Pj-1+⋯+a'0,

Причем B=B’ при a_j≠a’_j. Это невозможно. Даже если a_j=a’_j+1, а a_j-1=…=а₀ = P-1, мы все равно не получим равенство. А если В≠В’, то и разложения на самом деле не равны одному числу. Получаем противоречие с утверждением о том, что число А представляется двумя разными разложениями.

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

3.1.           Сложение

Для выполнения этой операции используют таблицы сложения. По вертикали и по горизонтали откладываем числа алфавита. На пересечении строки и столбца получаем результат операции. При сложении двух чисел P-ичной системы счисления мы не можем перенести в старший разряд больше 1. Действительно, максимальная сумма, которую мы можем получить, будет результатом сложения двух максимальных цифр алфавита (P - 1) + (P - 1) = 2(P - 1) = 2P - 2 = P  + P - 2 = 1[P - 2]. Число “десятков” - 1, число “единиц” - P-2.

 

Примеры:

+1010111200001012   10111002     +1011,0121000,112 10100,002     +538478 1228     +46,02812,108   60,128    

3.2.         Вычитание

Для вычитания также используется таблица сложения. Предположим, мы вычитаем цифру b из числа a.

1. Ищем строку, именованную цифрой b.
2. В этой строке ищем цифру a.
3. Смотрим, какой цифрой именован столбец, на пересечении которого с цифрой получаем результат a.

Эта схема работает, если у нас a≥b. В противном случае, мы занимаем единицу старшего разряда и по вышеописанной схеме решаем 1a - b.

Примеры:

-10012  01102     00112       -100,102   01,002      11,002     -43,508   11,448          32,048  

3.3.         Умножение

По сути, это то же самое умножение столбиком, которые мы привыкли применять в десятичной системе счисления. Единственное отличие - для проведения этой операции в P-ичной системе нам необходимо использовать  таблицы сложения для этой P-инчной системы счисления.

Примеры:

 

×10111012         1012+10111012  10111012               1110100012           ×101,012  101,12+   101012  101012    000002         101012              11100,1112 

3.4.         Деление

Делим также “столбиком”, однако, как и в случае умножения, используем таблицы умножения и сложения для P-ичной системы счисления. В качестве примера приведем деление 69 на 3 в двоичной и восьмеричной системах счисления.

10001012|112101112-11                             0101                   -11                 100           -11            011     -11      01058|38278-6               25         -25            0

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

3.5.           Таблицы сложения и умножения (двоичная и восьмеричная система счисления)

Таблица  SEQ Таблица \* ARABIC 2. Таблица сложения в двоичной системе счисления.

 

Таблица  SEQ Таблица \* ARABIC 3. Таблица умножения в двоичной системе счисления.

ы

Таблица 4. Таблица сложения в восьмеричной системе счисления.

 

Таблица 5. Таблица умножения в восьмеричной системе счисления.

 

Вы и сами можете составить таблицу умножения или сложения для любого основания.

1. В крайних левом вертикальном и верхнем горизонтальном записываете алфавит  (цифры записываются по возрастанию). В ячейке, основанной на пересечении i строчки и j столбца будет записан результат операции.
2. Считаем i * j или i + j  как бы мы считали в обычной десятичной системе. Переводим результат в систему счисления с исходным основанием.

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

4.        Перевод чисел из Р-ичной системы счисления в десятичную

Алгоритм:

1)Записываем исходное число в развернутой форме.

2) Считаем полученную сумму.

Примеры:

101₂ = 1 * 2² + 0 * 2¹  + 1 * 2⁰  = 5₁₀

0,222₃ = 0 * 3⁰ + 2 * 3^-1 + 2 * 3^-2 + 2 * 3^-3 = 0,(962)₁₀ 

347,4₈ = 3 * 8² + 4 * 8¹ + 7 * 8⁰ + 4 * 8^-1 = 231,5₁₀

3A,B7₁₆ = 3 * 16¹  +10 * 16⁰  + 11 * 16^-1  +7 * 16^-2= 58, 71484375₁₀

5.        Перевод чисел из десятичной системы счисления в Р-ичную

5.1.         Перевод целой части числа

Алгоритм перевода рассмотрим на примере перевода из десятичной системы счисления в двоичную. Пусть необходимо перевести число 27₁₀ в двоичную систему счисления.

1. Разделим 27 на 2. Получим 13 и остаток 1. Значит, последняя цифра в двоичной системе счисления будет 1.
2. 13 /2  = 6 (остаток 1)
3. 6 /2  = 3 (остаток 0)
4. 3 / 2 = 1 (остаток 1)

Следовательно, 27₁₀ = 11011₂

Проверка:

11011₁₀ = 1 * 2⁴ + 1 * 2³ + 0 * 2² + 1 * 2¹ + 1 * 2⁰ = 16 + 8 + 0 + 2 + 1 = 27₁₀

Для других оснований аналогично. Переведем то же число в троичную систему счисления.

1. 27 / 3 = 9 (остаток 0)
2. 9 / 3 = 3 (остаток 0)
3. 3 / 3 = 1 (остаток 0)

Следовательно, 27₁₀ = 1000₃

Проверка:

1000₃ = 1 * 3³ + 0 + 0 + 0 + 0 = 27₁₀

Пусть теперь необходимо перевести число 27₁₀ в восьмеричную систему счисления.

1)27 \8 = 3 (остаток 3)

27₁₀ = 33₈

Проверка :

33₈ = 3 * 8 + 3 = 27₁₀

Перевести 27₁₀ в шестнадцатеричную систему счисления.

1) 27/16 = 1(остаток 11)

27₁₀ = 1B₁₆

Проверка :

1B₁₆ = 1 * 16 + 11 = 27₁₀

5.2.         Перевод дробной части числа

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

Примеры:

1. 0,25₁₀
   1. 0,25 * 2 = 0,5 (целая часть 0)
   2. 0,5  * 2 = 1,0 (целая часть1)
   3. 0,25 = 0, 01

 

1. 0,725₁₀
   1. 0,725 * 2 = 1,45 (целая часть1)
   2. 0,45 * 2 = 0,9 (целая часть0)
   3. 0.9 * 2 = 1,8  (целая часть1)
   4. 0,8 * 2 = 1,6  (целая часть1)
   5. 0.6 * 2 = 1,2  (целая часть1)
   6. 0,2 * 2 = 0,4  (целая часть0)
   7. 0.4 * 2 =0,8  (целая часть0)
   8. 0,8 * 2 = 1,6  (целая часть1)
   9. 0,725 = 0.101(1100)

Упражнение:  проделать самостоятельно для остальных систем счисления

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

6.1.         Перевод целой части числа

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

 

Таблица 6. Перевод из двоичной системы счисления в восьмеричную.

Таблица 7. Перевод из двоичной системы счисления в шестнадцатеричную.

Рассмотрим пример перевода из двоичной системы счисления в восьмеричную числа 1110101000001101101₂. Первым делом разбиваем число на триады, начиная с правого конца 1 110 101 000 001 101 101₂. Нам необходимо целое число триад, потому дописываем слева недостающие нули 001 110 101 000 001 101 101₂. Далее смотрим по таблице перевода, какому числу соответствует очередная триада в восьмеричной системе счисления 001 110 101 000 001 101 101₂ = 1650155₈.

Переведем то же самое число в шестнадцатеричную систему счисления. Записываем число, разбиваем его на группы по 4 с правого конца, если необходимо, дописываем слева недостающие нули. 0111 0101 0000 0110 1101₂. Далее действуем как и в случае с восьмеричной системой - ищем соответствующее число в таблице перевода.

0111 0101 0000 0110 1101₂  = 7506D₁₆

6.2.         Перевод из восьмеричной системы счисления в шестнадцатеричную и обратно

Для этого переведем число из восьмеричной системы счисления в двоичную, а уже из двоичной - в шестнадцатеричную. Обратно перевод производится аналогично.

Примеры.

46213732₈ = 100 110 010 001 011 111 011 010₂ = 1001 1001 0001 0111 1101 1010₂ = 9917DA₁₆

Перевод дробной части:

0,25₁₀ = 0,0100₂ = 0,2₈ = 0,4₁₆

Совет: для выполнения арифметических операций в двоичной системе счисления, бывает удобнее перевести число в шестнадцатеричную, выполнить соответствующие действия в ней, а результат перевести обратно в двоичную. Заметим, что ЭВМ используют этот же принцип, только все арифметические операции выполняются в двоичной системе счисления, а уже результат переводится в десятичную.

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

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

Существует также факториальная

АQ=k=1ndkk!,    0≤dk≤k

 

 и фиббоначиева

AQ=k=0nfkFk,

системы счисления. При записи числа в фиббоначиевой системе счисления F_k – числа Фиббоначи, коэффициенты f_k принимают значения 0 или 1, и в последовательности коэффициентов f_nf_n-1…f₀ нет двух подряд идущих единиц.

8.        Литература

1. С. Б. Гашков. Системы счисления и их применение. М.: МЦНМО, 2004. — 52 с.: ил.
2. Игорь Н. Бекман. Компьютеры в информатике. Лекция 4: Кодирование в информатике. [http://profbeckman.narod.ru/Komp.files/Lec4.pdf]
3. В. М. Казиев. Введение в информатику.  [http://www.intuit.ru/department/informatics/intinfo/4/1.html]

Е. А. Роганов. Практическая информатика. [http://www.intuit.ru/department/se/pinform/1/4.html