1. Представление целых чисел и символов в ЭВМ

1. Представление целых чисел и символов в ЭВМ.

1.1. Структура ячейки памяти.
Наименьшая единица информации — бит (bit — сокращение от английско-го BInary digiT — двоичная цифра). Бит принимает два значения, которые ко-дируются нулем и единицей. Тем самым описываются два уровня сигнала, два состояния элемента и т.д. Если значение бита равно 1, то говорят, что он "уста-новлен", если 0 — то "сброшен".
Ссылаться на каждый бит памяти сложно, поэтому их объединяют в груп-пы и рассматривают это объединение как единое целое. Наименьшей группой бит, к которым можно обращаться, является байт (byte — кусок). Его состав-ляют 8 бит. Биты нумеруют так, как показано на рисунке 1.1: справа налево, начиная с нулевого бита.
7 6 5 4 3 2 1 0

Рис. 1.1.

Части байта имеют свои названия: биты с 0-го по 3-й называют младшим полубайтом, а биты с 4-го по 7-й — старшим полубайтом. Полубайт также на-зывают тетрадой. (Интересные сведения о происхождении терминов бит, байт и т.д. приведены в [Новый словарь хакера / Под ред. Э.С.Реймонда. — М.: Цен-трКом, 1996. — 584 с.].)
Вводят и более крупные единицы. Слово (word) составляют два байта (рис. 1.2).
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0


старший байт младший байт
Рис. 1.2.
Двойное слово (doubleword) составляют два слова, или четыре байта (рис. 1.3).
31 30 29 … 16 15 … 2 1 0
… …

старшее слово младшее слово
Рис. 1.3.

Для байта, слова, двойного слова будем использовать обобщенный термин "ячейка".
Странная на первый взгляд нумерация битов (слева направо, начиная с ну-ля) имеет объяснение. Если в ячейке записано двоичное число, то номер бита k является показателем в весовом коэффициенте bk позиционного представления числа. Пусть, например, в байте установлены 5-й и 2-й бит, а остальные сбро-шены. Это означает, что в нем записано число 1*25 + 1*22 = 32 + 4 = 36 = 24h = 00100100b.
0-й бит ячейки называют также младшим битом. "Самый левый" бит носит название старший бит. Нельзя его называть первым: первым является бит "вто-рой справа".
Для записи содержимого байта требуется две 16-ричные цифры, содержи-мого слова — четыре цифры, содержимого двойного слова — восемь цифр. При этом по 16-ричному представлению слова легко выделить содержимое старшего и младшего байта. Например, в слове записано C7FB. Тогда в стар-шем байте записано C7, а в младшем FB.
Упражнение. В слове записано число 1756318. Какие числа в восьмеричном представлении записаны в старшем и младшем байтах? (Это упражнение убедит вас, что 16-ричное представление удобнее, чем 8-ричное.)
Итак, в ЭВМ для представления любой информации используются цепочки нулей и единиц. В одни и те же цепочки можно вкладывать разный смысл. Мы должны изучить кодирование информации: как, например, записать в память ЭВМ отрицательное число –5, букву "A".

1.2. Представление целых чисел.
Представление целых чисел будем рассматривать на примере гипотетиче-ской ЭВМ, память которой — совокупность четырехбитовых ячеек. Это изба-вит нас от необходимости работать с большим числом разрядов одновременно. ("Нужно изучать задачу, которая заключала бы основную трудность и одновре-менно была бы свободной от второстепенных затруднений."(А.Пуанкаре)) .

3 2 1 0

Рис. 1.4.

В эти 4 бита можно записать 24 = 16 комбинаций нулей и единиц (эти ком-бинации перечислены в таблице 1.1). Будем записывать их так: a = [a3a2a1a0]. Сначала рассмотрим беззнаковые целые числа. Интерпретируем содержимое слова следующим образом:
a = a3*23 + a2*22 + a1*21 + a0 .
Тогда наименьшее представимое число [0000] есть 0, наибольшее число [1111] есть 23 + 22 + 21 + 20 = 15 = 24 – 1.
Однако удобно иметь в распоряжении не только неотрицательные, но и от-рицательные числа. Введем в рассмотрение знаковые целые числа.
Теперь мы должны часть комбинаций четырех нулей и единиц интерпрети-ровать как положительные, а часть как отрицательные числа. Для этой цели могут быть использованы различные способы кодирования: прямой, обратный и дополнительный коды. В настоящее время в подавляющем большинстве ЭВМ используется дополнительный код. Мы не будем проводить сравнения различ-ных систем кодирования, а ограничимся изучением дополнительного кода.
Сначала попытаемся наглядно представить, как он получается. Поделим окружность на 16 частей и перенумеруем все отметки по часовой стрелке четы-рехбитовыми беззнаковыми числами в порядке возрастания. Проставим неот-рицательные числа от 0 до 7 возле соответствующих кодов — и остановимся. Если теперь двигаться в правой части окружности по часовой стрелке от от-метки к отметке — это соответствует увеличению на единицу. Движение в про-тивоположном направлении соответствует вычитанию единицы. Продолжая это движение за нулевую отметку, естественно приписать коду [1111] значение –1, коду [1110] значение –2 и т.д. Так в левой части окружности появляются числа от –1 до –8.

Рис. 1.5.

Итак, мы получили числа в диапазоне [ –8 ; 7] = [–24–1 ; 24–1 – 1].
Обратите внимание: если в третьем (старшем) бите записан 0, то число не-отрицательное, если 1 — отрицательное. Поэтому старший бит называется зна-ковым.
Легко доказать, что a = [a3a2a1a0] в дополнительном коде интерпретируется так: a = – a3*23 + a2*22 + a1*21 + a0 (для доказательства достаточно заметить, что [1000] соответствует –8, а остальные коды получаются последовательным прибавлением единицы).
Определим дополнительный код для общего случая произвольного n-разрядного слова [an–1 an–2... a1 a0]:
a = –an–12n–1 + an–22n–2 + ... + a12 + a0.
Легко убедиться, что код [11...1] соответствует числу –1.
Приведем еще одно определение дополнительного кода

где n — разрядность слова, . Например, код числа –5 вычис-ляется так: .
Именно это определение служит обоснованием названия кода: дополни-тельный (до двух) — twos complement representation.
Полезно знать правило, позволяющее получить код числа –a по коду числа a. Для вывода этого правила достаточно заметить, что
– a = (–1– a) + 1 = ([11...1] – [an–1an–2 ... a0]) + 1 = [ an–1 an–2 ...  a0] + 1 ,
где  a = 1 – a — инвертирование бита a (т.е. бит 0 заменяется битом 1, а бит 1 — битом 0).
П р а в и л о 1. Для получения дополнительного кода числа –а нужно ин-вертировать биты кода а (т.е. получить так называемый обратный код числа а) и прибавить к нему 1.
Пример. Получим дополнительный код –5 ( разрядность n = 4).
5 = [0101] ,  [0101] = [1010] , –5 = 1010 + 1 = [1011].
По кодам, нанесенным на "обод колеса", легко убедиться, что ответ правиль-ный.
Теперь по коду –5 получим код 5: –5 = 1011, 0100 + 1 = 0101 = 5
Сформулируем еще одно правило.
П р а в и л о 2. Для получения дополнительного кода числа –а нужно запи-сать код а. Затем просматривать число справа налево, сохранить все младшие нули и первую встретившуюся единицу. Остальные биты инвертировать.
Задача. Обосновать это правило. Привести примеры.
Нетрудно видеть, что множества беззнаковых и знаковых чисел, предста-вимых описанными способами в четырехбитовой ячейке суть два изоморфных представления кольца вычетов по модулю 24 = 16: . Это сразу гарантирует нам, что код результата сложения двух слов в этом кольце вычетов определяет-ся однозначно по кодам слагаемых и не зависит от выбранного представления. Представление несимметрично: для числа –8 нет положительного «оппонента». Можно было выбрать и другое представление — с диапазоном [–7; 8]. Но тогда было бы неприменимо простое правило: старший бит отрицательного числа установлен.
Подведем итоги. Пусть n — разрядность ячейки. Тогда диапазон представ-ления чисел:
• беззнаковых [ 0; 2n – 1];
• знаковых [ – 2n–1 ; 2n–1 – 1].
Старший бит является знаковым: 1 соответствует отрицательному числу, 0 — неотрицательному.
Полезно запомнить величину диапазонов для нескольких важных частных случаев.

Таблица 1.1.
размер
(биты) размер
(байты) вид диапазон
8 1 беззнаковый [ 0; 255]
знаковый [–128; 127]
16 2 беззнаковый [ 0; 65535]
знаковый [–32768; 32767]
32 4 беззнаковый [0; 232–1]
знаковый [–231; 231–1]

Упражнение. В байте записано число 11001000. Переведите его в 16-ричное и десятичное представление, интерпретируя его как а) знаковое, б) без-знаковое.
Поясним теперь, в чем преимущества дополнительного кода.
1) При сложении дополнительных кодов слагаемых как беззнаковых целых получается дополнительный код суммы (если результат лежит в допустимом диапазоне) xд.к.+ yд.к.= (x+y)д.к. (примеры мы увидим ниже).
2) Число в дополнительном коде можно расширить до произвольного числа разрядов, копируя содержимое знакового бита влево (эта операция носит название "расширение знака"). Пусть, например, в байте записано число 1010 0000 = A0h. Число отрицательное, т.к. знаковый разряд равен 1. Расширим его до слова: 1111 1111 1010 0000 = FFA0h. Нетрудно убедиться, что получи-лось то же самое отрицательное число (какое?).
Упражнение. С каких 16-ричных цифр могут начинаться отрицательные числа, записанные в ячейки памяти ЭВМ?

1.3. Сложение и вычитание целых чисел
Из-за ограниченности диапазона целых чисел при их сложении может по-лучиться результат, который не помещается в ячейку. Такая ситуация называет-ся переполнением (overflow).
Наша гипотетическая четырехразрядная машина оперирует с беззнаковыми числами в диапазоне от 0 до 15 и со знаковыми — от –8 до 7. Для того чтобы фиксировать переполнения, дополним машину ячейкой из двух бит: OF и CF.

OF CF
Рис. 1.6.

Здесь OF — Overflow Flag — флаг переполнения (знакового!), CF — Carry Flag — флаг переноса. Процессор устанавливает эти биты по результату опера-ции. Разберемся, как он это делает.
При выполнении сложения процессор анализирует:
• был ли перенос единицы в знаковый разряд;
• был ли перенос единицы из знакового разряда (он попадает в CF).
После этого определяется переполнение по следующему правилу:
• для беззнаковых чисел: если есть перенос из знакового разряда, то произош-ло переполнение (CF = 1), иначе — переполнения нет (CF = 0).
• для знаковых чисел: если имел место только один из переносов, то про-изошло переполнение (OF = 1), иначе (два или ни одного переноса) пере-полнения нет (OF = 0).
(Для беззнаковых чисел правило очевидно, для знаковых — доказывается пере-бором возможных случаев).
Еще раз напомним, что 1 соответствует ДА, а 0 — НЕТ. (То есть OF = 1 оз-начает, что: "да, знаковое переполнение есть"; 1 кодирует слово ДА).
Рассмотрим три примера:
1)

бит 2  бит 3
CF = 0
OF = 1 беззнаковые: переполнения нет знаковые:
переполнение (11>7) (сложили два положи-тельных числа, полу-чили отрицательное число)
2)

бит 2  бит 3
бит 3  CF
CF = 1
OF = 0 беззнаковые: переполнение
(17 > 15) знаковые:
переполнения нет
3)

бит 3  CF
CF = 1
OF = 1 беззнаковые: переполнение
(21 > 15) знаковые:
переполнение
(–11 < –8)

При сложении знаковых чисел переполнение возникает, когда складывают числа одного знака, а получают результат противоположного знака (как в пер-вом и третьем примерах). Если складывают числа разных знаков, переполнение никогда не возникает.
Вычитание реализовано в процессоре следующим образом: a – b = a + (–b). Процессор вычисляет дополнительный код (–b) и выполняет сложение, напри-мер: 6 – 5 = 6 + (–5) = 0110 + 1011 = 1 0001. Тогда CF = 0 (!), OF = 0.
При сложении появился перенос из знакового разряда. Однако CF = 0, т.к. при вычитании заем (borrow) единицы за пределами ячейки не требуется. Дру-гими словами, выполнение вычитания заменяется в процессоре сложением, но от переноса из знакового разряда берется логическое отрицание и результат этого отрицания помещается в CF. Флаг OF выставляется, как и при сложении: если результат знакового вычитания находится в допустимом диапазоне, то OF = 0, иначе OF = 1.
Задача. Проанализируйте вышеприведенные три примера, заменив сложе-ние вычитанием.

1.4. Кодирование символов
Буквы алфавита, цифры, скобки, запятые и т.д. нужно кодировать цепочка-ми нулей и единиц, так же как и целые числа, как и любую другую информа-цию. Нужно только условиться о том, какому символу какая цепочка соответ-ствует. Тогда, по коду буквы A на экране дисплея будет нарисована картинка с изображением буквы A, принтер напечатает изображение буквы A. Эти изо-бражения берутся из кодовых таблиц (по-английски это кодовые страницы — code page). Международным стандартом кодирования символов стал ASCII (произносится "аски") — American Standard Code for Information Interchange — Американский стандартный код для обмена информацией.
Код символа занимает один байт, т.е. всего можно закодировать 256 сим-волов. ASCII фиксирует только коды от 0 до 127 (0h – 7Fh). Коды 128 – 255 (80h – 0FFh) составляют расширение ASCII.
Изучим таблицу кодов (ее нижнюю половину) подробнее. Сначала объяс-ним, как она построена. Шапка таблицы соответствует единицам, а боковик — десяткам (в 16-ричной системе счисления). Поэтому код буквы z, например, есть 70h + 0Ah = 7Ah.

00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
00 управляющие
10 символы
20 ! " # $ % & ( ) * + , - . /
30 0 1 2 3 4 5 6 7 8 9 : ; < = > ?
40 @ A B C D E F G H I J K L M N O
50 P Q R S T U V W X Y Z [ ] ^ _
60 ` a b c d e f g h i j k l m n o
70 p q r s t u v w x y z { | } ~
Рис. 1.7 .

Символы делятся на два больших класса: изображаемые (символ может быть выведен на экран или напечатан) и управляющие (им соответствуют спе-циальные сигналы и функции устройств).
Изображаемые символы. Эти символы разбиваются на несколько классов.
Прописные латинские буквы. A – 41h, B – 42h, C – 43h,…, Z – 5Ah. Код сле-дующей по алфавиту буквы возрастает на единицу. Это позволяет организовать в программах лексикографическое упорядочение строк: сравниваются коды символов на "больше-меньше". В дальнейшем мы увидим, что такую проверку легко запрограммировать.
Строчные латинские буквы. a – 61h, b – 62h, c – 63h, ... z – 7Ah. Код строч-ной буквы получается прибавлением 20h к коду прописной буквы.
Цифры. 0 – 30h, 1 – 31h, ... , 9 – 39h. Чтобы получить код цифры надо при-бавить к цифре код цифры 0, т.е. 30h. Отметим, что, благодаря такому кодиро-ванию, цепочки цифр можно сортировать, как и цепочки букв. (Сортировка будет осуществляться правильно и для чисел в шестнадцатеричном представле-нии).
Символы пунктуации: ^&#(){} и т.д. Отметим код пробела 20h. Начинаю-щие ошибочно полагают, что пробел кодируется нулем.
Управляющие символы. Эти символы при вводе с клавиатуры или при пе-редаче периферийному устройству вызывают выполнение определенной функ-ции или посылку сигнала. Коды этих символов 0 … 1Fh и FFh. Они имеют спе-циальные обозначения. Приведем таблицу этих обозначений (чисто формаль-но), но прокомментируем лишь немногие из них. В полном объеме управляю-щие символы используются при передаче сообщений по линиям связи.

Таблица 1.2.
Dec Hex Ctrl Имя Назначение
0 00 ^@ NUL null (end string) — пусто (конец строки)
1 01 ^A SOH start of heading — начало заголовка
2 02 ^B STX start of text — начало текста
3 03 ^C ETX end of text — конец текста
4 04 ^D EOT end of transmission — конец передачи
5 05 ^E ENQ enquiry — запрос
6 06 ^F ACK acknowledge — подтверждение
7 07 ^G BEL bell — звонок
8 08 ^H BS backspace — шаг назад
9 09 ^I HT TAB horizontal tab — ТАБ горизонтальная табуляция
10 0A ^J LF line feed — перевод строки
11 0B ^K VT vertical tab — вертикальная табуляция
12 0C ^L FF form feed — перевод страницы
13 0D ^M CR carriage return — возврат каретки
14 0E ^N SO shift out — переключение на стандартный регистр
15 0F ^O SI shift in — переключение на дополнительный регистр
16 10 ^P DLE data line escape — авторегистр 1
17 11 ^Q DC1 device ctrl 1 (X—ON) — управление устройством 1
18 12 ^R DC2 device ctrl 2 — управление устройством 2
19 13 ^S DC3 device ctrl 3 (X—OFF) — управление устройством 3
20 14 ^T DC4 device ctrl 4 — управление устройством 4
21 15 ^U NAK negative acknowledge — отрицательное подтвержде-ние
22 16 ^V SYN synchronous idle — синхронизация
23 17 ^W ETB end transmit block — конец блока передачи
24 18 ^X CAN cancel — снять (отменить)
25 19 ^Y EM end of medium — конец носителя
26 1A ^Z SUB substitute — подстановка
27 1B ^[ ESC escape — авторегистр 2
28 1C ^ FS file separator — разделитель файлов
29 1D ^] GS group separator — разделитель групп
30 1E ^^ RS record separator — разделитель записей
31 1F ^_ US unit separator — разделитель полей

Поясним заголовок этой таблицы: Dec — десятичный код, Hex — шестна-дцатеричный код, Имя — условное наименование сигнала, Назначение — анг-лийское и русское наименование сигнала. Остановимся на столбце Ctrl. Для управляющих символов на клавиатуре терминала клавиш, как правило, нет. Но можно получить управляющий символ, или сигнал, нажимая одновременно клавишу Ctrl и буквенную клавишу, например, нажатие Ctrl+I вызовет переме-щение курсора на следующую позицию табуляции, что эквивалентно нажатию клавиши Tab. Следует заметить, что многие прикладные программы переопре-деляют эти комбинации клавиш для своих нужд, например, в редакторе Word нажатие Ctrl+I вызовет переход к курсивному (italic) шрифту в выделенном фрагменте.
В основном, управляющие символы и сигналы используются в сетях ЭВМ, например, сигнал ACK выдается в качестве подтверждения успешного приема сообщения. Прокомментируем еще некоторые символы.
CR — перемещает каретку, печатающую головку или курсор на экране тер-минала к началу текущей строки. Обычно клавиша Enter вызывает и возврат каретки (CR), и перевод строки (LF).
LF — перемещает каретку, печатающую головку или курсор вниз на одну строку.
FF — перемещает каретку, печатающую головку или курсор к началу сле-дующей страницы.
BEL — активизирует звонок, гудок или другой звуковой сигнал на том уст-ройстве, на которое он был послан.

1.5. Расширение ASCII
Коды 128–255 могут быть определены по-разному.
Для различных языков используются разные кодовые таблицы. Коды 0–7F в них одинаковы. Это ASCII. Верхняя часть таблицы зависит от языка. Полная таблица кодов носит название кодовой страницы (code page, сокращенно — cp).
Нас, разумеется, интересует, как кодируются русские буквы (кириллица).
Для MS DOS используется кодировка cp866. Помимо кириллицы и симво-лов для рисования таблиц в текстовом режиме (псевдографика), сюда входят некоторые математические знаки.
Таблица 1.3.

Между кодами букв "п" и "р" имеется разрыв, хотя это и не препятствует, например, корректной сортировке. Хуже, что буква ё", введенная в русский алфавит Н.М.Карамзиным, оказалась вне привычного алфавитного расположе-ния.
В операционной системе Windows используется другая кодировка кирилли-цы: cp1251. В кодировку для Windows не входят символы псевдографики. В системе с графической оболочкой они просто не нужны. Здесь буквы русского алфавита располагаются без разрывов, но буквы Ё и ё по-прежнему "на отши-бе".
Для некоторых восточных языков используется так называемая многобайт-ная кодировка (MBCS — Multi-byte Character Set). В этом наборе символ может быть представлен одним или двумя байтами. Если первый байт заключен в оп-ределенном диапазоне, то это означает, что следующий байт надо рассматри-вать совместно с ним для кодирования одного символа. Такую кодировку ино-гда называют двухбайтовой (DBCS — Double-byte Character Set), хотя это и не-верно, ведь это смесь одно- и двухбайтовых символов. Такая кодировка не-удобна, т.к. по количеству байтов, занимаемых текстом, нельзя сразу сказать, сколько символов содержит текст.
Конечно, лучше было бы иметь коды для всех распространенных языков в одной таблице. Для этого введена двухбайтовая кодировка каждого символа Unicode. Здесь возможное количество комбинаций 65536. Сюда записаны и китайские, японские и корейские иероглифы, арабская вязь, изображения шах-матных фигур, … Начальные 127 кодов — это ASCII.
Приведем сводную таблицу кодов для кириллицы (табл. 1.4). Промежуточ-ные коды легко вычислить.

Таблица 1.4.
cp 866 cp 1251 Unicode
А 80h А C0h А 410h
Я 9Fh Я DFh Я 42Fh
а A0h а E0h а 430h
п AFh
р E0h
я EFh я FFh я 44Fh
Ё F0h Ё A8h Ё 401h
ё F1h ё B8h ё 451h

Заметим еще, что кодировка для MS DOS именуется также кодировкой OEM (Original Equipment Manufacturer), а кодировка для Windows — кодировка ANSI.
Освоим полезный способ получения символа по его коду. Нажмите и удерживайте клавишу Alt. Наберите на малой цифровой клавиатуре (не на ос-новной клавиатуре!) десятичный код символа. Отпустите клавишу Alt. На экра-не появится изображение символа.

Задание A1.
1. Вручную преобразовать десятичное число в 16-ричную и двоичную сис-темы счисления (пример: 4020).
2. В байте записано число. Перевести его в десятичную систему счисления, рассматривая как беззнаковое и как знаковое. Какому символу кодовой табли-цы соответствует число? Ответ — с обоснованием — должен быть представлен в виде таблицы
Беззнаковое Знаковое Символ
54h
D6h