Жмакин А.П. Архитектура ЭВМ (2006), страница 6

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

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

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

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

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

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

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

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

Определение

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

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

575,15 = 5 • 10² + 7 ∙ 10¹ + 5 ∙ 10° +1 • 10^-1 -I- 5 • 10^-2.

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

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

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

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

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

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

Уместно задаться вопросом: каково минимальное значение рЧ Очевидно,

р = \ невозможно, поскольку тогда все о, =0 и форма (3.1) теряет смысл.

Первое допустимое значение р = 2 — оно и является минимальным для по­зиционных систем.

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

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

3.2. Представление чисел

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

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

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

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

3.2.1. Перевод целых чисел

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

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

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

Преобразование Z_p ->Zj -> Z_q

Идея алгоритма перевода предельно проста: положим начальное значение Z_q:=0; из числа Z_p вычтем 1 по правилам вычитания системы р, т.е. Z_p:=Z_p-\, и добавим ее к Z_q по правилам сложения системы q, т.е. Z_q := Z_q +1 . Будем повторять эту последовательность действий, пока не достигнем Z_p=0. Правила сложения с 1 (инкремента) и вычитания 1 (дек­ремента) могут быть записаны так, как представлено в табл. 3.1.

Примечание: П— перенос в случае инкремента или заем в случае декремента.

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

Преобразование Z_p -> Z_w Z_q

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

где m — число разрядов в записи Z_p, a bj(j = 0,/и-1)— цифры чис­ла Z_q.

Позаимствуем из языка PASCAL обозначение двух операций: div— ре­зультат целочисленного деления двух целых чисел и mod— остаток от це­лочисленного деления (13 div 4 = з; 13 mod 4 = i).

Теперь если принять y_m_, =b_m__], то в (3.2) усматривается следующее ре­куррентное соотношение:

у, =у,₊₁ +*,, из которого, в свою очередь, по­лучаются выражения:

Аналогично, если принять 8₀ = b₀, то для правой части числа будет спра­ведливо другое рекуррентное соотношение: 8,=8_м+£,9 , из которого следуют:

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

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

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

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

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

\ Пример 3.1

Выполнить преобразование 123₁₀ -> Z₅. Результат — на рис. 3.1.

Рис. 3.1. Результат выполнения примера 3.1

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

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

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

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

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

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

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

Определить ли — 1 можно либо путем подбора (5°=1<123; 5¹ = 5 < 123;

2 3

5 = 25< 123; 5 = 125> 123, следовательно, m-1 = 2), либо логарифми­рованием с оставлением целой части логарифма (log₅ 123 = 2,99, т.е. wj — 1 = 2 ).

Далее:

b = 123 div 5² =4 8, =23mod 5² =23 / = 2-1 =1

6, = 23 div 5¹ = 4 8₀ =23 mod5¹=3 / = 0

Алгоритмы перевода Z_g—>Z_W явно вытекают из представлений (3.1) или (3.2): необходимо Z_p представить в форме многочлена и выполнить все опе­рации по правилам десятичной арифметики.

Выполнить преобразование 443₅ -> Z\₀.

Решение:

443₅ =4∙5² +4∙5¹ +3∙5° =4∙25+ 4∙5+ 3∙1 = 12310

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