Представление чисел при обработке в компьютере

Любая компьютерная программа оперирует определенными элементами (константами, числовыми или символьными переменными, массивами и т.д.), которые принято называть данными. Человек, оперируя какими-то данными, способен быстро разобраться в них и в тех операциях, которые допустимы для определенных данных. Он не будет извлекать корень квадратный из слова и не запишет число с заглавной буквы. Быстро разобраться ему в этом позволяет отличие в записи разных типов данных. Компьютер же любые данные воспринимает как последовательность двоичных чисел. Поэтому ему необходимо указывать тип данных, обрабатываемых программой. Для этого элементы программы описывают, то есть указывают их тип либо в начале программы, либо перед их обработкой.

Любой тип данных определяет две важные для транслятора (компилятора или интерпретатора) вещи:

• объем памяти, выделяемый для размещения элемента программы;

• набор допустимых действий с элементами данного типа.

Существует несколько типов данных: числовые, логические, символьные или строковые и т.д. Мы будем рассматривать только числовые данные. Код каждого символа, в том числе и любой десятичной цифры, в памяти занимает один байт, а в Unicode – два байта. Если каждую цифру числа представлять в виде кода, то для записи, например, числа 2813694570 потребовалось бы 10 или 20 байт памяти. Для обработки сравнительно небольшого массива размером 1000 x 1000 таких чисел памяти уже нужно было бы до 20 Мбайт. Это большая трата памяти. Поэтому транслятор записывает числа по-другому – в виде разных форматов, в которых для представления числа используется определенное количество байт, определяемых данным форматом.

Совокупность разрядов (бит), отводимая для представления числа определенного формата, образует разрядную сетку компьютера.

Различают две формы представления чисел:

- естественную (с фиксированной запятой);

- экспоненциальную (с плавающей запятой).

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

Машинное представление целых чисел. Обычно для представления целых чисел используют один, два или четыре байта. Существуют две формы представления: беззнаковая и со знаком. Например, в языке програм-мирования Turbo Pascal 7.0 из пяти целочисленных типов два имеют беззнаковую форму, три – со знаком. В таблице ниже представлены все пять указанных форматов.

Тип	Диапазон чисел	Формат
ShortInt	-128 (-27). . .127 (27-1)	1 байт со знаком
Integer	-32768 (-215). . .32767 (215-1)	2 байта со знаком
LongInt	-231 . . . 231-1	4 байта со знаком
Byte	0 . . . 255 (28-1)	1 байт без знака
Word	0 . . . 65535 (216-1)	2 байта без знака

Разнообразие типов позволяет экономно расходовать память при разработке программ.

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

При представлении чисел со знаком под знак отводится старший (левый) бит разрядной сетки. Остальные разряды отводятся под само число. Для положительных чисел знаковый бит содержит 0, а для отрицательных – 1.

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

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

В связи с этим отрицательные числа представляют в компьютерах в обратном или дополнительном кодах. Для получения обратного кода число следует инвертировать (заменить 1 на 0, а 0 – на 1) за исключением знакового разряда. В обратном коде, как и в прямом, ноль имеет также два представления.

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

В дополнительном коде представление положительного нуля совпадает с прямым кодом. В разрядной сетке длиной 1 байт положительный нуль будет таким: 0 0 0 0 0 0 0 0. Для получения дополнительного кода отрицательного нуля следует к его обратному коду добавить единицу в младший разряд:

1 1 1 1 1 1 1 1 Полученная единица выходит за разрядную сетку и

+ 1 теряется. Таким образом, нуль в дополнительном коде

1 0 0 0 0 0 0 0 0 имеет единственное представление.

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

-2⁷+2⁶+2⁵+2⁴+2²+2⁰ = -128+64+32+16+4+1= -128+117= -11

Отсюда следует, что в разрядах с нулевого по шестой записанное число 117 является дополнением модуля числа -11 до переполнения разрядной сетки, то есть до числа 128. Поэтому код и называется дополнительным.

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

Покажем это на примерах.

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

При положительном результате: 34 – 19 = 15.

В прямом коде: В обратном коде: В дополнительном коде:

0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0

– 0 0 0 1 0 0 1 1 + 1 1 1 0 1 1 0 0 + 1 1 1 0 1 1 0 1

0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 1 1 1

+ 1

0 0 0 0 1 1 1 1

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

Пусть результат будет отрицательным: 19 – 34 = - 15.

В прямом коде операция не реализуема.

В обратном коде: В дополнительном коде:

0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1

+ 1 1 0 1 1 1 0 1 + 1 1 0 1 1 1 1 0

1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1

- 1

1 1 1 1 0 0 0 0

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

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

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

Машинное представление вещественных чисел. Для изображения вещественных чисел, а также очень маленьких и очень больших целых чисел используется экспоненциальная форма представления, например, 0,478·10⁵; -23·10^-1. Записывается это следующим образом: 0,478Е+05; 23Е-01, где символ Е читается как "умножить на десять в степени". При такой записи: 478·10² = 47,8·10³ = 4,48·10⁴ = 0,478·10⁵ число не изменяется по величине, а запятая в числе как бы плавает из одной позиции в другую. Для однозначности представления чисел, а также с целью минимизации погрешности при вычислениях и эффективного использования памяти в компьютерах к таким числам применяют процедуру нормализации справа. Число называют нормализованным справа, если целая часть числа равна нулю, а после запятой в мантиссе стоит не нуль. Нормализованная форма представления числа имеет следующий вид: А = ± m·q^p, где m –мантисса числа, равная q^-1 ≤ │m│<1, q- основание системы счисления, p- порядок числа.

При q = 10 0.1 ≤ │m│<1. При q = 2 0.5 ≤ │m│<1.

В языке программирования Turbo Pascal 7.0 существует пять стандартных типов для вещественных чисел, приведенных в таблице:

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

Для примера рассмотрим схему представления чисел для переменных типа Real. Переменная такого типа занимает в оперативной памяти 6 байт, или 48 разрядов.

Они распределены следующим образом:

m (39 разрядов)

p + t (8 разрядов)

47 . . . . . . 8 7 . . . . . . 0 разряды

Любое число Х типа Real в двоичной форме имеет следующий нормализованный вид:

Х= ± 0.1· m · 2^p, 0 ≤ m < 2³⁹, - 128 ≤ p ≤ 127.

Величина мантиссы равна 0.1· m, так как после запятой всегда стоит единица. В записи числа она не участвует, но учитывается при выполнении арифметических операций.

Величина t = 128 – это смещение порядка p. Оно введено для получения положительного порядка при любых числах. При записи числа с минимально возможным порядком, равным -128, все разряды, отводимые под порядок, будут содержать нули: - 128 + 128 = 0. Для числа с максимально допустимым порядком, равным 127, будет p + t =127 + 128 =255, то есть все разряды содержат единицы. Таким образом, порядок для переменных Real всегда представляется положительным беззнаковым числом.

В разрядной сетке на месте мантиссы размещается ее модуль, а знак ее, как и знак всего числа, определяется значением 47-го разряда: 0 для положительных чисел и 1 – для отрицательных чисел.

Минимальное значение мантиссы равно: 0.1₂. При этом все 39 разрядов, отведенных под мантиссу, содержат нули. Максимальное же значение мантиссы равно: 0.1 1. . . 1 = 2^-1 + 2^-2 +. . . + 2^-40 =1 – 2^-40.

39

Машинным нулем для переменной типа Real называется неотрицательное число, равное: 0.1₂ · 2^-128. При его записи все 48 разрядов содержат нули.

При представлении порядка со смещением (p + t) упрощается операция сравнения произвольного числа с нулем, которая реализована аппаратно и выполняется в программах довольно часто. Однако положительный нуль (+0) и отрицательный нуль (-0) оказываются различными. У отрицательного нуля в старшем 47 разряде записана 1, а в остальных нули. Поэтому при программировании сравнивать на точное равенство вещественные числа в большинстве случаев некорректно. Вместо Х – У = 0, следует писать │Х - У│<, где – достаточно малое число, соответствующее погрешности вычислений.

Максимально представимое число типа Real равно:

(1 – 2^-40) · 2¹²⁷ ≈ 2¹²⁷ = 2^{(10· 12.7)} =1024^12.7 ≈ 10^{(3· 12.7)} = 10^38.1.

Минимально представимое число равно:

0.1· 2^-128 = 1· 2^-129 = 2^{(-10 · 12.9)} =1024^-12.9 ≈ 10^{(-3 · 12.9)} =10^-38.7.

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

С = А + В = 0.397621· 10³ + 0.237912 · 10¹

Порядок второго слагаемого выравнивается до большего: 0.237912 · 10¹ = 0.002379 · 10³

С = А + В = (0.397621 + 0.002379) · 10³ = 0.4 · 10³ =400

С = А – В = 0.645623 · 10^-2 – 0.254811 · 10²

0.645623 · 10^-2 = 0.0000645623 · 10² ≈ 0.000065 · 10²

С = А – В = (0.000065 – 0.254811) · 10² = – 0.254746 · 10² = 25.4746

В двоичной системе счисления модуль мантиссы вычитаемого равен:111110001101011011, а модуль мантиссы уменьшаемого равен: 000000000001000001. Эта мантисса по модулю меньше мантиссы вычитаемого, поэтому ее представим в обратном коде: 111111111110111110 и сложим мантиссы: 111110001101011011

 111111111110111110

1

1

111110001100011010 = 254746 результат получается на месте мантиссы, поэтому он равен: 0,254746. Присвоим знак (–) большей по модулю мантиссы и добавим общий порядок: -25.4746.

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

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

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

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

При работе с вещественными числами следует учитывать следующие особенности:

1. Ошибки округления возникают уже на этапе записи чисел в компьютер. При выполнении арифметических операций они возрастают. Рассмотрим для простоты действий примеры в десятичной системе счисления: пусть под мантиссы отведено 5 разрядов Х = 0.87654 · 10¹; У = 0.94567 · 10². После выравнивания порядка до большего получим Х = 0.08765 · 10². Последнюю цифру 4 потеряли. Далее просуммируем мантиссы: 0.08765

+ 0.94567

1.03332

Получили мантиссу больше 1, поэтому произойдет нормализация ее вправо, то есть у результата порядок возрастет на единицу при сдвиге вправо, а последняя цифра 2 пропадет: 0.10333 · 10³. Итого потеряли две последние цифры 2 и 4.

2. Добавление или вычитание малого числа может не сказаться на результате. Пример: Х = 0.32165 · 10³; У = 0.48434 · 10^-3. После выравнивания порядков: У = 0.00000048434 · 10³. Так как под мантиссу у нас отведено 5 разрядов, то при сложении мантисс у второго слагаемого последние значащие цифры пропадут и результат будет равен первому слагаемому.

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

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

Изначальной причиной возникновения погрешностей обработки чисел является ограниченность разрядной сетки.

У целых чисел появляется понятие максимального числа, хотя на числа ограничений в принципе нет.

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

• строгие отношения между числами превращаются в нестрогие для их компьютерных кодов;

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

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

Лекция 9