Теоретический материал

Системы счисления

(5 уроков)

Урок 1.

Системы счисления. Классификация систем счисления.

Система счисления — это правила записи чисел с помощью специальных знаков некоторого алфавита (обычно цифр), а также соответствующие правила выполнения операций с этими числами.

Первоначально люди считали на пальцах — это самый простой способ, который используется и сейчас. Один загнутый (или отогнутый) палец обозначал единицу (один день, одного человека, одного барана и т.п.). Такая система счисления называется унарной (от лат. unus — один) (единичной). В качестве цифр унарной системы можно использовать камешки, узелки, счётные палочки (как в начальной школе), зарубки на дереве (как делал Робинзон Крузо) или на кости, чёрточки на бумаге, точки и другие одинаковые знаки или предметы.

С помощью унарной системы можно записывать только натуральные числа, причём запись больших чисел получается очень длинной (представьте себе, как записать миллион). Цифра любой позиции числа, записанного в унарной системе, всегда обозначает единицу, поэтому это одна из непозиционных систем счисления.

Непозиционная система счисления — это такая система счисления, в которой значение цифры не зависит от её места в записи числа.

К непозиционным относится и десятичная египетская система счисления. Египтяне ввели 7 знаков-иероглифов, которые обозначали степени числа 10 (чёрточка, хомут, верёвка, лотос, палец, лягушка, человек) — рис. 1.

рис. 1.

В этой системе, например, число 235 записывалось как

В римской системе счисления (она также считается непозици­онной) в качестве цифр используются латинские буквы: I обозначает 1, V — 5, X — 10, L — 50, С — 100, D — 500, М — 1000. Единицы, десятки, сотни и тысячи кодировались отдельными группами, например:

2368 = 2000 + 300 + 60 + 8 = (1000 + 1000) + (100 + 100 + 100) + (50 + 10) + (5 + 1 + 1 + +1) = MMCCCLXVIII.

Больше трёх одинаковых цифр подряд не ставили, поэтому число 4 записывали как IV. В такой записи меньшая цифра (I) стоит перед большей (V), поэтому она вычитается из неё. То есть:

IV = 5 - 1 = 4.

Аналогично записывались числа 9, 40, 90, 400 и 900:

IX = 10 - 1 = 9, XL = 50 - 10 = 40, ХС = 100 - 10 = 90,

CD = 500 - 100 = 400, МС = 1000 - 100 = 900.

Из-за этой особенности римскую систему нельзя считать полностью непозиционной, потому что значение меньшей цифры, стоящей слева от большей, меняется на отрицательное.

У римской системы есть несколько серьёзных недостатков:

•   можно записывать только натуральные числа (что делать с дробными и отрицательными?);

•   чтобы записывать большие числа, необходимо вводить всё новые и новые цифры (иногда использовались цифры с подчёркиванием или чертой сверху, что обозначало увеличение в 1000 раз: V — 5000, X — 10 000 и т. д.);

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

Сейчас римская система применяется для нумерации веков (XXI век), месяцев, глав в книгах, на циферблатах часов (например, на Спасской башне Московского Кремля).

В славянской системе счисления в качестве цифр использовались буквы алфавита, над которыми ставился знак isj («титло») (рис. 2).

рис. 2

Если в ряду стояло несколько цифр, знак «титло» ставился только у первой. Старшие цифры записывались справа от младших, например, число 11 записывалось как

     Славянская система счисления используется на циферблате часов Суздальского Кремля.

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

Позиционная система счисления — это такая система счисления, в которой значение цифры («вес») полностью определяется её местом (позицией) в записи числа.
Пример позиционной системы счисления - привычная нам десятичная система. В числе 6375 цифра 6 обозначает тысячи (т.е. 6000), цифра 3 - сотни (300), цифра 7 - десятки (70), а цифра 5 -  единицы:

6375 = 6•1000 + 3•100 + 7•10 + 5•1.

Алфавит системы счисления - это используемый в ней набор символов.

Основание системы счисления - это количество символов в алфавите (мощность алфавита).

В десятичной системе счисления основание - 10, алфавит состоит из 10 цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Число 10, вероятно, было выбрано потому, что люди сначала использовали для счета свои 10 пальцев на руках.

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

Например: Базисы некоторых позиционных систем счисления:

Десятичная система: 10⁰, 10¹, 10², 10³, 10⁴, ..., 10ⁿ, ...

Двоичная система: 2⁰, 2¹, 2², 2³, 2⁴, ..., 2ⁿ, ...

Восьмеричная система: 8⁰, 8¹, 8², 8³, 8⁴, ..., 8ⁿ, ...

Разряд - это позиция цифры в записи числа. Разряды в записи целых чисел нумеруются с нуля справа налево.

В числе 6375 цифра 6 стоит в третьем разряде (тысячи, 10³), 3 - во втором разряде (сотни, 10²), 7 - в первом (десятки, 10¹), а 5 - в нулевом (единицы, 10⁰). Не забывайте, что любое число (кроме нуля!) в нулевой степени равно 1. Поэтому

           разряды -  3210

                                      6375 = 6 • 10³ + 3 • 10² + 7 • 10¹ + 5 • 10°.

Это так называемая развёрнутая форма записи числа. Из этой записи видно, что последняя цифра 5 - это остаток от деления числа на 10 (все остальные слагаемые делятся на 10); число, составленное из двух последних цифр (75) - это остаток от деления исходного числа на 100 = 10² и т. д. Поэтому все числа, делящиеся на 100 без остатка, оканчиваются на два нуля.

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

Число 6375 можно представить в другой форме — по схеме Горнера:

6375 = ((6 • 10 + 3) • 10 + 7) • 10 + 5.

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

Кроме десятичной системы, на практике используются ещё несколько позиционных систем:

•     двоичная, восьмеричная и шестнадцатеричная в компьютерной технике;

•    двенадцатеричная английская система мер (1 фут = 12 дюймов, 1 шиллинг = 12 пенсов);

•  шестидесятеричная система измерения времени (1 час = = 60 минут, 1 минута = 60 секунд).

ГРУППЫ СИСТЕМ СЧИСЛЕНИЯ

 Анатомического         - десятичная

 происхождения          - пятиричная

                                      - двенадцатиричная

                                      - двадцатиричная

 Алфавитные             - славянская

                                   - древнеармянская

                                   - древнегрузинская

                                   - древнегреческая

                                   - (ионическая)

 Машинные               - двоичная

                                   - восьмеричная

                                   - шестнадцатеричная

 Прочие                     - римская

                                   - вавилонская

Урок 2.

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

В двоичной системе счисления, т. е. в системе с основанием 2, алфавит состоит из двух цифр: 0 и 1. Все данные в компьютерных устройствах хранятся и обрабатываются как числа, представлен­ные в двоичной системе счисления.

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

Кроме того, можно использовать метод подбора, или табличный метод (разложение числа на сумму степеней двойки). Так, в числе 77 старшая степень двойки — это 64 = 2⁶ (следующая степень, 128 = 2⁷, уже больше, чем 77), поэтому

77 = 2⁶ + 13.

Теперь выделяем старшую степень двойки в числе 13: это

8  = 2³, так что

77 = 2⁶ + 2³ + 5.

Выделяем старшую степень двойки в числе 5: это 4 = 2², получаем:

77 = 2⁶ + 2³ + 2² + 1 = 2⁶ + 2³ + 2² + 2°.

Мы разложили число на сумму степеней двойки. Для «полного комплекта» здесь не хватает 2⁵, 2⁴ и 2¹, но можно считать, что эти степени умножаются на нули:

77 = (1)*2⁶+(0)*2⁵+(0)*2⁴+(1)-2³+(1)*2²+(0)*2¹+(1)*2°

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

Арифметические операции в двоичной системе счисления

Дробные числа

Выводы:

Двоичная система счисления служит основой всех расчётов в современных компьютерах. Она обладает следующими преимуществами:

•    для того, чтобы построить компьютер, работающий с двоичными данными, достаточно иметь устройства с двумя состояниями (включено/выключено); первыми такими устройствами были электромагнитные реле, сейчас применяются микроэлектронные элементы;

•    надёжность и защита от помех при передаче информации (для приёма двоичного кода не нужно точно измерять сигнал, достаточно знать, какое из двух значений он принимает в каждый заданный момент времени);

•    компьютеру проще выполнять вычисления с двоичными числами, нежели с десятичными; например, умножение фактически сводится к многократному сложению, а деление - к вычитанию.

Тем не менее, с точки зрения человека у двоичной системы есть недостатки:

• двоичная запись чисел получается длинная: например, число 1024 записывается в виде 10000000000₂ – здесь легко перепутать количество идущих подряд нулей;
• запись однородна, т. е. содержит только нули и единицы; поэтому при работе с двоичными числами легко ошибиться или запутаться.

Урок 3.

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

Восьмеричная система счисления (позиционная система с основанием 8) использовалась для кодирования команд во многих компьютерах 1950-1980-х гг. (например, в американской серии PDP-11, советских компьютерах серий ДВК, СМ ЭВМ, БЭСМ). В ней используются цифры от 0 до 7.
Для перевода десятичного числа в восьмеричную систему проще всего использовать стандартный алгоритм для позиционных систем (деление на 8, выписывание остатков в обратном порядке). Например:

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

                            разряды 210

    144₈ - 1 • 8² + 4• 8¹ + 4• 8° = 64 + 4• 8 + 4 = 100.

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

Связь с двоичной системой

Оказывается, можно сделать перевод из восьмеричной системы в двоичную напрямую, используя тесную связь между этими системами: их основания связаны равенством 2³ = 8. Покажем это на примере восьмеричного числа 753₈. Запишем его в развёрнутой форме:

753₈ = 7 • 8² + 5 • 8¹ + 3 • 8° = 7 • 2⁶ + 5 • 2³ + 3 • 2°.

Теперь переведём отдельно каждую цифру в двоичную систему:

7 = 111₂ = 1 • 2² + 1 • 2¹ + 1 • 2°,       5 = 101₂ = 1 • 2² + 1 • 2°,

3 = 11₂ = 1 • 2¹ + 1 • 2°.

Подставим эти выражения в предыдущее равенство:

753₈ = (1 • 2² + 1 • 2¹ + 1 • 2°) • 2⁶ + (1 • 2² + 1 • 2°) • 2³ + (1 • 2¹ + 1 • 2°) • 2°.

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

753₈=1*2⁸+1*2⁷+1*2⁶+1*2⁵+0*2⁴+1*2³+0*2²+1*2¹+2⁰

Таким образом, 753₈ = 111 101 011₂. Двоичная запись разбита на триады (группы из трёх цифр), каждая триада - это двоичная запись одной цифры исходного восьмеричного числа.

Алгоритм перевода восьмеричного числа в двоичную систему счисления:

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

2.  Соединить триады в одно «длинное» двоичное число.

Например: 35721₈ = 11 101 111 010 001₂. В этой записи триады специально отделены друг от друга пробелами. Обратите внимание, что для всех чисел, меньших четырёх, результат перевода в двоичную систему дополняется слева нулями до трёх цифр:

2 = 10₂ = 010₂, 1 = 1₂ = 001₂.

Для самой первой триады это делать необязательно, потому что лидирующие нули в записи числа никак его не меняют. Напротив, если «потерять» нули в середине числа, получится неверный результат.

Очень важно помнить, что значение цифры в восьмеричной системе счисления совпадает со значением этой же цифры в десятичной системе.

табл. 1

Алгоритм перевода двоичного числа в восьмеричную систему счисления:

1. Разбить двоичное число на триады, начиная справа. В начало самой первой триады добавить слева нули, если это необходимо.

2.  Перевести каждую триаду (отдельно) в восьмеричную систему счисления.

3.  Соединить полученные цифры в одно «длинное» число.

Например, переведём в восьмеричную систему число 1010011100101110111₂. Разобьём его на триады (начиная справа), в начало числа нужно добавить два нуля (они подчёркнуты):

1010011100101110111₂= 001 010 011100 101110 111₂.

Далее по табл. 1 переводим каждую триаду в восьмеричную систему:

1010011100101110111₂ = 1234567₈.

Арифметические операции в восьмеричной системе счисления.

При вычислениях в восьмеричной системе нужно помнить, что максимальная цифра — это 7. Перенос при сложении возникает тогда, когда сумма в очередном разряде получается больше 7. Заём из старшего разряда равен 108 = 8, а все «промежуточ­ные» разряды заполняются цифрой 7 - старшей цифрой системы счисления. Приведём примеры сложения и вычитания:

В примере на сложение запись 1*8 + 2 означает, что получилась сумма, большая 7, которая не помещается в один разряд. Единица идёт в перенос, а двойка остаётся в этом разряде. В записи операций при выполнении вычитания запись «-1» означает, что из этого разряда раньше был заём (его значение уменьшилось на 1), а запись «+8» означает заём из старшего разряда.

Применение восьмеричной системы

Восьмеричная система счисления использовалась для кодирования команд во многих компьютерах 1950-1980-х гг. (например, в американской серии  PDP-11, советских компьютерах серий ДВК, СМ ЭВМ, БЭСМ), но позднее была почти вытеснена шестнадцатеричной системой.

С помощью восьмеричной системы удобно кратко записывать содержимое областей памяти, содержащих количество битов, кратное трём. Например, 6-битные данные «упаковываются» в две восьмеричные цифры. Некоторые компьютеры 1960-х годов использовали 24-битные и 36-битные данные, они записывались соответственно с помощью 8 и 12 восьмеричных цифр. 

Сейчас восьмеричная система применяется, например, для установки прав на доступ к файлу в операционной системе Linux (и других Unix-системах) с помощью команды chmod.

Режим доступа кодируется тремя битами, которые разрешают чтение (г, read, старший бит), запись (w, write) и выполнение файла (х, execute, младший бит). Код 7 = 111₂ (rwx) означает, что все биты установлены (полный доступ), а код 5 = 101₂ (r-х) разрешает чтение и выполнение файла, но запрещает его изменение.

Урок 4.

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

Урок 5.

Другие системы счисления.