1. Позиционные и непозиционные системы счисления
1.1. Основные определения
Для записи информации о количестве объектов мы пользуемся числами. Числа записываются при помощи особых знаковых систем, называемых системами счисления. Система счисления - совокупность правил для записи чисел из символов исходного алфавита. Алфавит - конечный набор (множество) символов. Элементы алфавита мы будем называть цифрами. Можно составить любую комбинацию из символов исходного алфавита. Здесь и далее мы будем предполагать, что мы можем представить любое число, используя символы алфавита системы счисления. Системы счисления бывают позиционные и непозиционные. В позиционной системе счисления позиция цифры в числе влияет на ее значение, в непозиционных, соответственно, не влияет.
1.2. Непозиционные системы счисления
Примером непозиционной системы счисления является унарная (единичная) система счисления. Основное ее применение - обучение детей счету. В ее алфавит входит единственная цифра - 1, а количество единиц соответствует количеству объектов. Так, число 111 в унарной системе счисления обозначает число 3 в десятичной. В числе 111 встречаются три цифры 1, и каждая из них обозначает одну величину - число “один”.
Еще одним классическим примером непозиционной системы счисления является римская система счисления (использовалась в Древнем Риме). Несмотря на то, что Римская империя рухнула многие сотни лет назад, римская система счисления применяется до сих пор, например, в нумерации глав. Ее алфавит состоит из следующего набора цифр (здесь и далее в скобках указаны соответствующие цифры десятичной системы счисления):
{I(1),V(5), X(10), L(50),C(100), D(500), M(1000)}.
Число составляется по следующим правилам:
- Если меньшая цифра стоит слева от большей, то меньшая цифра вычитается из большей.
- Если меньшая цифра стоит справа от большей, то обе цифры складываются. Одинаковые цифры так же складываются.
Примеры:
- IX = 9.
- MMXI = 1000 + 1000 +10 + 1 = 2011.
- MCMXCVIII = 1000 +(-100 + 1000) + (-10 + 100) + 5 + 1 + 1 + 1 = 1999.
Очевидным недостатком непозиционных систем счисления является трудность записи больших чисел, они слишком длинные и при их записи легко допустить ошибку. Для простоты обозначения больших чисел постоянно вводились новые цифры. Кроме того, в той же самой римской системе счисления трудно совершать арифметические операции, т.к. не существует четких алгоритмов их вычисления. Запись дробных и отрицательных чисел невозможна.
1.3. Позиционные системы счисления
Вышеперечисленные недостатки решают позиционные системы счисления. Классическим примером позиционной системы счисления является десятичная (арабская) система счисления. В позиционных системах счисления количественное значение цифры зависит от того, какую позицию в числе она занимает. Основание позиционной системы счисления показывает, сколько чисел в алфавите системы счисления, а также определяет, во сколько раз различаются значения одинаковых цифр в соседних позициях числа. Основание системы счисления записывают нижним индексом рядом с числом. К примеру, число 1110, 123, А16. Позиционную систему счисления с основанием P принято называть P-ичной. Примерами позиционной системы счисления могут служить двоичная, троичная, восьмеричная, шестнадцатеричная и т.д (табл. 1).
Таблица SEQ Таблица \* ARABIC 1. Примеры позиционных систем счисления.
Позиционная система счисления | Основание | Алфавит |
Двоичная | 2 | 0, 1 |
Троичная | 3 | 0, 1, 2 |
Восьмеричная | 8 | 0, 1, 2, 3, 4, 5, 6, 7 |
Десятичная | 10 | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 |
Шестнадцатеричная | 16 | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A(10), B(11), C(12), D(13), E(14), F(15) |
Позиция цифры в числе называется разрядом. Для целых чисел разряды нумеруются справа налево, началом отсчета является 0.
Например, для числа 571004910 разряды нумеруются следующим образом:
Цифра | 5 | 7 | 1 | 0 | 0 | 4 | 9 |
Разряд | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
Различают свернутую и развернутую форму записи числа. В нашем примере запись 571004910 является свернутой формой записи. В развернутой форме число запишется следующим образом:
571004910 = 5 * 106 + 7 * 105 + 1 * 104 + 0 * 103 + 0 * 102 + 4 * 101 + 9 * 100
Т.е. для того, чтобы определить количественное значение цифры, мы умножаем ее на число, равное основанию системы счисления в степени, равной разряду рассматриваемой цифры. Это правило действует и для дробей. Счет разряда дробной части ведется слева направо, начиная от запятой. Для развернутой формы записи дробных частей используются отрицательные значения степеней.
Пример:
Число 45,36710
Цифра | 4 | 5 | 3 | 6 | 7 |
Разряд | 1 | 0 | -1 | -2 | -3 |
45,36710 = 4 * 101 + 5 * 100 + 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
Примеры:
1012 = 1 * 22 + 0 * 21 + 1 * 20
0,2223 = 0 * 30 + 2 * 3-1 + 2 * 3-2 + 2 * -3
347,48 = 3 * 82+ 4 * 81 + 7 * 80 + 4 * 8-1
3A,B716 = 3 * 161 +10 * 160 + 11 * 16-1 +7 * 16-2
Очень часто позиционные системы разделяются на однородные (P-ичные) и смешанные.
2. Единственность представления чисел в Р-ичных системах счисления
Пусть Р – произвольное натуральное число, большее 1. Существует и единственно представление любого натурального числа А в виде:
А=an∙Pn+an-1∙Pn-1+⋯+a0,
Где 0≤ai<P, 0<i<n, an≠0
Доказательство:
Существование.В качестве доказательства приведем алгоритм построения с пояснениями. Числа Р0, Р1, Р2… образуют монотонную возрастающую числовую последовательность. Из этого следует, что найдется такое число n, что
Pn≤A≤Pn+1,
Рассмотрим интервал [Pn,Pn+1). Для начала разделим его на (P-1) равных частей. Получим интервалы [Pn,2∙Pn), [2∙Pn,3∙Pn), [3∙Pn,4∙Pn), …,[(P-1)∙Pn,P∙Pn). Длина каждого из этих интервалов равна P.
Из того, что
Pn≤A≤Pn+1,
Следует, что существует такое m, что
mPn≤A<(m+1)Pn+1,
Тогда положим an = m. an≠0 по построению. Для нахождения an-1 повторим описанные выше действия для числа (A - an∙Pn). Найдем коэффициент an-1.
A’ = (A – an Pn) Если это число меньше либо равно P, то an-1 = A’ и процесс останавливается. Если же нет, то находим ah по описанной выше схеме, а затем применяем алгоритм уже к числу
A”=(A’ – ah Ph)
Для тех номеров, которые находятся между n и h (h<i<n), полагаем ai = 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,
Снизу наименьшим возможным числом (старший разряд an = 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=ai, для любого 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’ при aj≠a’j. Это невозможно. Даже если aj=a’j+1, а aj-1=…=а0 = 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.
- Ищем строку, именованную цифрой b.
- В этой строке ищем цифру a.
- Смотрим, какой цифрой именован столбец, на пересечении которого с цифрой получаем результат 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. Таблица сложения в двоичной системе счисления.
+ | 0 | 1 |
0 | 0 | 1 |
1 | 1 | 10 |
Таблица SEQ Таблица \* ARABIC 3. Таблица умножения в двоичной системе счисления.
* | 0 | 1 |
0 | 0 | 0 |
1 | 0 | 1 |
ы
Таблица 4. Таблица сложения в восьмеричной системе счисления.
+ | 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 |
Таблица 5. Таблица умножения в восьмеричной системе счисления.
* | 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 |
Вы и сами можете составить таблицу умножения или сложения для любого основания.
- В крайних левом вертикальном и верхнем горизонтальном записываете алфавит (цифры записываются по возрастанию). В ячейке, основанной на пересечении i строчки и j столбца будет записан результат операции.
- Считаем i * j или i + j как бы мы считали в обычной десятичной системе. Переводим результат в систему счисления с исходным основанием.
В качестве упражнения можете составить таблицы умножения и сложения для троичной и шестнадцатеричной систем счисления.
4. Перевод чисел из Р-ичной системы счисления в десятичную
Алгоритм:
1)Записываем исходное число в развернутой форме.
2) Считаем полученную сумму.
Примеры:
1012 = 1 * 22 + 0 * 21 + 1 * 20 = 510
0,2223 = 0 * 30 + 2 * 3-1 + 2 * 3-2 + 2 * 3-3 = 0,(962)10
347,48 = 3 * 82 + 4 * 81 + 7 * 80 + 4 * 8-1 = 231,510
3A,B716 = 3 * 161 +10 * 160 + 11 * 16-1 +7 * 16-2= 58, 7148437510
5. Перевод чисел из десятичной системы счисления в Р-ичную
5.1. Перевод целой части числа
Алгоритм перевода рассмотрим на примере перевода из десятичной системы счисления в двоичную. Пусть необходимо перевести число 2710 в двоичную систему счисления.
- Разделим 27 на 2. Получим 13 и остаток 1. Значит, последняя цифра в двоичной системе счисления будет 1.
- 13 /2 = 6 (остаток 1)
- 6 /2 = 3 (остаток 0)
- 3 / 2 = 1 (остаток 1)
Следовательно, 2710 = 110112
Проверка:
1101110 = 1 * 24 + 1 * 23 + 0 * 22 + 1 * 21 + 1 * 20 = 16 + 8 + 0 + 2 + 1 = 2710
Для других оснований аналогично. Переведем то же число в троичную систему счисления.
- 27 / 3 = 9 (остаток 0)
- 9 / 3 = 3 (остаток 0)
- 3 / 3 = 1 (остаток 0)
Следовательно, 2710 = 10003
Проверка:
10003 = 1 * 33 + 0 + 0 + 0 + 0 = 2710
Пусть теперь необходимо перевести число 2710 в восьмеричную систему счисления.
1)27 \8 = 3 (остаток 3)
2710 = 338
Проверка :
338 = 3 * 8 + 3 = 2710
Перевести 2710 в шестнадцатеричную систему счисления.
1) 27/16 = 1(остаток 11)
2710 = 1B16
Проверка :
1B16 = 1 * 16 + 11 = 2710
5.2. Перевод дробной части числа
Необходимо производить умножение на основание системы до тех пор, пока не останется дробной части или не будет достигнута необходимая степень точности.
Примеры:
- 0,2510
- 0,25 * 2 = 0,5 (целая часть 0)
- 0,5 * 2 = 1,0 (целая часть1)
- 0,25 = 0, 01
- 0,72510
- 0,725 * 2 = 1,45 (целая часть1)
- 0,45 * 2 = 0,9 (целая часть0)
- 0.9 * 2 = 1,8 (целая часть1)
- 0,8 * 2 = 1,6 (целая часть1)
- 0.6 * 2 = 1,2 (целая часть1)
- 0,2 * 2 = 0,4 (целая часть0)
- 0.4 * 2 =0,8 (целая часть0)
- 0,8 * 2 = 1,6 (целая часть1)
- 0,725 = 0.101(1100)
Упражнение: проделать самостоятельно для остальных систем счисления
6. Перевод из двоичной в родственные системы счисления и обратно
6.1. Перевод целой части числа
Для выполнения этой операции удобно воспользоваться таблицей соответствия чисел в двоичной системе счисления числам в другой.
Таблица 6. Перевод из двоичной системы счисления в восьмеричную.
основание 2 | основание 8 |
000 | 0 |
001 | 1 |
010 | 2 |
011 | 3 |
100 | 4 |
101 | 5 |
110 | 6 |
111 | 7 |
Таблица 7. Перевод из двоичной системы счисления в шестнадцатеричную.
основание 2 | основание 16 |
0000 | 0 |
0001 | 1 |
0010 | 2 |
0011 | 3 |
0100 | 4 |
0101 | 5 |
0110 | 6 |
0111 | 7 |
1000 | 8 |
1001 | 9 |
1010 | A |
1011 | B |
1100 | C |
1101 | D |
1110 | E |
1111 | F |
Рассмотрим пример перевода из двоичной системы счисления в восьмеричную числа 11101010000011011012. Первым делом разбиваем число на триады, начиная с правого конца 1 110 101 000 001 101 1012. Нам необходимо целое число триад, потому дописываем слева недостающие нули 001 110 101 000 001 101 1012. Далее смотрим по таблице перевода, какому числу соответствует очередная триада в восьмеричной системе счисления 001 110 101 000 001 101 1012 = 16501558.
Переведем то же самое число в шестнадцатеричную систему счисления. Записываем число, разбиваем его на группы по 4 с правого конца, если необходимо, дописываем слева недостающие нули. 0111 0101 0000 0110 11012. Далее действуем как и в случае с восьмеричной системой - ищем соответствующее число в таблице перевода.
0111 0101 0000 0110 11012 = 7506D16
6.2. Перевод из восьмеричной системы счисления в шестнадцатеричную и обратно
Для этого переведем число из восьмеричной системы счисления в двоичную, а уже из двоичной - в шестнадцатеричную. Обратно перевод производится аналогично.
Примеры.
462137328 = 100 110 010 001 011 111 011 0102 = 1001 1001 0001 0111 1101 10102 = 9917DA16
Перевод дробной части:
0,2510 = 0,01002 = 0,28 = 0,416
Совет: для выполнения арифметических операций в двоичной системе счисления, бывает удобнее перевести число в шестнадцатеричную, выполнить соответствующие действия в ней, а результат перевести обратно в двоичную. Заметим, что ЭВМ используют этот же принцип, только все арифметические операции выполняются в двоичной системе счисления, а уже результат переводится в десятичную.
7. Смешанные системы счисления
В отличие от P-ичных систем счисления, в смешанных системах счисления количество символов алфавита может меняться в зависимости от разряда числа. Классическим примером смешанных систем счисления является система измерения времени, где мы используем часы, минуты, секунды.
Существует также факториальная
АQ=k=1ndkk!, 0≤dk≤k
и фиббоначиева
AQ=k=0nfkFk,
системы счисления. При записи числа в фиббоначиевой системе счисления Fk – числа Фиббоначи, коэффициенты fk принимают значения 0 или 1, и в последовательности коэффициентов fnfn-1…f0 нет двух подряд идущих единиц.
8. Литература
- С. Б. Гашков. Системы счисления и их применение. М.: МЦНМО, 2004. — 52 с.: ил.
- Игорь Н. Бекман. Компьютеры в информатике. Лекция 4: Кодирование в информатике. [http://profbeckman.narod.ru/Komp.files/Lec4.pdf]
- В. М. Казиев. Введение в информатику. [http://www.intuit.ru/department/informatics/intinfo/4/1.html]
Е. А. Роганов. Практическая информатика. [http://www.intuit.ru/department/se/pinform/1/4.html