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

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

Замечание: Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера — поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, [math]\dfrac<1><3>[/math] ), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число. В такой реализации вероятность встречи символа представляется в виде рационального числа. Поскольку в каждой итерации будет переход из текущего отрезка в один из его [math]m[/math] подотрезков, кратных по длине [math]n[/math] , а всего итераций [math]n[/math] , в конечном результате знаменатель дроби не превысит [math]n^[/math] , а поскольку сумма всех вероятностей встречи символов равна [math]1[/math] , полученная дробь будет находиться в промежутке [math][0; 1)[/math] .

Пример работы [ править ]

Рассмотрим в качестве примера строку [math]abacaba[/math] :

Источник

ГЛАВА 2. ПРЕДСТАВЛЕНИЕ ЧИСЕЛ, АРИФМЕТИЧЕСКИЕ И ЛОГИЧЕСКИЕ
ОПЕРАЦИИ В ВЫЧИСЛИТЕЛЬНЫХ МАШИНАХ

2.1. ВВЕДЕНИЕ

Вычислительные машины выполняют обработку информации под управлением программы. Существенным является способ представления информации в ЭВМ. В данной главе будет рассмотрено двоичное представление целых чисел и логических значений в памяти ЭВМ VAX. В последующих главах будет показано, как представляются символьная информация, числа с плавающей точкой и простые структуры данных, такие как массивы.

2.2. СИСТЕМЫ СЧИСЛЕНИЯ

ИСТОРИЧЕСКИЕ СВЕДЕНИЯ

На протяжении всей истории человечества было изобретено много различных способов счисления или счёта. И сегодня ещё можно встретить людей, которые используют примитивные способы счёта, например складывают камешки в мешок или делают зарубки на палочке. До сих пор существует и более сложная римская система счисления, римские цифры сейчас используются главным образом в демонстрационных целях [1] . Однако наиболее привычной для всех нас системой счисления является десятичная или арабская [2] . На рис. 2.1 показаны примеры представления чисел в различных системах.

Счёт по зарубкам на палочке

Рис. 2.1. Некоторые системы представления чисел

ДЕСЯТИЧНАЯ СИСТЕМА СЧИСЛЕНИЯ

Одним из свойств традиционных систем представления чисел является стремление сгруппировать числа по "пятёркам" и "десяткам". Это заставляет считать числа 5, 10 и кратные им, а также степени этих чисел крайне важными, обладающими чуть ли не магическими свойствами. Действительно, очень легко умножить или разделить число на 10. Выполнить ту же операцию с числами 8, 9, 11 или 12 гораздо сложнее.

На самом деле единственной причиной наличия у чисел 5 и 10 каких-либо особенных свойств является то, что основание системы счисления равно 10. Системы счисления могут иметь и другие основания. Например, в Вавилоне более 4000 лет назад использовалась система счисления с основанием 60, называемая шестидесятеричной. В какой-то степени она сохранилась и до наших дней, например: в 1 ч - 60 мин, а в 1 мин - 60 с. Употребление слов "дюжина" для обозначения числа 12 и " гросс" [3] для числа 144 является примером использования системы счисления с основанием 12. В действительности особых преимуществ в десятичной системе счисления нет. Наиболее вероятно, что начало развитию десятичной системы положил счёт на пальцах рук. Поскольку вычислительные машины не имеют рук с пятью пальцами, использование для них десятичной системы не даёт заметного преимущества. Более того, вычислительные машины работают более эффективно при применении систем счисления, отличных от десятичной.

СЧЁТ В СИСТЕМАХ СЧИСЛЕНИЯ, ОТЛИЧНЫХ ОТ ДЕСЯТИЧНОЙ

По мере рассмотрения различных систем счисления будут излагаться основы десятичной системы, т.е. как в ней осуществляются счёт, сложение, вычитание, а также как интерпретируется представление чисел. В десятичной системе числа представляются в виде строки символов, выбранных из набора, состоящего из десяти цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Счёт ведётся начиная с 0 при последовательной записи цифр от 0 до 9. Когда будет достигнуто число 9, все цифры набора окажутся использованными. Затем слева добавляется ещё одна позиция, куда помещается цифра 1, а в начальной правой позиции повторяется последовательная запись цифр начиная с 0, что позволяет получать числа 10, 11, 12 и т.д. Когда получено число 19, при продолжении счёта цифра 9 заменяется на 0, а в соседней левой позиции прибавляется 1, в результате получается число 20. Следовательно, когда справа образуется последовательность девяток, то при увеличении счёта на 1 все они заменяются на 0, при этом перенос распространяется справа налево. Таким образом, после 3999 следует 4000.

Как было отмечено в предыдущем подразделе, нет ничего сверхъестественного ни в числе 10, ни в использовании для счёта набора из десяти цифр. Предположим, что имелось бы всего шесть цифр. Такой могла бы быть сегодняшняя традиционная система счисления, будь у людей по три пальца на руке вместо пяти. Эта система называлась бы системой счисления с основанием 6.

В системе счисления с основанием 6 имеется шесть цифр: 0, 1, 2, 3, 4, 5. Счёт в этой системе ведётся фактически так же, как и в десятичной, за исключением того, что отсутствуют цифры 6, 7, 8 и 9, а возврат к 0 и перенос осуществляются по достижении цифры 5. Так, за числом 5 следует число 10, за 15 - 20, за 255 - 300. В табл. 2.1 показано, как осуществляется счёт от 0 до 36 в системе счисления с основанием 6.

2.3. ДВОИЧНЫЕ ЧИСЛА

ЗАЧЕМ НУЖНЫ ДВОИЧНЫЕ ЧИСЛА

В предыдущем разделе была представлена система счисления с основанием 6 для иллюстрации того, как может осуществляться счёт в системах, отличных от десятичной. Однако намного более важной, хотя и странной на вид, является система счисления с основанием 2, или двоичная система счисления.

Напомним, что используемая нами десятичная система счисления основана на примитивной практике счёта на пальцах. Другими словами, пальцы были для человека доступным техническим средством счёта. Именно потому, что пальцев - десять, десятичная система кажется человеку естественной. Использование систем счисления с основаниями 5 и 20 имеет такое же историческое происхождение.

Возникает следующий вопрос: "Какая система естественна для ЭВМ?" Ясно, что вычислительные машины не имеют пальцев, следовательно, отсутствуют предпосылки к использованию десятичной системы. То, что естественно для ЭВМ, зависит от природы процессов, которые происходят в различных узлах вычислительной машины. Анализ работы ЭВМ показывает, что каждый процесс складывается из одного или более событий, которые либо происходят, либо - нет. Если взглянуть на некоторый участок перфокарты, то можно увидеть, что на каждой позиции перфокарты либо есть пробитое отверстие, либо его нет. Существует два, и только два возможных исхода. Отверстие не может быть пробито наполовину. Событие, результатом которого может быть только один из двух возможных исходов (отверстие пробито или не пробито), называется двоичным [4] . Ниже приведено несколько примеров различных двоичных событий.

Клавиша на клавиатуре

Нажата или не нажата

Отверстие в перфокарте

Пробито или не пробито

Включён или выключен

Зажжена или погашена

Цифровой сигнал из шине

Высокий или низкий уровень напряжения

СЧЁТ В ДВОИЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ

Счёт в двоичной системе выполняется практически так же, как в десятичной или в шестеричной системах счисления, с той разницей, что в двоичной системе имеется всего две цифры: 0 и 1. Счёт, как обычно, начинается с 0. Следующим числом является 1, но дальнейший счёт без добавления позиции слева невозможен, поскольку больше нет цифр. Поэтому происходит возврат к 0 и перенос 1 на следующую позицию, в результате будет получено двоичное число 10, которое соответствует числу 2 в десятичной системе счисления. В табл. 2.2 приведено представление чисел от 0 до 32 в двоичной системе счисления.

ДВОИЧНАЯ АРИФМЕТИКА

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

Аналогичный набор правил может быть выведен и для вычитания. На рис. 2.2 показаны некоторые простые действия с двоичными числами.

Рис. 2.2. Двоичные вычисления

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

что равняется 32 + 4 + 1 = 37. Отметим также, что 37 = 11 + 26, что и получено на рис. 2.2,в, Таблица степеней числа 2 представлена в конце книги.

2.4. ПРЕОБРАЗОВАНИЕ ЧИСЕЛ

ОСНОВНЫЕ АЛГОРИТМЫ

Существуют два распространённых способа преобразования чисел из одной системы счисления в другую. В одном из них используется умножение, в другом - деление. Преобразование умножением применяется для перевода чисел из какой-либо системы в систему счисления, в которой в данный момент выполняются арифметические действия. Для выполнения арифметических действий человек обычно использует десятичную систему счисления, тогда как большинство ЭВМ используют двоичную систему. Преобразование делением применяется для преобразования чисел системы, в которой в данный момент выполняются арифметические действия, в какую-либо другую систему.

ПРЕОБРАЗОВАНИЕ УМНОЖЕНИЕМ

Способ преобразования умножением основан на представлении чисел в виде суммы степеней. Например, в десятичной системе значение цифры определяется в зависимости от того, в каком разряде числа она находится, умножением соответственно на 1, 10, 100, 1000 и т.д. В двоичной системе такое умножение выполняется на степени числа 2, т.е. на 1, 2, 4, 8, 16, 32 и т.д. В общем случае в системе счисления с основанием b значения цифр, составляющих число, определяются умножением на степени числа b. Поэтому заданное в системе с основанием b число

можно представить в виде

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

Читатель может убедиться, что эта формула эквивалентна предыдущей. Отметим, что член 0* b равен 0 и его можно было бы исключить, однако его присутствие упрощает описание алгоритма. Алгоритм выполнения вычислений по этой формуле может быть описан следующим образом:

Шаг 1. Присвоить переменной ANSWER значение 0.

Шаг 2. Начать преобразование с самой левой цифры числа.

Шаг 3. Умножить значение переменной ANSWER на b.

Шаг 4. Получить значение следующего разряда числа (очередную цифру) и сложить его с хранящимся в переменной ANSWER значением.

Шаг 5. Если в числе есть ещё цифры, вернуться на шаг 3. Иначе переменная ANSWER содержит преобразованное число.

В качестве примера рассмотрим преобразование двоичного числа 10110 в десятичное. Ниже для каждого шага алгоритма приведены оставшиеся цифры двоичного числа и значения переменной ANSWER.

ПРЕОБРАЗОВАНИЕ ДЕЛЕНИЕМ

Способ перевода чисел из одной системы в другую с помощью деления по своему действию является обратным преобразованию, рассмотренному выше. Как известно, при делении десятичного числа на 10 остаток от деления будет равен значению цифры в самом правом разряде числа. Оставшиеся слева цифры числа образуют полученное при делении частное. Таким образом, при делении числа 3754 на 10 остаток равен 4, а частное равно 375. Этот же принцип соблюдается при делении числа в системе счисления с основанием b на число b. Остаток будет равен значению самой правой цифры числа, а частное будет представлено цифрами, оставшимися слева.

Так как частное содержит оставшиеся цифры, этот приём может повторяться, чтобы преобразовать все число. Ниже приведён алгоритм для перевода числа N в систему счисления с основанием b.

Шаг 1. Присвоить n значение N.

Шаг 2. Вычислить q (частное) и r (остаток) от деления n на b.

Шаг 3. Вывести содержимое r как очередную цифру числа в системе с основанием b (цифры располагаются справа налево).

Шаг 4. Присвоить n значение q. Если n не равно нулю, перейти на шаг 3. Иначе преобразование закончено. При использовании этого алгоритма для преобразования десятичного числа 25 в двоичное число получается следующая последовательность шагов:

Отметим, что алгоритм преобразования умножением использовался при преобразовании двоичного числа в десятичное, а алгоритм преобразования делением - для преобразования десятичного числа в двоичное. Причина такого выбора алгоритма заключается в том, что для нас естественной является десятичная арифметика. Положив это в основу общего правила, можно сказать, что при преобразовании чисел из одной системы счисления в другую выбор алгоритма зависит от того, в какой из этих двух систем выполняются арифметические действия. Если арифметические действия выполняются в той системе, в которую осуществляется преобразование, то следует выбрать алгоритм преобразования умножением, и наоборот, если арифметические действия выполняются в системе, из которой делается преобразование, то выбирают алгоритм преобразования делением. Человек, осуществляя преобразование вручную, пользуется десятичной арифметикой. Однако для ЭВМ, в частности для ЭВМ семейства VAX, естественной является двоичная арифметика. Поэтому в машинной программе следует ожидать применения алгоритма преобразования умножением для преобразования чисел из десятичной в двоичную систему и алгоритма преобразования делением для преобразования чисел из двоичной системы в десятичную, что совершенно противоположно тому, что делалось в рассмотренных выше примерах.

2.5. ШЕСТНАДЦАТЕРИЧНЫЕ ЧИСЛА

ЕЩЁ НЕМНОГО О ПРЕДСТАВЛЕНИИ ЧИСЕЛ

Можно заметить, что чем меньше основание системы счисления, тем меньше возможных значений у каждого разряда числа: 10 значений в десятичной системе, 6 - в системе с основанием 6, и 2 - в двоичной системе. Чем меньше значений может иметь каждый разряд, тем меньше информации несут разряды числа. Как следствие этого, для представления чисел в системе с основанием 6 требуется больше разрядов, чем для представления тех же чисел в десятичной системе. Например, число 10000 в системе с основанием 6 эквивалентно числу 1296 в десятичной системе. Ситуация ещё больше усложняется для двоичных чисел. Например, число 71230 в десятичной системе представляется как 10001011000111110 в двоичной системе, т.е. число разрядов двоичного представления числа более чем в 3 раза превышает число разрядов его десятичного представления. Обычно соотношение между разрядами двоичного и десятичного представления числа равно 3 1 /₃.

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

ШЕСТНАДЦАТЕРИЧНОЕ ПРЕДСТАВЛЕНИЕ ЧИСЕЛ

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

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

Рассмотрим теперь каждую группу из четырёх битов как четырёхбитовое двоичное число. В четырёх битах может быть образовано 2 4 , или 16, двоичных комбинаций. Таким образом, для обозначения 16 возможных комбинаций нужен набор из 16 простых символов. Как правило, для этого используются 10 цифр десятичной системы счисления и буквы латинского алфавита от А до F. Все эти символы являются шестнадцатеричными цифрами.

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

Шестнадцатеричное
представление

Таким образом, 1163Е является шестнадцатеричным представлением данной двоичной последовательности.

Было бы неверно думать, что шестнадцатеричное представление - это только код, который применяется для более простого представления двоичных чисел. Шестнадцатеричное представление чисел по праву образует систему счисления, а именно систему с основанием 16. Основная трудность, связанная с представлением шестнадцатеричных чисел, да и вообще чисел в любой системе счисления с основанием, превышающим 10, заключается в необходимости использования более 10 числовых символов для обозначения цифр. В результате получаются числа, которые не похожи на числа, например 1163Е. Однако вспомним основное правило счёта: счёт осуществляется последовательным перебором всех цифр до тех пор, пока не будет достигнуто значение старшей цифры, после чего выполняется перенос единицы в следующий разряд. В шестнадцатеричной системе значением старшей цифры является десятичное число 15, оно обозначается буквой F. Поэтому в шестнадцатеричной системе за числом F следует число 10, за числом FF - 100, за числом B7CFFF - B7D000. В табл. 2.3 приведены двоичные и шестнадцатеричные числа, эквивалентные десятичным числам от 1 до 100. Обратите внимание на соответствие между двоичными и шестнадцатеричными числами.

Рис. 2.3. Шестнадцатеричное представление

В языке ассемблера, в дампах памяти и файлов для упрощения записи чисел, имеющих в ЭВМ семейства VAX двоичное представление, широко используется шестнадцатеричное представление. Очевидно, что число 6ЕА7 не может быть десятичным, поэтому можно с уверенностью полагать, что для ЭВМ VAX это число является шестнадцатеричным. Но, например, число 1734 может интерпретироваться и как десятичное, и как шестнадцатеричное. Чтобы избежать недоразумений, шестнадцатеричные числа в программах на языке ассемблера ЭВМ VAX сопровождаются префиксом ^X . Числа без префикса ^X обычно рассматриваются как десятичные. В соответствии с этим далее там, где необходимо избежать разночтения, для обозначения шестнадцатеричных чисел будет применяться префикс ^X . Таким образом, если два предыдущих числа надо было обозначить как шестнадцатеричные, то их следовало бы записать как ^X 6AE7 и ^X 1734 .

СЛОЖЕНИЕ И ВЫЧИТАНИЕ ШЕСТНАДЦАТЕРИЧНЫХ ЧИСЕЛ

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

Самый правый разряд (разряд единиц) содержит ^X A и ^X 3 . Преобразуя сумму ^X A + ^X 3 в десятичную систему, получаем 10 + 3, или 13. Преобразуя число 13 обратно в шестнадцатеричную систему, находим ^X D . Эго значит, что сумма ^X A и ^X 3 равна ^X D без переноса в следующий разряд. На этом этапе сложения имеем:

В среднем разряде или в разряде "десятков" (десятичное число 16), сумма ^X 8 + ^X B , равна сумме 8 + 11 в десятичной системе, или числу 19. Преобразуя число 19 в шестнадцатеричную систему, получаем 16 + 3, или ^X 13 . Таким образом, сумма ^X 8 и ^X B равна ^X 3 с переносом в следующий старший разряд. (Перенос осуществляется всегда, когда десятичная сумма больше или равна 16.) На этом этапе сложения имеем:

Наконец, в самом левом разряде или в разряде "сотен" (десятичное число 256) сложим ^X 1 + ^X C + ^X A , что равняется сумме 1 + 12+ 10 в десятичной системе, или 23. Так как число 23 равно 16 + 7, оно равно ^X 17 или ^X 7 с переносом в следующий старший разряд. Окончательный результат сложения следующий:

Аналогично выполняется и вычитание. Вычитание чисел

начинается с самого правого разряда или разряда единиц. Разность ^X A - ^X 3 равна разности 10 - 3, или 7, в десятичной системе, что соответствует ^X 7 . (Поскольку 10 больше 3, заём из старшего разряда не требуется.) Выполнив это вычитание, получим:

В среднем разряде или в разряде "десятков" (десятичное число 16), разность ^X 8 - ^X B равна разности чисел 8 - 11 в десятичной системе. Поскольку 8 меньше 11, необходимо занять единицу (16 десятичное) из следующего старшего разряда. Таким образом, разность ^X 8 - ^X B равна результату выражения 16 + 8 - 11, или числу 13 с заёмом. В шестнадцатеричной системе это соответствует ^X D с заёмом. На этом этапе вычитания имеем

И наконец, в самом левом разряде или в разряде "сотен" (десятичное число 256) вычисляется выражение ^X C - ^X A - ^X 1 , где ^X 1 - значение заёма. Окончательный результат вычитания

Правильность вычитания можно проверить, убедившись, что сумма ^X AB3 и ^X 1D7 равна ^X C8A .

УПРАЖНЕНИЯ 2.1

1. Воспользуйтесь информацией, приведённой в энциклопедиях и словарях, и опишите три известные системы счисления, отличные от римской и арабской. Сравните эти системы:
   • а) по лёгкости освоения;
   • б) по применимости для вычислений;
   • в) по удобству представления больших чисел.
2. Продолжите счёт шестнадцатеричных и двоичных чисел, представленных в табл. 2.3, до числа 200 (десятичного).
3. Сложите приведённые ниже двоичные числа:
   

   а)

4. Выполните вычитание двоичных чисел, используя пары чисел из п. 3.
5. Преобразуйте следующие двоичные числа в десятичные:
   

   а)

6. Двоичные числа из п. 5 преобразуйте в шестнадцатеричные.
7. Сложите приведённые ниже шестнадцатеричные числа:
   

   а)

8. Выполните вычитание шестнадцатеричных чисел, используя пары чисел из п. 7.
9. Преобразуйте следующие шестнадцатеричные числа в десятичные:
   

   а)

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

   а)

10. Преобразуйте десятичные числа из п. 10 в шестнадцатеричные. Используйте в ответах обозначение ^X .
11. * Покажите, как выполняется счёт от 1 до числа, эквивалентного десятичному числу 200 в системе счисления с основанием 7. Как в этой системе можно отличить чётные числа от нечётных? Действует ли здесь такое же простое правило, как в десятичной системе?

2.6. ДВОИЧНАЯ АРИФМЕТИКА В ДОПОЛНИТЕЛЬНЫХ КОДАХ

ОСОБЕННОСТИ ПРЕДСТАВЛЕНИЯ ЧИСЕЛ В ВЫЧИСЛИТЕЛЬНЫХ МАШИНАХ

До сих пор при изложении материала предполагалось, что на длину чисел не накладывается никаких ограничений. Однако в вычислительных машинах арифметические операции в основном выполняются с помощью устройств, называемых регистрами. Регистр - это устройство, в котором содержится представление числа. Наглядным примером регистра может служить автомобильный одометр - счётчик пройденного расстояния. Шкала счётчика составлена из колёсиков с нанесёнными по окружности цифрами. При вращении колёсиков на шкале может быть отображено любое число в диапазоне 0 - 99999, в данном случае расстояние, выраженное в милях. Важно отметить наличие фиксированной верхней границы диапазона представляемых чисел. В вычислительных машинах большинство регистров состоят из строго определённого числа запоминающих элементов, и поэтому имеется фиксированная верхняя граница диапазона, зависящая от длины числа, которое может быть представлено в регистре. Например, в ЭВМ семейства VAX большинство операций ограничивается действиями, выполняемыми над числами длиной 8, 16 или 32 двоичных разрядов (битов). Из-за таких ограничений могут быть получены странные результаты, например когда одометр старого автомобиля, прошедшего более 100 тыс. миль, показывает небольшое расстояние.

Рис. 2.4. Пятибитовые числа без знака

Рис. 2.5. Сложение в пятиразрядном регистре

В качестве примера рассмотрим небольшую вычислительную машину с пятиразрядными двоичными регистрами. В пяти разрядах можно составить 2 5 , или 32, двоичные комбинации. Поэтому такой регистр можно использовать для счёта от 0 до 31 в десятичной системе или от 00000 до 11111 - в двоичной. Так как в счёте участвуют только положительные целые числа, то такая интерпретация содержимого регистра называется беззнаковой, а такие числа называются числами без знака. Любая попытка использовать в счёте числа больше 31 приведёт к циклическому обращению содержимого регистра в 0 и снова к отсчёту с нуля, что даст неверный результат, как в случае с одометром автомобиля, прошедшего более 99999 миль. Эта ошибка называется переполнением числа без знака. На рис. 2.4 показаны все 32 5-битовых числа и их беззнаковая десятичная интерпретация.

Однако на самом деле оказывается, что свойство переполнения может быть использовано для представления отрицательных целых чисел. Рассмотрим опять ЭВМ с пятиразрядными двоичными регистрами. Посмотрим, что произойдёт при сложении двоичного числа 11101 (десятичное число 29) с различными числами, такими как 7, 8 и 9. Сложение этих чисел в двоичной системе показано на рис. 2.5. Обратите внимание на то, что, так как мы ограничены использованием пяти разрядных двоичных регистров, при каждом сложении в ответе теряется разряд переноса.

ОТРИЦАТЕЛЬНЫЕ ЧИСЛА В ДОПОЛНИТЕЛЬНОМ КОДЕ

Исследуя результаты сложения, представленные на рис. 2.5, можно видеть, что при сложении двоичного числа 11101 с двоичным представлением любого из чисел 7, 8 или 9 полученная сумма меньше каждого второго слагаемого на 3, как если бы выполнялось вычитание числа 3. То же самое наблюдается в примерах с другими числами. В итоге при работе с 5-битовыми числами двоичное число 11101 можно рассматривать как десятичное число -3. Аналогично двоичное число 11111 при сложении подобно десятичному числу -1, двоичное 11110 - десятичному числу -2, и т.д.

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

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

На рис. 2.6 приведены все 32 возможных 5-битовых числа и их десятичная интерпретация как чисел со знаком. Самый левый разряд используется для обозначения знака числа: 1 обозначает отрицательные, а 0 - положительные числа. Это означает, что числа, подобные 11101, которые можно интерпретировать как большие числа без знака, на самом деле являются отрицательными числами в дополнительном коде. Из рис. 2.6 видно, что в пяти битах возможно представить в дополнительном коде отрицательные числа от -1 до -16 и положительные числа от 0 до 15. Заметьте, что имеется двоичное представление числа -16, но нет представления числа +16. Отсутствие симметрии обусловлено тем, что представление числа 0 относится к положительным числам. Любая попытка породить число меньше -16 или больше +15 в таком представлении приводит к ошибке, называемой переполнением числа со знаком.

Рис. 2.6. Пятибитовые числа в дополнительном коде

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

При интерпретации этих чисел как чисел без знака сложение эквивалентно сложению десятичных чисел 24 + 5 = 29. При сложении их как чисел со знаком эквивалентным является -8 + 5 = -3.

2.7. ПРЕДСТАВЛЕНИЕ ЧИСЕЛ В ЭВМ СЕМЕЙСТВА VAX

БАЙТЫ, СЛОВА И ДЛИННЫЕ СЛОВА

Как отмечалось выше, большинство операций в ЭВМ семейства VAX выполняются над группами из 8, 16 или 32 двоичных разрядов (или битов). Группа из 8 битов называется байтом (byte), группа из 16 битов - словом (word), а группа из 32 битов - длинным словом (longword).

Информация, содержащаяся в байте, может быть представлена непосредственно в виде 8 двоичных цифр, например

Однако обычно информация в байте представляется в виде двух шестнадцатеричных цифр. Содержимое рассмотренного выше байта в шестнадцатеричном виде представляется так:

Обратите внимание, что двоичное и шестнадцатеричное представления информации, содержащейся в байте, являются всего лишь различными способами её представления. На самом деле в ЭВМ байт представляется в двоичном виде. Для человека удобным является шестнадцатеричное представление.

В действительности слово "байт", обозначающее небольшое количество (кусочек) битов возникло в конце 50-х годов как каламбур. В слове bite (кусок) вторая буква была заменена на у, поскольку легко спутать слова bit и bite в печатном виде. Продолжая каламбур, группу из четырёх битов (полубайт) иногда называют словом nibble (огрызок) или даже nybble.

В восьми битах можно составить только 2 8 , или 256, двоичных комбинаций. Если 8-битовый байт используется для представления числа без знака, то возможно представить целые числа только от 0 до 255 (десятичные числа). Диапазон представления чисел со знаком ограничен от -128 до +127.

Чтобы избежать подобных ограничений, в ЭВМ семейства VAX для хранения большего количества информации используется 2, 4, 8 или даже 16 байтов. В ЭВМ семейства VAX информация, содержащаяся в двух байтах, называется словом. Так как каждый байт состоит из 8 битов (две шестнадцатеричные цифры), то слово состоит из 16 битов (четыре шестнадцатеричные цифры) информации. Число ^X 1A2B в двоичном виде можно представить так:

Следующей, более крупной единицей информации является длинное слово, состоящее из двух слов, или четырёх байтов. Так как содержимое каждого байта (8 битов) может быть представлено двумя шестнадцатеричными цифрами, то содержимое длинного слова (32 бита) представляется как 8 шестнадцатеричных цифр. Длинное слово ^X 1A2B3C4D можно представить в двоичном виде так:

Ещё более крупными единицами информации являются квадраслово и октаслово. В соответствии со своим названием квадраслово состоит из четырёх слов, или 8 байтов. Квадраслово представляется 16 шестнадцатеричными цифрами (64 бита). Октаслово состоит из восьми слов, или 16 байтов (128 битов), а его содержимое может быть представлено 32 шестнадцатеричными цифрами. В данной книге чаще всего будут использоваться такие единицы информации, как байт и длинное слово. В табл. 2.4 приведены различные единицы информации, используемые в ЭВМ семейства VAX.

Почти на всех современных вычислительных машинах понятие "байт" служит для обозначения 8 битов информации. Однако количество битов в слове зависит от производителя и конкретной модели ЭВМ. Например, в ЭВМ DECsystem10 и DECSYSTEM20 слово составляют 36 битов информации, тогда как в больших ЭВМ фирмы IBM, как правило, слово - это 32 бита информации. Для совместимости ЭВМ семейства VAX с появившимся ранее семейством ЭВМ PDP-11, описанными гл. 1, длина слова была определена как 16 битов.

Длинное слово (longword)

Как показывают предыдущие примеры, шестнадцатеричное представление содержимого байтов, слов и длинных слов намного компактнее, чем двоичное представление. Поэтому при описании операций ЭВМ семейства VAX, как правило, будет использоваться шестнадцатеричное представление. Это возможно потому, что во многих случаях представление информации в шестнадцатеричном и двоичном виде приводит к эквивалентным результатам. Ниже дан пример сложения двух байтов.

0010 1110
+ 0100 1111
0111 1101

Суммой содержимого двух байтов, представленных в шестнадцатеричном виде ^X 2E и ^X 4F , является ^X 7D , что в принципе идентично шестнадцатеричному представлению результата, полученному при сложении двоичных чисел.

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

ПРЕДСТАВЛЕНИЕ ЦЕЛЫХ ЧИСЕЛ В ФОРМАТЕ БАЙТА

Для представления целых чисел со знаком и без знака в байте могут использоваться 8 битов. В табл. 2.5 показана интерпретация байтов, представленных в шестнадцатеричном виде от ^X 00 до ^X FF , как чисел без знака и со знаком. Как видно из таблицы, числа без знака могут быть представлены в диапазоне от 0 - 255, где код ^X 00 является представлением числа 0, а код ^X FF - представлением числа 255. Для представления чисел со знаком применяется дополнительный код. Числа со знаком представляются в диапазоне от - 128 до +127. Заметим, что код ^X 80 представляет число - 128, код ^X FF - число -1, код ^X 00 - число 0, а код ^X 7F - число + 127.

По отношению к 5-битовым числам было отмечено, что для чисел со знаком и без знака применимы одни и те же правила сложения. Это же справедливо и по отношению к 8-битовым числам со знаком и без знака. Различие состоит только в способе интерпретации этих чисел. Например, при сложении ^X FC с ^X 02 результатом является ^X FE . В случае беззнаковой интерпретации это соответствует сложению чисел 252 и 2, что в сумме даёт 254. При интерпретации этих кодов как представлений чисел со знаком приведённый пример соответствует сложению чисел -4 и 2, а полученный результат будет равен -2.

Ошибки переполнения возможны при любой интерпретации. Например, суммой ^X FF и ^X 03 является ^X 02 . (В обычном случае, при сложении чисел без знака, правильным результатом была бы сумма ^X 102 , но это число не поместится в разрядной сетке байта.) Для чисел со знаком этот результат корректен, так как сумма чисел -1 и 3 равна 2. Однако для чисел без знака он ошибочен, поскольку сумма чисел 255 и 3 не равна 2. В данном случае произошло переполнение числа без знака. Аналогично суммой ^X 7E и ^X 04 является ^X 82 . При интерпретации этих кодов как чисел без знака полученный результат будет правильным: 126 + 4 = 130, а при интерпретации их как чисел со знаком результат неверен: 126 + 4 = -126. В этой ситуации произошло переполнение числа со знаком. Очевидно, что возникновение ситуации переполнения любого рода служит признаком того, что при выполнении арифметической операции мог быть получен неверный результат. В гл. 6 объясняется, как осуществляется проверка переполнения.

ПРЕДСТАВЛЕНИЕ ЦЕЛЫХ ЧИСЕЛ В ФОРМАТЕ СЛОВА И ДЛИННОГО СЛОВА

Кроме целых чисел в формате байта ЭВМ семейства VAX могут работать с целыми числами в формате 16-битового слова, 32-битового длинного слова и отчасти - с целыми числами в формате 64-битового квадраслова. Это позволяет выполнять арифметические операции над числами с более широким диапазоном значений. Например, при представлении целых чисел в форматах байта, слова и длинного слова значения целых чисел без знака находятся в следующих диапазонах:

^X FFFF , или
65 535

^X FFFFFFFF , или
4 294 967 295

Ниже приводятся граничные значения представления целых чисел со знаком в формате байта, слова и длинного слова, а также показано представление чисел - 2, - 1, 0, +1 и +2 в этих форматах.

^X 8000 , или
-32 768

^X 80000000 , или
-2 147 483 648

Минимальное значение
плюс единица

^X 8001 , или
-32 767

^X 80000001 , или
-2 147 483 647

Максимальное значение
минус единица

^X 7FFE , или
+32 766

^X 7FFFFFFE , или
+2 147 483 646

^X 7FFF , или
+32 767

^X 7FFFFFFF , или
+2 147 483 647

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

2.8. БУЛЕВА ЛОГИКА

ЛОГИЧЕСКИЕ ЗНАЧЕНИЯ И ОПЕРАЦИИ

В XIX в. английский математик Джордж Буль разработал алгебраические методы выполнения операций над логическими значениями "истина" (true) и "ложь" (false). При работе с вычислительными машинами вполне пригодно иногда интерпретировать двоичные значения 1 и 0 как логические значения "истина" и "ложь".

Для обработки логических значений необходимо иметь логические операции. Основными логическими операциями являются операции И (AND), ИЛИ (OR) и НЕ (NOT). Операции И и ИЛИ объединяют истинностные значения двух высказываний, почти так же, как в естественном языке. Например, высказывание " А И В" истинно тогда, и только, когда истинны оба высказывания " А" и " В". Аналогично высказывание " А ИЛИ В" истинно тогда, когда истинно одно из высказываний " А" или " В" или истинны оба высказывания " А" и " В". Операция НЕ изменяет истинностное значение высказывания на противоположное. Таким образом, высказывание " НЕ А" истинно тогда, когда высказывание " А" ложно, а высказывание " НЕ А" ложно тогда, когда высказывание " А" истинно. На рис. 2.7 показаны все возможные комбинации истинностных значений для трёх основных логических операций.

0 И 0 = 0

0 ИЛИ 0 = 0

НЕ 0 = 1

0 И 1 = 0

0 ИЛИ 1 = 1

НЕ 1 = 0

1 И 0 = 0

1 ИЛИ 0 = 1

1 И 1 = 1

1 ИЛИ 1 = 1

Рис. 2.7. Логические операции

Таблицы логических операций, подобные приведённым на рис. 2.7, называются таблицами истинности и могут применяться для определения любой логической операции помимо основных трёх операций, показанных выше. Например, ещё одной обычно используемой логической операцией является операция ИСКЛЮЧАЮЩЕЕ ИЛИ. Она определяется так же, как и операция ИЛИ, но в случае истинности обоих операндов значение операции ложно. Ниже дана таблица истинности для операции ИСКЛЮЧАЮЩЕЕ ИЛИ:

Оказывается, что любая логическая операция может быть составлена из трёх основных операций: И, ИЛИ и НЕ. Например,

А ИСКЛЮЧАЮЩЕЕ ИЛИ В = (А ИЛИ В) И НЕ (А И В)

ПОБИТОВАЯ ОБРАБОТКА

ЭВМ семейства VAX включают инструкции для выполнения логических операций над содержимым байтов, слов и длинных слов. Логические операции в ЭВМ семейства VAX реализованы таким образом, что выполняются поразрядно над соответствующими битами байта, слова и длинного слова. Например, с содержимым двух длинных слов может быть выполнена следующая операция:

Отметим, что каждый бит результата является результатом логической операции ИЛИ над соответствующими битами двух операндов. Кроме чисто логических имеются операции, которые могут использовать логические операции для побитовой обработки. Следующий пример иллюстрирует применение логической операции И для маскирования (сброса в 0) самых левых 16 бит в длинном слове:

В заключение отметим, что при выполнении логической операции НЕ над содержимым длинного слова каждый бит длинного слова будет инвертирован, т.е. произойдёт замена каждой 1 на 0, а каждого 0 - на 1.

2.9. ДРУГИЕ СПОСОБЫ КОДИРОВАНИЯ

ВОСЬМЕРИЧНОЕ ПРЕДСТАВЛЕНИЕ

Большинство вычислительных машин имеют количество информации, запоминаемое в двоичном виде в регистрах и кратное 8 битам, в том числе 8, 16, 32 и 64 бита. Так как такие числа делятся без остатка только на 1, 2, 4 и 8, то единственными возможными системами представления чисел, разделяющими содержимое регистров на равное число бит, могут быть двоичная система, система с основанием 4, шестнадцатеричная система и система с основанием 256. Как уже обсуждалось, запись чисел в двоичной системе слишком длинная. Система с основанием 4 в этом смысле не намного лучше, а система с основанием 256 невероятно трудна для изучения. Остаётся шестнадцатеричная система; именно она и является общераспространённой для большинства ЭВМ нынешнего поколения.

Однако в вычислительных машинах предыдущего поколения широко применялись регистры с числом разрядов, кратным 6 битам. В итоге предпочтение обычно отдавалось системе счисления с основанием 8, иначе - восьмеричной системе счисления, так как в ней двоичные числа можно разделить на группы из трёх битов. Среди ЭВМ, для которых использовалось восьмеричное представление двоичных чисел, были все основные ЭВМ фирмы DEC, предшествующие ЭВМ семейства VAX, ЭВМ фирмы CDC, а также большинство ЭВМ серии IBM 7000.

Чтобы преобразовать двоичное число в восьмеричное, необходимо разделить двоичное число на группы из трёх битов, начиная справа. Слева к двоичному числу могут быть добавлены нули для гарантии того, что количество разрядов двоичного числа будет точно кратно 3. Затем каждая группа из трёх двоичных цифр заменяется их числовым эквивалентом. Соответствие между двоичным и восьмеричным представлением чисел можно найти в верхней половине рис. 2.3, где рассматривалось преобразование шестнадцатеричных чисел. Например, двоичное число 1101110011100010 может быть преобразовано в восьмеричное следующим образом:

Одно преимущество, которое имеет восьмеричная система перед шестнадцатеричной, состоит в том, что она проще для освоения и в ней легче выполнять арифметические действия вручную. Но из-за того, что используется разбиение на группы из трёх битов, восьмеричное представление информации плохо сочетается со структурой байта, слова и длинного слова, принятых в ЭВМ семейства VAX. Тем не менее восьмеричная система представляет определённый интерес для пользователей ЭВМ семейства VAX вследствие их совместимости с предшествующим семейством ЭВМ PDP-11, описанным в гл. 1. Дело в том, что в документации для ЭВМ семейства PDP-11 в основном применялось восьмеричное представление информации, чтобы сохранить совместимость с другими разработками фирмы DEC, уже существовавшими к моменту выпуска PDP-11.

ПРЕДСТАВЛЕНИЕ ЧИСЕЛ В ОБРАТНОМ КОДЕ

Как описывалось выше, отрицательные числа в дополнительном коде могут быть получены с помощью инвертирования всех битов положительного числа с последующим прибавлением 1. Например, 8-битовое представление числа -3 получается следующим образом:

В противоположность этому в некоторых ЭВМ отрицательные числа образуются простым инвертированием 0 и 1. В них для образования отрицательного числа выполняется логическая операция НЕ. Например, 8-битовым представлением числа -3 является НЕ 00000011 или 11111100. Такой способ представления чисел называется системой представления чисел в обратном коде или поразрядным дополнением до 1, так как отрицательное число может быть также получено при вычитании положительного числа из двоичного числа, во всех разрядах которого содержатся единицы. Например,

Особенность системы представления чисел в обратном коде состоит в том, что в ней имеется два представления числа 0. В случае 8 битовых чисел этими представлениями являются 00000000 и его дополнение до единицы 11111111. Наличие двух представлений числа 0 требует от программистов особого внимания при проверке результатов на равенство нулю. При использовании системы представления чисел в обратном коде соответственно должны быть несколько модифицированы арифметические операции сложения и вычитания, умножения и деления. Так как арифметика в обратных кодах применяется лишь в немногих вычислительных машинах, то в данной книге эти вопросы рассматриваться не будут [5] .

ДРУГИЕ СПОСОБЫ ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ

Числа могут быть представлены и другими способами. Например, четыре бита могут использоваться для представления десятичной цифры, хотя в четырёх битах может быть составлено и 16 различных комбинаций. Если шесть из этих возможных комбинаций рассматривать как "запрещённые", то оставшиеся десять "разрешённых" комбинаций в результате образуют 10-позиционный переключатель, который можно использовать для представления одной десятичной цифры. В этой системе последовательность двоичных цифр

представляет десятичное число 189204 (где код 0000 является представлением десятичной цифры 0, код 0001 представляет десятичную цифру 1, и т.д.). Такое представление чисел называется двоично-десятичным или упакованным десятичным. Ещё одно представление чисел основывается на экспоненциальной форме записи чисел и называется представлением действительных чисел или чисел с плавающей точкой. Оно подобно экспоненциальной форме записи, применяемой для представления больших чисел в языках высокого уровня, таких как Фортран и Паскаль, а также в калькуляторах для научных расчётов (например, 3.84536Е+08).

Так как особое внимание уделялось представлению чисел, в конечном счёте у читателя может сложиться впечатление, что вычислительные машины в основном используются для выполнения арифметических вычислений. Но это неверно. Последовательности двоичных цифр могут применяться для представления любого фиксируемого физического события. Например, многие терминалы способны напечатать 95 разных символов (включая пробел). В семи битах информации может быть составлено 2 7 , или 128, различных комбинаций. Таким образом, достаточно иметь семь битов для представления какого-либо одного из 95 печатных символов, при этом 128 - 95, или 33 комбинации, могут использоваться для представления служебных символов, т.е. как код специальных функциональных клавиш клавиатуры терминала, таких как RETURN (Возврат каретки) или TAB (Табуляция). Действительно, в гл. 8 такой 7-битовый код будет использоваться при обработке символьных строк. Способы представления символьной информации играют очень важную роль. Например, они применяются в процессе трансляции программы с языка высокого уровня или с языка ассемблера в машинный язык.

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

И наконец, последний пример. Возможно представлять изображения в виде битовых строк. Для этого на фотографию накладывается сетка-шаблон, которая может иметь 1000 строк и 1000 столбцов. Для каждой из миллиона ячеек сетки измеряется интенсивность отражённого светового потока, а результат преобразуется в двоичное число. (Если различается 64 градации яркости, то интенсивность светового потока, отражённого от каждой ячейки, может быть преобразована в 6-битовое число, при этом двоичный код 000000 служит для представления уровня белого, код 111111 - уровня чёрного тона, а все другие комбинации служат для представления различных полутонов.) Теперь изображение преобразовано в такую форму, при которой оно может быть обработано ЭВМ. Подобные методы кодирования изображений обычно применяются при обработке на ЭВМ фотографий, полученных со спутников, некоторых видов рентгеновских и других медицинских снимков.

УПРАЖНЕНИЯ 2.2

1. Интерпретируя 64 возможные двоичные комбинации, которые могут быть образованы в шести битах, как представление чисел в дополнительном коде, приведите эквивалентные им десятичные числа со знаком.
2. Сложите следующие 8-битовые пары чисел в дополнительном коде с указанием всех переносов, в том числе и тех, что теряются из-за ограничения разрядной сетки в 8-разрядном регистре. В следующих примерах приведите для двоичных слагаемых и результата эквивалентные им десятичные числа со знаком: