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

Системы счисления – одна из самых базовых тем в информатике, поэтому разберемся в этой теме по порядку.

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

Существует два типа систем счисления:

Непозиционная

Позиционная

В непозиционной системе счисления величина, которая обозначает цифру, не зависит от положения в числе.

К таким системам счисления можно отнести египетскую и римскую системы счисления.

Пример. Число в римской системе счисления – это набор стоящих подряд заглавных латинских букв, таких как I, V, X, L, C, В и M, которые обозначают числа 1, 5, 10, 50, 100, 500 и 1000 соответственно.

Тогда число 67 в римской системе счисления можно записать, как LXVII.

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

Позиционные системы счисления основаны на том, что «вес» цифры зависит от её положения – или позиции – в числе, отсюда и такое название.

Самые популярные в информатике позиционные системы счисления: двоичная, восьмеричная, десятичная, шестнадцатеричная.

Десятичная система счисления

Исторически сложилось, что это самая распространенная система счисления. Именно её мы используем, когда мы делаем покупки в магазине, набираем номер телефона или открываем страницу в книге. На каждой позиции может стоять только одна цифра из диапазона от 0 до 9.

Основанием (то есть, количество цифр) является число 10. Это значит, что «вес» любой цифры в числе будет кратен 10 в степени, равной позиции этой цифры. При этом позиции (их называют разрядами) отсчитываются с правого конца числа, начиная с нуля.

Пример. Чтобы разобраться подробнее, возьмем число 123. Давайте «разложим» это число по разрядам. Для этого каждую цифру числа умножим на основание системы, в данном случае число 10, возведенное в степень, равную номеру разряда. Цифра 3 стоит в нулевом разряде, цифра 2 – в первом, а цифра 1 – во втором. Получается, значение равно:

1∙10² + 2∙10¹ + 3∙10⁰ = 100 + 20 + 3 = 123.

При работе с разными системами счисления, чтобы избежать путаницы, справа от числа приписывают нижний индекс с основанием: 123₁₀.

Двоичная система счисления

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

Пример. Возьмем число 1001 – это число 9 в десятичной системе счисления. Для того, чтобы перевести число из двоичной в десятичную систему счисления, необходимо точно так же «разложить» число на разряды, т.е. каждую цифру двоичного числа умножить на основание 2, возведенное в степень, равную разряду:

1001₂ = 1∙2³ + 0∙2² + 0∙2¹ + 1∙2⁰ = 8 + 0 + 0 + 1 = 9.

Точно так же выполняется перевод из любой n-ричной системы счисления в десятичную. Для этого надо:

Определить количество разрядов;

Умножить каждую цифру n-ричной системы счисления на основание «n», возведенное в степень, равную разряду.

Пример. Посмотрим, как переводить число из десятичной системы счисления в двоичную. Пусть нужно перевести число 240₁₀ в двоичную систему счисления. Для этого надо последовательно делить число 240 на 2, фиксируя получающиеся остатки (удобнее всего делать это «лесенкой»), пока не дойдем до последнего частного, которое на 2 уже не делится. Это будет первая цифра числа в двоичной системе. А остальные цифры – это получившиеся остатки, записанные в обратном порядке:

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

240₁₀ = 11110000_2.

Точно так же выполняется перевод из десятичной системы счисления в любую n-ричную. Для этого надо:

Целую часть числа последовательно делить на основание новой системы счисления, пока не останется число или цифра, которая уже делиться не будет;

Эта оставшаяся цифра (частное) будет первой цифрой нового числа. Остальные цифры – это остатки от всех делений, записанные в обратном порядке.

Восьмеричная система счисления

Имеет основание 8, использует цифры от 0 до 7.

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

Пример.

671₈ = 6∙8² + 7∙8¹ + 1∙8⁰ = 384 + 56 + 1 = 441_10.

Перевод из десятичной системы счисления в восьмеричную осуществляется аналогично

переводу в двоичную, только делителем в данном случае является 8.

Пример. Пусть надо перевести число 163₁₀ в восьмеричную систему:

Получаем, что:

163₁₀ = 243_8.

Шестнадцатеричная система счисления

Имеет основание 16, использует цифры от 0 до 9 и буква A, B, C, D, E, F, где буква А = 10, В = 11, С = 12, D = 13, Е = 14, F = 15.

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

Пример.

127₁₆ = 1∙16² + 2∙16¹ + 7∙16⁰ = 256 + 32 + 7 = 295_10.

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

Пример. 191₁₀ переведем в шестнадцатеричную систему:

При этом 11 = B, 15 = F. Получаем, что:

191₁₀ = BF_16.

Метод триад и тетрад

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

Триады – числа, состоящие из трех цифр, вообще говоря, это перевод восьмеричных чисел от 0 до 7 в двоичную систему счисления. Тетрады состоят из четырех, и являются переводом шестнадцатеричных чисел от 0 до F в двоичную систему счисления.

Триады и тетрады переводятся, начиная с конца числа (т.е. с младших разрядов). Если крайние триады (тетрады) оказались неполными, они дополняются нулями. Если при переводе в двоичную систему в начале числа (слева) возникают нули, их следует отбросить (они незначащие).

Пример.

12345667₈ = 001 010 011 100 101 110 110 111₂ = 1 010 011 100 101 110 110 111₂.

Таблица с триадами и тетрадами, которую надо знать наизусть.

Число	Триада	Тетрада
0	000	0000
1	001	0001
2	010	0010
3	011	0011
4	100	0100
5	101	0101
6	110	0110
7	111	0111
8		1000
9		1001
A (10)		1010
B (11)		1011
С (12)		1100
D (13)		1101
E (14)		1110
F (15)		1111

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

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

Записываем таблицу степеней двойки в обратном порядке.

Выбираем самое большое значение степени, помещающееся в число, которое переводим в двоичную систему. Эту степень обводим.

Переходим к следующей степени двойки.

Вычитаем каждое следующее помещающееся число. Вмещающиеся степени обводим.

Продолжаем вычитать, пока не дойдем до конца таблицы.

Под обведенными степенями пишем «1», под не обведенными «0».

Записываем получившееся число.

Пример. С помощью этого метода переведем число 79₁₀ из десятичной системы счисления в двоичную.

79 = 64 + 8 + 4 + 2 + 1

Получаем:

79₁₀ = 1001111_{2 .}

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

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

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

Сложение в позиционных системах счисления

Сложение многозначных чисел в n-ричной системе счисления производится поразрядно, начиная с младшего разряда. Если при суммировании цифр одного разряда сумма оказывается больше n – 1, то в данном разряде записывается младшая цифра суммы, а старшая цифра прибавляется к ближайшему слева разряду. При этом таблица сложения в двоичной системе счисления выглядит следующим образом:

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

Вычитание в позиционных системах счисления

Вычитание многозначных чисел в n-ричной системе производится также столбиком. Если в очередном разряде уменьшаемого стоит цифра, меньшая чем у вычитаемого, то занимается единица у ближайшего слева ненулевого разряда. В результате к вычисляемому разряду уменьшаемого добавляется n. Если единица занималась не у соседнего слева разряда, то к промежуточным разрядам добавляется n – 1.

Пример. Рассмотрим вычитание чисел в восьмеричной системе счисления.

Умножение и деление в позиционных системах счисления

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

Пример. Рассмотрим, как умножать и делить числа в двоичной системе счисления.

Пример. Закрепим операции умножения и деления чисел в пятеричной системе счисления.

Числа Фибонначи и Фибоначчиевая система счисления

Итальянский математик Леонардо Пизанский, более известный под именем Фибоначчи, открыл удивительную последовательность чисел:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …

Именно такие числа называются «числами Фибоначчи», а сама последовательность – последовательностью Фибоначчи.

В этой последовательности первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число получается из суммы двух предыдущих чисел:

1 = 0 +1, 2 = 1 + 1, 3 = 1 +2, 5 = 2 + 3, 8 = 3 +5, и т. д.

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

Решая эту задачу, получаем таблицу с данными, которые являются членами последовательности Фибоначчи:

Числа Фибоначчи используются в так называемой Фибоначчиевой системе счисления.

Принцип разложения любого числа в Фибоначчиевой системе счисления основывается на вышеупомянутым переводе десятичного числа в двоичное с помощью степенной таблицы, но данном случае верхнюю строку таблицы заполняем числами Фибоначи в порядке убывания вместо степеней двоек. При этом нижний индекс для обозначения системы счисления выглядит следующим образом: _Fib.

Пример. Рассмотрим прямое и обратное разложение числа в Фибоначчиевой системе счисления.

25₁₀ = X_Fib

25 = 21 + 3 + 1