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

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

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

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

Способ представления числа определяется системой счисления.

Система счисления – это правило записи чисел с помощью заданного набора специальных знаков – цифр.

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

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

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

• если цифра меньшего значения стоит справа от большей цифры, то их зна­чения суммируются; если слева — то меньшее значение вычитается из большего;

• цифры I, X, С и М могут следовать подряд не более трех раз каждая;

• цифры V, L и D могут использоваться в записи числа не более одного раза.

Например, запись XIX соответствует числу 19, МDХLIХ — числу 1549. Запись чисел в такой системе громоздка и неудобна, но еще более неудобным оказывается выполнение в ней даже самых простых арифметических операций. Отсутствие нуля и знаков для чисел больше М не позволяют римскими цифрами записать любое число (хотя бы натуральное). По указанным причинам теперь римская система используется лишь для нумерации.

В настоящее время для представления чисел применяют, в основном, позиционные системы счисления.

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

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

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

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

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

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

(1)

Из коэффициентов при степенях основания строится сокращенная запись числа:

Индекс р числа Z указывает, что оно записано в системе счисления с основанием р, общее число цифр числа равно k. Все коэффициенты — целые числа, удовлетворяющие условию: .

Уместно задаться вопросом: каково минимальное значение р? Очевидно, невозможно, поскольку тогда все и форма (1) теряет смысл. Первое допустимое значение — оно и является минимальным для позиционных систем.

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

Наряду с двоичной в компьютерах используются восьмеричная и шестнадцатеричная системы счисления.

Представление чисел в различных системах счисления

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

Например: |||||₁= 5₁₀ = 101₂ = 5₁₆.

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

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

Обозначим преобразование числа Z, представленного в p-ричной системе счисления в представление в q-ричной системе как . Теоретически возможно произвести его при любых q и р. Однако подобный прямой перевод будет затруднен тем, что придется выполнять операции по правилам арифметики недесятичных систем счисления (полагая в общем случае, что ).

По этой причине более удобными с практической точки зрения оказываются варианты преобразования с промежуточным переводом с основанием r, для которого арифметические операции выполнить легко. Таким удобным основанием является r = 10, т.е. перевод осуществляется через десятичную систему счисления.

Преобразование

Идея алгоритма перевода предельно проста: положим начальное значение ; из числа вычтем 1 по правилам вычитания системы р, т.e. , и добавим ее к по правилам сложения системы q, т.е. . Будем повторять эту последовательность действий, пока не достигнем .

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

Преобразование

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

(2)

где т — число разрядов в записи, а — цифры числа .

Разделим число на две части по разряду номер i. Число, включающее разрядов с -го по i-й, обозначим , а число с i разрядами с -го по 0-й — . Очевидно, .

.

Позаимствуем из языка VBA обозначение двух операций: \ — результат целочисленного деления двух целых чисел и mod— остаток от целочисленного деления 13 \ 4 = 3; 13 mod 4 = 1.

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

; . (3)

Аналогично, если принять , то для правой части числа будет справедливо другое рекуррентное соотношение: , из которого следуют:

; . (4)

Из соотношений (3) и (4) непосредственно вытекают два способа перевода целых чисел из десятичной системы счисления в систему с произвольным основанием q.

Способ 1 является следствием соотношений (3), предполагающий следующий алгоритм перевода:

1. Целочисленно разделить исходное число (Z₁₀) на основании новой системы счисления (q) и найти остаток от деления — это будет цифра 0-го разряда числа Z_q.

2. Частное от деления снова целочисленно разделить на q с выделением остатка; процедуру продолжать до тех пор, пока частное от деления не окажется меньше q.

3. Образовавшиеся остатки от деления, поставленные в порядке, обратном порядку их получения, и представляют Z_q.

Пример. Выполнить преобразование

Остатки от деления (3, 4) и результат последнего целочисленного деления (4) образуют обратный порядок цифр нового числа. Следовательно, .

Способ 2 вытекает из соотношения (4), действия производятся в соответствии со следующим алгоритмом:

1. Определить — максимальный показатель степени в представлении числа по форме (2) для основания q.

2. Целочисленно разделить исходное число (Z₁₀) на основание новой системы счисления в степени (т.е. q^m-1) и найти остаток от деления; результат деления определит первую цифру числа Z_q.

3. Остаток от деления целочисленно разделить на g^m-2, результат деления принять за вторую цифру нового числа; найти остаток; продолжать эту последовательность действий, пока показатель степени q не дос­тигнет значения 0.

Продемонстрируем действие алгоритма на той же задаче, что была рассмотрена выше.

Определить можно либо путем подбора (5⁰ = 1 < 123; 5¹ = 5 < 123; 5² = 25 < 123; 5³ = 125 > 123, следовательно, ), либо логарифмированием с оставлением целой части логарифма (1оg₅123 = 2,99, т.е. ). Далее:

Алгоритмы перевода явно вытекают из представлений (1) или (2): необходимо Z_p представить в форме многочлена и выполнить все операции по правилам десятичной арифметики.

Пример. Выполнить преобразование .

Решение: .

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

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

Контрольный тест №2:

1. Результат вычисления выражения имеет в двоичной системе счисления вид …

   1. 10010100

   2. 70040001

   3. 20020001

   4. 10010001

2. Результат вычисления выражения имеет в двоичной системе счисления вид …

   1. 112001

   2. 122001

   3. 10010001

   4. 10011001

3. Если числа в двоичной системе счисления имеют вид 1001₂ и 101₂, то их разность в десятичной системе счисления равна …

   1. 8

   2. 2

   3. 4

   4. 900

4. Последняя цифра суммы чисел 57₈ и 56₈ в восьмеричной системе счисления равна

   1. 6

   2. 3

   3. 5

   4. С

5. Последняя цифра суммы чисел 55₁₆ и 56₁₆ в шестнадцатеричной системе счисления равна

   1. 1

   2. 6

   3. 3

   4. В

6. Укажите упорядоченную по возрастанию последовательность значений

   1. 55₁₆ 55₈ 55₇

   2. 55₈ 55₇ 55₁₆

   3. 55₇ 55₈ 55₁₆

   4. 55₈ 55₁₆ 55₇

7. В записи числа в двоичной системе счисления могут присутствовать

   1. цифры от 1 до 5

   2. шесть нечетных цифр

   3. цифры 0 и 1

   4. буквы от А до Е