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

2.1. ВВЕДЕНИЕ

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

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

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

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

I II III IV V ...

Римские цифры

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

1 2 3 4 5...

Арабские цифры

Счёт по-английски

Кучки камешков

Игральные кости

Счёт по-французски

Рис. 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.1
Счёт в системе счисления с основанием 6
Основание 10 Основание 6 Основание 10 Основание 6
0 0 19 31
1 1 20 32
2 2 21 33
3 3 22 34
4 4 23 35
5 5 24 40
6 10 25 41
7 11 26 42
8 12 27 43
9 13 28 44
10 14 29 45
11 15 30 50
12 20 31 51
13 21 32 52
14 22 33 53
15 23 34 54
16 24 35 55
17 25 36 100
18 30    

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

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

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

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

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

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

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

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

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

Двухпозиционный тумблер

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

Электрическая лампа

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

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

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

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

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

Таблица 2.2
Счёт в двоичной системе счисления
Основание 10 Основание 2 Основание 10 Основание 2
0 0 17 10001
1 1 18 10010
2 10 19 10011
3 11 20 10100
4 100 21 10101
5 101 22 10110
6 110 23 10111
7 111 24 11000
8 1000 25 11001
9 1001 26 11010
10 1010 27 11011
11 1011 28 11100
12 1100 29 11101
13 1101 30 11110
14 1110 31 11111
15 1111 32 100000
16 10000    

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

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

0 + 0 = 00 (0 без переноса);
0 + 1 = 01 (1 без переноса);
1 + 0 = 01 (1 без переноса);
1 + 1 = 10 (0 с переносом).

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

а)

 101
+ 10
111
 

б)

 110
- 10
100

в)

 11010
+ 1011
100101
 

г)

 11001
- 1101
1100

д)

  11111
+   101
100100
 

е)

 100000
-  1011
10101

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

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

11010 = (1*16) + (1*8) + (0*4) + (1*2) + (0*1) = 16 + 8 + 2=26,

Аналогично

1011 = (1*8) + (0*4) + (1*2) + (1*1) = 8 + 2+1 = 11.

И наконец,

100101 = (1*32) + (0*16) + (0*8) + (1 *4) + (0*2) + (1*1),

что равняется 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 число

d4d3d2d1d0

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

d4*b4 + d3*b3 + d2*b2 + d1 *b1 + d0.

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

((((0*b+d4) *b + d3) *b + d2) *b+d1) *b +d0.

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

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

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

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

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

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

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

Шаг ANSWER Оставшиеся разряды
двоичного числа
1 0 -
2 0 10110
3 0 10110
4 1 0110
5 1 0110
3 2 0110
4 2 110
5 2 110
3 4 110
4 5 10
5 5 10
3 10 10
4 11 0
5 11 0
3 22 0
4 22 -
5 22 Двоичное число 10110
соответствует
десятичному числу 22

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

Способ перевода чисел из одной системы в другую с помощью деления по своему действию является обратным преобразованию, рассмотренному выше. Как известно, при делении десятичного числа на 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 в двоичное число получается следующая последовательность шагов:

Шаг n q r Вывод Преобразованное
число
 
1 25          
2 25 12 1      
3 25 12 1 1 1  
4 12 12 1   1  
2 12 6 0   1  
3 12 6 0 0 01  
4 6 6 0   01  
2 6 3 0   01  
3 6 3 0 0 001  
4 3 3 0   001  
2 3 1 1   001  
3 3 1 1 1 1001  
4 1 1 1   1001  
2 1 0 1   1001  
3 1 0 1 1 11001 Искомое
4 0 0 1   11001 число равно 11001

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

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

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

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

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

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

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

0001

0001

0110

0011

1110

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

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

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

0001

0001

0110

0011

1110

Двоичное число

1

1

6

3

Е

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

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

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

Двоичная комбинация Шестнадцатеричное представление
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 8
1001 9
1010 А
1011 В
1100 С
1101 D
1110 Е
1111 F

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

Таблица 2.3
Десятичные, двоичные и шестнадцатеричные представления
Десяти-
чные
числа
Двоич-
ные
числа
Шестна-
дцатери-
чные числа
Десяти-
чные
числа
Двоич-
ные
числа
Шестна-
дцатери-
чные числа
Десяти-
чные
числа
Двоич-
ные
числа
Шестна-
дцатери-
чные числа
Десяти-
чные
числа
Двоич-
ные
числа
Шестна-
дцатери-
чные числа
1 1 1 26 11010 1A 51 110011 33 76 1001100
2 10 2 27 11011 1B 52 110100 34 77 1001101 4D
3 11 3 28 11100 1C 53 110101 35 78 1001110
4 100 4 29 11101 1D 54 110110 36 79 1001111 4F
5 101 5 30 11110 1E 55 110111 37 80 1010000 50
6 110 6 31 11111 1F 56 111000 38 81 1010001 51
7 111 7 32 100000 20 57 111001 39 82 1010010 52
8 1000 8 33 100001 21 58 111010 83 1010011 53
9 1001 9 34 100010 22 59 111011 84 1010100 54
10 1010 А 35 100011 23 60 111100 3C 85 1010101 55
11 1011 В 36 100100 24 61 111101 3D 86 1010110 56
12 1100 С 37 100101 25 62 111110 87 1010111 57
13 1101 D 38 100110 26 63 111111 3F 88 1011000 58
14 1110 E 39 100111 27 64 1000000 40 89 1011001 59
15 1111 F 40 101000 28 65 1000001 41 90 1011010
16 10000 10 41 101001 29 66 1000010 42 91 1011011
17 10001 11 42 101010 67 1000011 43 92 1011100
18 10010 12 43 101011 68 1000100 44 93 1011101 5D
19 10011 13 44 101100 69 1000101 45 94 1011110
20 10100 14 45 101101 2D 70 1000110 46 95 1011111 5F
21 10101 15 46 101110 71 1000111 47 96 1100000 60
22 10110 16 47 101111 2F 72 1001000 48 97 1100001 61
23 10111 17 48 110000 30 73 1001001 49 98 1100010 62
24 11000 18 49 110001 31 74 1001010 99 1100011 63
25 11011 19 50 110010 32 75 1001011 100 1100100 64

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

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

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

  С 8 А
+ А В 3

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

    0       (перенос)
  С 8 А
+ А В 3
      D

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

  1 0       (перенос)
  С 8 А
+ А В 3
    3 D

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

  1 1 0     (перенос)
  С 8 А
+ А В 3
1 7 3 D

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

  С 8 А
- А В 3

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

    0       (заём)
  С 8 А
- А В 3
      7

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

- 1 0       (заём)
  С 8 А
- А В 3
    D 7

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

- 1 0       (заём)
  С 8 А 
- А В 3
  1 D 7

Правильность вычитания можно проверить, убедившись, что сумма ^XAB3 и ^X1D7 равна ^XC8A.

УПРАЖНЕНИЯ 2.1

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

    101|
    + 11|
     

    б)

    110|
    +101|

    в)

    101|
    +101|

    г)

    10111|
    + 1010|
     

    д)

    11011|
    + 1001|

    е)

    11101|
    + 101|

    ж)

    1011011|
    + 101101|
     

    з)

    110101101|
    + 10110010|

    и)

    110101100011|
    +101100011010|

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

    101;

    б)

    11010;

    в)

    111010;

    г)

    101110;

    д)

    110011;

    е)

    1011101;

    ж)

    1100011;

    з)

    1101111;

    и)

    11100101;

    к)

    1110101011;

    л)

    101110100001;

    м)

    11001010101110.

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

    7F
    + 32
     

    б)

    Е3
    +

    в)

    Е3
    +АА

    г)

    А7В
    + 82
     

    д)

    5Е4
    + 39D

    е)

    Е3В
    +C8D

    ж)

    А5В9
    + 276
     

    з)

    48FD
    +3CFF

    и)

    2В89
    + FFF

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

    ^XA;

    б)

    ^X10;

    в)

    ^X100;

    г)

    ^X1F;

    д)

    ^X2A;

    е)

    ^X45;

    ж)

    ^XA4;

    з)

    ^XC8;

    и)

    ^XDA;

    к)

    ^X1374;

    л)

    ^X1A3D;

    м)

    ^XF3DE.

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

    10;

    б)

    15;

    в)

    24;

    г)

    37;

    д)

    42;

    е)

    51;

    ж)

    85;

    з)

    97;

    и)

    128;

    к)

    1000;

    л)

    3555;

    м)

    5999.

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

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

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

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

00000

0

01000

8

10000

16

11000

24

00001

1

01001

9

10001

17

11001

25

00010

2

01010

10

10010

18

11010

26

00011

3

01011

11

10011

19

11011

27

00100

4

01100

12

10100

20

11100

28

00101

5

01101

13

10101

21

11101

29

00110

6

01110

14

10110

22

11110

30

00111

7

01111

15

10111

23

11111

31

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

11101

= 29

11101

= 29

11101

= 29

+ 00111

= 7

+ 01000

= 8

+ 01001

= 9

00100

= 4

00101

= 5

00110

= 6

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

В качестве примера рассмотрим небольшую вычислительную машину с пятиразрядными двоичными регистрами. В пяти разрядах можно составить 25, или 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) и не помещается в разрядной сетке регистра. Например,

 100000
- 00011 = 3
  11101 = -3

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

00011   равно 3
11100   замена 0 на 1 и наоборот
11101   после прибавления 1 получается -3

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

10000

-16

11000

-8

00000

0

01000

8

10001

-15

11001

-7

00001

1

01001

9

10010

-14

11010

-6

00010

2

01010

10

10011

-13

11011

-5

00011

3

01011

11

10100

-12

11100

-4

00100

4

01100

12

10101

-11

11101

-3

00101

5

01101

13

10110

-10

11110

-2

00110

6

01110

14

10111

-9

11111

-1

00111

7

01111

15

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

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

 11000
+00101
 11101

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

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

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

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

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

00111010

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

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

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

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

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

0001

1010

0010

1011

1

А

2

В

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

0001

1010

0010

1011

0011

1100

0100

1101

1

А

2

В

3

С

4

D

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

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

Таблица 2.4
Единицы информации на ЭВМ семейства VAX

Формат данных

Число

битов

шестнадцатерич-ных цифр

байтов

слов

Байт (byte)

8

2

1

-

Слово (word)

16

4

2

1

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

32

8

4

2

Квадраслово (quadword)

64

16

8

4

Октаслово (octaword)

128

32

16

8

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

Двоичный код Шестнадцатеричный код

  0010   1110
+ 0100   1111
  0111    1101

 2Е
+4F
 7D

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

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

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

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

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

Таблица 2.5
Представление чисел со знаком и без знака в формате байта
Шестнадцатеричное представление Интерпретация как
число без знака
Интерпретация как
число со знаком

00

0

0

01

1

1

02

2

2

03

3

3

04

4

4

05

5

5

.

.

.

.

.

.

.

.

.

124

124

7D

125

125

126

126

7F

127

127

80

128

-128

81

129

-127

82

130

-126

83

131

-125

.

.

.

.

.

.

.

.

.

FC

252

-4

FD

253

-3

FE

254

-2

FF

255

-1

Ошибки переполнения возможны при любой интерпретации. Например, суммой ^XFF и ^X03 является ^X02. (В обычном случае, при сложении чисел без знака, правильным результатом была бы сумма ^X102, но это число не поместится в разрядной сетке байта.) Для чисел со знаком этот результат корректен, так как сумма чисел -1 и 3 равна 2. Однако для чисел без знака он ошибочен, поскольку сумма чисел 255 и 3 не равна 2. В данном случае произошло переполнение числа без знака. Аналогично суммой ^X7E и ^X04 является ^X82. При интерпретации этих кодов как чисел без знака полученный результат будет правильным: 126 + 4 = 130, а при интерпретации их как чисел со знаком результат неверен: 126 + 4 = -126. В этой ситуации произошло переполнение числа со знаком. Очевидно, что возникновение ситуации переполнения любого рода служит признаком того, что при выполнении арифметической операции мог быть получен неверный результат. В гл. 6 объясняется, как осуществляется проверка переполнения.

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

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

  Байт Слово Длинное слово
Нуль

^X00

^X0000

^X00000000

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

^XFF, или
255

^XFFFF, или
65 535

^XFFFFFFFF, или
4 294 967 295

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

 

Байт

Слово

Длинное слово

Минимальное значение

^X80, или
-128

^X8000, или
-32 768

^X80000000, или
-2 147 483 648

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

^X81, или
-127

^X8001, или
-32 767

^X80000001, или
-2 147 483 647

-2

^XFE

^XFFFE

^XFFFFFFFE

-1

^XFF

^XFFFF

^XFFFFFFFF

0

^X00

^X0000

^X00000000

+1

^X01

^X0001

^X00000001

+2

^X02

^X0002

^X00000002

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

^X7E, или
+ 126

^X7FFE, или
+32 766

^X7FFFFFFE, или
+2 147 483 646

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

^X7F, или
+127

^X7FFF, или
+32 767

^X7FFFFFFF, или
+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, называются таблицами истинности и могут применяться для определения любой логической операции помимо основных трёх операций, показанных выше. Например, ещё одной обычно используемой логической операцией является операция ИСКЛЮЧАЮЩЕЕ ИЛИ. Она определяется так же, как и операция ИЛИ, но в случае истинности обоих операндов значение операции ложно. Ниже дана таблица истинности для операции ИСКЛЮЧАЮЩЕЕ ИЛИ:

0 ИСКЛЮЧАЮЩЕЕ ИЛИ 0 = 0
0 ИСКЛЮЧАЮЩЕЕ ИЛИ 1 = 1
1 ИСКЛЮЧАЮЩЕЕ ИЛИ 0 = 1
1 ИСКЛЮЧАЮЩЕЕ ИЛИ 1 = 0

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

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

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

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

      1011  0111  1100  1010  0000  0000  1111  1111
ИЛИ   0010  0101  0101  0011  0000  1111  0000  1111      
      1011  0111  1101  1011  0000  1111  1111  1111

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

     1011  0111  0000  1111  1111  0000  1010  1111    длинное слово
И    0000  0000  0000  0000  1111  1111  1111  1111    маска
     0000  0000  0000  0000  1111  0000  1010  1111    результат 

В заключение отметим, что при выполнении логической операции НЕ над содержимым длинного слова каждый бит длинного слова будет инвертирован, т.е. произойдёт замена каждой 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 может быть преобразовано в восьмеричное следующим образом:

001

101

110

011

100

010

1

5

6

3

4

2

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

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

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

 00000011 = 3
 11111100 = НЕ 00000011
+       1
 11111101 = -3 в дополнительном коде

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

 11111111
-00000011 = 3
 11111100 = -3 в обратном коде.

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

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

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

0001    1000    1001    0010    0000    0100

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

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

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

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

УПРАЖНЕНИЯ 2.2

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

    00000011
    00000101
      

    б)

    00001011
    11111100

    в)

    11111101
    11111010
     

    г)

    11101100
    11111111

    д)

    00100111
    11011011
     

    е)

    10011101
    00100101

  3. Для каждой пары чисел из п. 2 выполните вычитание второго числа из первого. Укажите заёмы, в том числе и те, которые теряются.
  4. Преобразуйте в шестнадцатеричную систему представления числа из п. 2 и выполните сложение байтов в шестнадцатеричном виде. Укажите переносы, в том числе и те, которые теряются в случае переноса из старшего разряда числа.
  5. Повторите п. 4, выполнив вместо сложения вычитание шестнадцатеричных чисел. Укажите заёмы, включая потерянные.
  6. Каждое из следующих длинных слов представляет число со знаком. Приведите соответствующие им десятичные числа.

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

    a)

    0000000F;

    б)

    FFFFFFF0;

    в)

    00000100;

    г)

    FFFFFF00;

    д)

    00001000;

    е)

    FFFFF000;

    ж)

    00ABCDEF;

    з)

    FFABCDEF.

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

    0011 0111;

    6)

    1010 0001;

    в)

    0111 1100;

    г)

    1110 1111;

    д)

    0011 1001 1110 0101;

    е)

    1010 1011 1111 0010;

    ж)

    0011 1011 1110 1111 0101 1000 1101 0001;

       
    з)

    1101 1110 0110 1001 1000 1110 0101 1110.

       
  8. Каждый из следующих байтов представляет собой число со знаком от -128 до +127.

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

    a)

    01;

    б)

    FF;

    в)

    0F;

    г)

    1А;

    д)

    FA;

    е)

    А0;

    ж)

    7А;

    з)

    83.

  9. Предполагая, что содержимое каждого байта из п. 8 является представлением числа без знака от 0 до 255, приведите эквивалентные им десятичные числа.
  10. Для каждой пары двоичных чисел из п. 2 выполните логические операции И, ИЛИ и ИСКЛЮЧАЮЩЕЕ ИЛИ.
  11. Покажите, как выполняется счёт в восьмеричной системе от 0 до числа, эквивалентного десятичному числу 200.
  12. Для двоичных чисел из п. 7 приведите эквивалентные им восьмеричные числа.

 

< НАЗАД ОГЛАВЛЕНИЕ ВПЕРЁД >


[1] Например, на циферблатах часов. - Прим. ред.

[2] Арабские цифры проникли в европейскую культуру в XII в. при переводе на латынь книги арабского математика Мухаммеда Ибн-Муса аль-Хорезми (780 - 850 гг.). Трансформированное имя аль-Хорезми лежит в основе слова "алгоритм, означающего однозначно определённый пошаговый процесс решения задачи".

[3] "Дюжина дюжин". - Прим. ред.

[4] Читатели могут отметить, что для таких событий, как пробивка отверстий, число возможных состояний может быть более двух. Например, может быть пробито три, четыре и более отверстий различной формы. Однако в вычислительной технике, как правило, это не практикуется, поскольку устройство, способное надёжно распознавать несколько отверстий различной формы, было бы значительно дороже устройства, умеющего распознавать только наличие или отсутствие пробивки.

[5] Замечательным примером вычислительных машин, в которых для представления чисел используется обратный код, являются ЭВМ CPC Cyber.