2.5. Арифметические и логические основы программирования

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

Рассмотрим такую странную автобиографию: «Я окончил университет 44 лет отроду, спустя год 100-летним молодым человеком я познакомился с 34-летней девушкой. Незначительная разница в возрасте – всего 11 лет – способствовала тому, что мы жили душа в душу…»

Странность чисел в этой биографии из-за того, что все они указаны не в десятичной, как привычно, а в пятеричной системе счисления. Разгадка во фразе «спустя год». После 44 идет 100, т.е. 4 – это максимальная цифра и требует обнуления младших разрядов и появления 1 в новом разряде, аналогично тому, как в десятичной 9+1 – вызывает появление 1 в новом разряде, т.е. получается 10.

Система счисления – это совокупность приемов и правил для записи чисел знаками. Наиболее известна десятичная система, где используют цифры от 0 до 9. Способов записи чисел бесконечно. Но любая система должна

1) представлять любое число;

2) при этом единственным образом;

3) обеспечить простоту оперирования числами.

Системы делят на позиционные и непозиционные. Способ записи можно представить как

, (1)

где А – число; D_i – символ системы.

Такая запись отражает число в непозиционной системе.

Непозиционная система – это система, для которой значение символа не зависит от его положения в числе и принцип образования числа через операции сложения или вычитания. Примером такой системы может служить римская система (I, V, X, L, C, D, M и т.д.).

Если формулу записать как

, (2)

где в_i=qⁱ, то В_i=qВ_i-1, q – называют основанием системы счисления.

Позиционные системы – это системы, удовлетворяющие равенству (2). В таких системах значение цифры определяется местом в числе.

Например, в десятичной системе число 222:

2 на первом месте – это сотни;

2 на втором месте – это десятки;

2 на третьем месте – это единицы.

Длина числа или длина разрядной сетки – это количество позиций в записи числа (3).

Для различных систем счисления характерна разная длина.

Например, 96₍₁₀₎ – это 140₍₈₎, или 10120₍₃₎, или 1100000₍₂₎. (Цифра в скобках обозначает основание системы счисления.)

Для длины N можно задать диапазон представления (ДП) чисел в заданной системе счисления как

. \ (3)

В ЭВМ используется двоичная система счисления, правила которой просты, но требуют перевода результата в приемлемый вид (десятичный).

Для систем счисления с основанием больше 10 для обозначения разрядов вводят буквы. Например, 16-ричная система имеет в своем составе следующие разряды: 1 2 3 4 5 6 7 8 9 А В С D E F.

Принято обозначать числа из 16-ричной системы, добавляя букву Н, двоичные – В. Например, 10С0Н, 00011В.

Двоичная арифметика

Двоичная система счисления – это система, в которой используются только знаки 0 и 1. Исследования в этой системе начались в XIV веке. Основное достоинство – это удобство и простота. (Удобство реализации в машине: ток есть или нет, намагничен или нет участок и т.д.)

Рассмотрим, как реализуются четыре основные арифметические операции в такой системе.

Сложение. Используем следующую таблицу для сложения двоичных чисел Х и Y.

X Y S 1 Факт переноса 1 в более старший разряд 0 0 1 1 0 1 0 1 0 1 1 0

Пример: 5 + 11 = 16.

Вычитание. Используем таблицу для вычитания двоичных чисел X и Y.

Факт заёма 1 из старшего разряда X Y S 1 0 0 1 1 0 1 0 1 0 1 1 0

Реально в машине вычитание заменяется сложением чисел согласно формуле: А–В=А+(–В). Величина В представляется в дополнительном коде.

Умножение. Умножение реализуется с помощью двух операций: сложения и сдвига. Произведение получается суммированием частичных сумм и сдвигом. Сдвиг можно производить влево и вправо. Соответственно множитель анализируется, начиная с младшего или старшего разряда. Если в текущем разряде множителя 1, суммирование производит, если 0 – не производят.

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

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

Пример: 35:7=5

Методы перевода чисел из одной системы счисления в другую. Трудно ли изображать число в других системах счисления? Нисколько. Согласно (2) число отображается как

, (4)

следовательно, достаточно определить новые коэффициенты b (вместо а) в системе с основанием q₂ (вместо q₁). Процесс получения новых коэффициентов заключается в последовательном делении числа на основание q₂ х раз, пока частное не станет меньше делителя.

Например, представить число 98 в десятичной системе счисления в двоичной системе.

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

1100010₍₂₎=0·2⁰+1·2¹+0·2²+0·2³+0·2⁴+1·2⁵+1·2⁶=98₍₁₀₎.

Теперь, зная метод перевода, можно восстановить автобиографию как:

«Я окончил университет 24 лет отроду, спустя год 25-летним молодым человеком я познакомился с 19-летней девушкой. Незначительная разница в возрасте – всего 6 лет – способствовала тому, что мы жили душа в душу…»

Способы перевода дробей. Дробное число можно представить как

(5)

в новой системе оно будет как 0, в_-1в_-2…в_-k. Т.е. требуется поочередное умножение данной дроби на другое основание системы счисления с выделением целой части.

Пример: Представить десятичную дробь 0,453 в 5-ричной системе счисления с точностью 5^-4.

0,453=4·10^-1+5·10^-2+3·10^-3

0 ,453·5= 2,265

0,265·5= 1,325

0,325·5= 1,625

0,625·5= 3,125

выбираем целые. Ответ 0,2113.

Проверка: 0,2113=2·5^-1+1·5^-2+1·5^-3+3·5^-4.

Пример: Представить десятичную дробь 0,625 в двоичной системе счисления.

Перевести дробь 0,1101 из двоичной системы счисления в десятичную.

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

Используя вышеописанные алгоритмы перевода дробных чисел в заданную систему счисления, рассмотрим пример с 16-ричной системой, допустим требуется число FA0 преобразовать в десятичную систему:

FA0=0·16⁰+10·16¹+15·16²=4000.

Для перевода из 16-ричной в двоичную специальных процедур не требуется, поскольку одна 16-ричная цифра соответствует четырем двоичным разрядам:

Аналогично просто преобразование между 8-ричной и двоичной системами, с той разницей, что вместо тетрады (4^хразрядов) здесь используют триаду (3 разряда).

Формы представления информации

Представление дробных величин. Число 0.028 можно записать как 28·10^-3 или 0,03 или 2.8·10^-2 и т.д. Во избежание путаницы ЭВМ оперирует специальными формами представления чисел. Машинное изображение числа – это представление чисел в разрядной сетке машины.

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

Если только правильные дроби, т.е. такие, которые в диапазоне от –1 до 1, то хранят только часть после запятой, в самом левом разделе хранят знак.

Целые числа хранят подобным образом, диапазон представления чисел от –(2^п–1)' до (2^п–1). Числа с целой и дробной частью при хранении уравнивают.

Например, рассмотрим, как хранят два числа А1= -1011, 0111110; А2= 0,110001101

Числа представляют в виде А1= -0,10110111110·24, А2= 0,0000110001101·24

В памяти ЭВМ эти данные будут представлены в виде:

А1

1

1

0

1

1

0

1

1

1

1

1

0

А2

0

0

0

0

0

1

1

0

0

0

1

1

0

1

погрешность

Если в машине под хранение данных предусмотрено только 12 разрядов, такое представление может привести к погрешности. Возможны случаи когда произойдет переполнение.

Например:

В современных ЭВМ дробные величины хранятся по-другому.

Формат представления с плавающей запятой. Число представляется в виде

А=m·p, (6)

где m – мантисса; p – порядок (или характеристика).

На m накладывается ограничение вида:

, (7)

где q – основание системы счисления.

Мантисса, удовлетворяющая неравенству (7), называется нормализованной. Формат машинного представления следующий:

Например, А1= –10110,1111; А2= 0,000110010111

приводят к виду А1= –0,101101111·2+5; А2= 0,110010111·2–3.

Теперь в 12 разрядах числа помещаются без погрешности:

m p

А1

1

1

0

1

1

0

1

1

1

1

0

0

0

1

0

1

А2

0

1

1

0

0

1

0

1

1

1

1

0

0

0

1

1

Представление данных сопроцессора. Наряду с основным микропроцессором в архитектуре применяют специально разработанный процессор для эффективного выполнения арифметических операций. Сопроцессор может обрабатывать семь типов данных, слово (16 разрядов), короткое целое (32 разряда), длинное целое (64 разряда) (все они со знаком и без), упакованное ВСD (см. дальше), короткое вещественное, временное вещественное. С целью экономии разряда знака порядка используют смещенный порядок. Числовую ось искусственно перемещают в отрицательную область на 127, т.е. реальные значения (отрицательные и положительные) хранят с положительным порядком.

Например, в формате короткого целого 32 разряда хранят следующим образом:

0	01100101	01011000	0
Разряд знака	порядок	мантисса	Номер разряда

Истинный порядок определяется как разница Р – 127, т.е.

01100101 – 01111111= –00011010₍₂₎= –26₍₁₀₎.

Реально хранится число 1.01011000…0·2^–26

22 разряда

Представление целых чисел. В общем случае под целое число можно отвести любое число соседних байтов, но система команд микропроцессора поддерживает работу с числами размером 8, 16, 32 байт.

Различают числа со знаком и без знака. Диапазон чисел без знака больше. Например, 1 байт может хранить либо числа от 0 до 256, либо числа от – 127 до 128.

16- и 32-разрядные числа хранятся в памяти в перевернутом виде: левые во – втором, правые – в первом байте. Например, 98₍₁₀₎=0062₍₁₆₎ в памяти размещается как

А+1

62

00

где А – адрес числа.

Появилось такое изображение в наследство от 8-разрядных микропроцессоров, где операции начинались с младших разрядов (операции с 16 и более разрядными числами). Поэтому они и считывались по первому адресу. Но во внутренних регистрах процессора числа хранятся нормально.

Целые со знаком записываются в дополнительном коде, т.е. как беззнаковое

где к – количество разрядов, отведенных под число.

Например: +98_доп=98₍₁₀₎=0062₍₁₆₎;

–98_доп=2¹⁶–98=FF9E₍₁₆₎.

Двоично-кодированное десятичное представление. Такое представление называют BCD-формат, т.е. десятичные цифры хранятся в виде четырех двоичных разрядов (похоже на преобразование чисел из 16-ричной в двоичную). Используются комбинации от 0000 до 1001.

Например:

	1986(10)		=		0001		1001		1000		0110
					1		9		8		6

Операции над такими числами требуют коррекции при получении числа больше 9.

Отрицательные BCD-числа представляются в дополнительном коде. Простое правило поручения дополнительного кода состоит в замене всех цифр на дополнение до 9 и увеличении на 1 младшего ряда.

Пример.

0561(10)	=	0000		0100		0110		0001(BCD)
допол. до 9-----
		1001 9		0100 4		0011 3		1001 9

Бывают упакованные и неупакованные форматы BCD. В неупакованном под 1 цифру (4 разряда двоичных) отводят 1 байт, в упакованном 1 байт хранит 2 цифры. Знак – это еще 1 байт: 00000000 – положительные; 10000000 – отрицательное.

Имеющиеся в процессоре команды позволяют выполнять арифметические операции только над однозначными числами BCD.

Представление символов и строк символов. Как и другие, символьные данные хранятся в двоичном виде. Для этого каждому символу ставится в соответствие некоторое число, которое называется кодом.

Например, буква латинского алфавита А имеет код 65. Системой кодов называют набор соответствий кодов символам, используемый компьютером для представления этих символов в текстовых данных.

Существует несколько систем кодов, используемых в разных операционных системах. Например, Windows версии для Северной Америки и Западной Европы использует код 176 для представления знака градуса (^о), тогда как Windows другой языковой версии может использовать этот код для другого символа. Тем более различаются системы кодов в операционных системах разных компьютерных платформ. Знак градуса в системе Macintosh имеет код 161.

Большинство программ DOS используют расширенную систему кодов ASCII для представления символов. В среде Windows используется ANSI-стандарт. Одним из следствий существования нескольких наборов символов является необходимость перекодировки данных при переносе их с одной вычислительной платформы на другую. В большинстве кодировок часть символов представлена одинаковыми числами, например, символ английской буквы А имеет один и тот же код 65 в средах Windows, UNIX и Maсintosh. Начиная со 126 символа, размещаются символы различных языков.

Системы кодировки ASCII (American Standarts Code for Information Interchange) и ANSI (American National Standarts Institute) используют для кодировки символов 1 байт, байтом можно представить 256 символов.

Стандартная ASCII не содержит кодов русских букв. В нашей стране используют варианты этой системы, которые имеют коды русских букв (основная и альтернативная таблицы).

Особенности систем кодирования:

1. Код пробела меньше кода любой буквы, цифры, графически представимого.

2. Коды цифр упорядочены по возрастанию и идут без пропусков, код 0 – это не цифра 0.

3. Коды больших и малых латинских букв упорядочены по алфавиту и тоже без пропусков.

4. В альтернативной кодировке коды русских букв упорядочены по алфавиту. Большие – без пропусков, малые между n и p имеют пропуск. В основной в малых нет пропуска.

Первые 32 кода от ОН до 1 FH в ASCII являются управляющими, они служат для представления специальных символов. Другие (до 7 FH) кодируют латинские буквы, знаки пунктуации, цифры, операции арифметики.

Вторая половина от 80Н до OFFH – это расширение ASCII, в разных моделях ПЭВМ используются по-разному. Именно эти коды кодируют русские буквы.

Машинное представление строк – это нужное число соседних байтов памяти, в которые записывают коды символов, образующих строку. Эта последовательность заносится не в перевернутом, а в прямом виде.

В реальных программах BCD-числа редко выписываются явно. Они обычно получаются из ASCII-чисел ­ из строк, т.е. чисел в виде строки (например, '256') и в конце снова преобразуются в такие строки. Эти преобразования реализуются просто: коды '0' – '9' имеют 16-ричное представление – 30Н – 39Н, в двоичном соответственно 0011 0000 В ­ 0011 1001 В. Для получения цифр 0 – 9 достаточно выделить 4 бита справа: 0000 - 1001. А для обратного преобразования требуется логически сложить число и 0011 0000 В.

ASCII-кодировку еще называют ОЕМ-кодировка. Существует преобразование кодов ОЕМ–ANSI, и наоборот.

8-разрядные символы много лет были стандартом всех Intel-базированных компьютеров. Однако проблема с ними состоит в том, что они представляют только 256 возможных символов, которых и близко недостаточно для национальных языков или математических и других символов.

Появился новый стандарт UNICODE, который имеет 64 Кб возможных символов, т.е. символы 16-разрядные и называются WideCode. Теперь требуется преобразование из 8-разрядных в 16-разрядные.

Представление логических величин. Логическая величина может принимать только два значения: истина и ложь, следовательно, для ее хранения требуется 1 бит. В языках программирования логические величины могут храниться по-другому. Например, в Delphi можно различить Boolean, LongBoolean, которые хранятся соответственно в байте, двух байтах.

Представление дат и времени. Время, дату можно представлять в машине по-разному. Первоначально языки программирования вообще не предусматривали хранение и обработку дат. Современные языки, СУБД представляют дату или в формате с плавающей запятой, где целая часть дает значение даты, а время – это дробная часть, или в виде строки символов. Например, '01.01.1996' и время как '03:03:06'.