Двоичная арифметика. Арифметические операции в позиционных системах счисления.

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

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

§ Беззнаковые целые числа —Хотя в математических задачах не так часто встречаются величины, не имеющие отрицательных значений, беззнаковые типы данных получили в компьютерах достаточно большое распространение. Возможно, главная причина этого состоит в том, что в самой машине и программах для нее имеется много подобного рода объектов, таких как, адреса ячеек, всевозможные счетчики (количество повторений циклов, число параметров в списке или символов в тексте и т.п.). К этому списку следует также добавить числа, обозначающие дату и время, размеры графических изображений в пикселях. Всё перечисленное выше всегда и во всех программах принимает только целые и неотрицательные значения.

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

Пример: число 14 будет в восьмиразрядной записи имеет следующий вид 00001110, а в шестнадцатиразрядном представлении 0000000000001110.

Зная разрядность Nпредставления можно легко определить минимальное и максимальное значение чисел для N-разрядного беззнакового целого: минимальное состоит из одних нулей, а значит, при любом N равняется нулю; максимальное, напротив, образовано одними единицами и, разумеется, для разных N различно. Для вычисления максимально допустимого значения беззнакового целого A _Max(N)при известном чисое разрядов для его записи обычно используют формулу

A _Max(N)=2^N–1

§ Целые числа со знаком — Добавление отрицательных значений приводит к появлению некоторых новых свойств. Ровно половина из всех 2^N чисел теперь будут отрицательными; учитывая необходимость нулевого значения, положительных будет на единицу меньше, т.е. допустимый диапазон значений оказывается принципиально несимметричным.

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

Примечание.

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

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

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

Примечание.

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

Суть метода в следующем. Все отрицательные числа записываются в ЭВМ в виде:

2^N – |m|

где N — количество двоичных разрядов, а m — конкретное значение отрицательного числа.

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

§ Модуль |m|отрицательногоm числа переводится в двоичную форму;

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

§ К полученному обратному коду обычным образом прибавляем единицу.

Пример: пусть 00001000 есть исходное число
		— обратный код числа
		— добавляемая единица
		—дополнительного код числа

Примечание.

Хотя дополнительный код гораздо менее наглядный, чем прямой, он позволяет значительно проще реализовать арифметические операции. Более того, наличие дополнительного кода позволяет упразднить действие вычитания, сводя его к сложению с дополнительным кодом вычитаемого. Этот метод вычитания будет писан ниже (см. пп. 3.4.6).

Завершить изложение данной части вопроса хочется цитатой из книги известного российского специалиста по разработке ЭВМ Н.П.Бруснецова [7]⁾:

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

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

Примечание.

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

Известны два способа представления вещественных чисел: с фиксированной и с плавающей запятой [8]⁾. Первый способ считается устаревшим и он в настоящее время не используется.

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

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

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

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

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

A=(±M) · Q ^±P ,

где M — мантисса, а показатель степени P — порядок числа.

Примечание.

Для десятичной системы это выглядит очень привычно, например: заряд электрона равен -1,6·10^-19 к, а скорость света в вакууме составляет 3*10⁸ м/сек. Некоторое неудобство при этом вносит тот факт, что представление числа с плавающей запятой не является единственным, например, 3·10⁸ =30·10⁷=0,3·10⁹=0,03·10¹⁰ = ...

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

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

Пример: Тогда из всех записей 3·10⁸ =30·10⁷=0,3·10⁹=0,03·10¹⁰ = ... для числа 300 000 000справедлива только одна форма — 0,3·10⁹.

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

Примечание.

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

Все сказанное о нормализации можно легко применить и к двоичной системе:

A=(± M) · 2 ^±P, причем ½ ≤ M <1.

Пример: –3₁₀ = –0,11·2¹⁰, где M = 0,11 и P = 10(записи M и P в двоичном коде).

Примечание.

Характерно, что двоичная мантисса всегда начинается с единицы (M ≥ ½ ). Поэтому во многих ЭВМ эта единица не записывается в оперативную память, что позволяет сохранить еще один дополнительный разряд мантиссы (это так называемая скрытая единица).

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

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

В частности, для IBM PC, мантисса хранится в прямом коде, а для хранения порядка используется так называемыйсдвиг: к значению порядка прибавляется некоторая константа. В результате все значения порядка становятся положительными беззнаковыми числами, что заметно упрощает «…операцию сравнения произвольного числа с нулем, которая выполняется аппаратно довольно часто» [9]⁾.

Рассмотрим далее правила выполнения арифметических операций над числами в двоичной системе счисления с фиксированной запятой [10]⁾.

Примечание.

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

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

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

Правило. Сложение двоичных чисел осуществляется вычислением суммы значений одноименных разрядов и единицы переноса из предыдущего разряда, если она есть. Перенос производится, если эта сумма не меньше, чем основание системы счисления, т.е. число 2₁₀.

Таким образом, для одноразрядных двоичных чисел имеем:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 10 (0 и единица переноса в следующий старший разряд)

Сравним десятичное и двоичное сложение

Пример:	Десятичная арифметика	Двоичная арифметика
Слагаемое			0 1 1 0 0 0 1 1
Слагаемое			0 1 0 1 0 1 1 0
Перенос (единицы)			1 0 0 0 1 1 0
Сумма			1 0 1 1 1 0 0 1

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

Пример: сложим 9₁₀ и 3₁₀, заданные двоичным кодом

0011

1100₂ = 12₁₀

Двоичное вычитание.

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

Вычитание двоичных чисел производится поразрядно по следующим правилам:

0 – 0 = 0

10 – 1 = 1

1 – 0 = 1

1 – 1 = 0

Выполняя вычитание из нуля единицы, следует занять единицу из старшего значащего разряда:

Сравнение процедур десятичного и двоичного вычитания можно продемонстрировать следующим образом:

Пример:	Десятичная арифметика	Двоичная арифметика
Заем (единица)					0 0 1 1 0 0 0 0
Уменьшаемое					0 1 1 0 1 1 0 1
Вычитаемое					0 0 1 1 0 0 0 1
Разность					0 0 1 1 1 1 0 0

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

Двоичное умножение.

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

Двоичное умножение следует производить в соответствии со следующими правилами:

0 ´ 0 = 0

0 ´ 1 = 0

1 ´ 0 = 0

1 ´ 1 = 1

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

А).Формирование первого частного произведения. Если значение младшего значащего разряда множителя равно 0, то и результат равен 0, если значение этого разряда равно 1, то результат является копией множимого.

Б).Правило сдвига. При использовании очередного разряда множителя для формирования частного произведения производится сдвиг множимого на один разряд (позицию) влево.

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

Г).Определение результирующего произведения. Искомое произведение есть результат выполнения всех операций сдвига и сложения.

Пример:	Десятичная арифметика	Двоичная арифметика
Множитель
Множитель
1-е частное произведение
2-е частное произведение
3-е частное произведение
Произведение

Двоичное деление.

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

Пример:	Десятичная арифметика	Двоичная арифметика
Делимое
Делитель	(1) 17		(1) 110
1-е частная разность
	(2) 34		(0) 0000
2-е частная разность
	(1) 17		(1) 110
3-е частная разность