Таблица 12.1. Преобразование десятичных чисел в числа про основанию -2

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

от-(2°"-2)/з до(2-1)/з для четных и, (1,а)

от-(2"-2)/Здо(2°*-1)/з для нечетных и. (1,6)

Предположим сначала, что и четно. Для п=2 представляемыми числами являются 10, 11, 00 и 01 по основанию -2, т.е. десятичные числа -2, -1, О, 1. Это согласуется с формулой (1,а), причем каждое из чисел диапазона представлено только один раз.

Слово из л-1-1 битов при ведущем бите О может представлять все числа, задаваемые формулой (1,а). Если ведущий бит равен 1, то это слово может представлять все эти же целые числа, смещенные на (-2)" = 2". Новый диапазон равен

от 2" -(2"* -2)/з до 2" +{2" -1)/з

от(2"-1)/з+1до (2"*=-1)/з.

Этот диапазон является смежным с диапазоном (1,а), так что слово размером п + 1 битов однозначно представляет все целые числа из диапазона

от-(2"*-2)/Здо (2"*=-1)/з.

Это согласуется с (1,6), если заменить и на л +1.

Доказательство того, что (1,а) следует из (1,6) при нечетном и и что все целые числа диапазона представлены однозначно, проводится аналогично.

в случае сложения и вычитания используются обычные правила: 0 + 1 = 1 и1-1 = 0. Поскольку 2 записывается как 110, а -1 - как 11, применимы дополнительные правила, которых наряду с обычными вполне достаточно для проведения арифметических вычислений.

1+1=110 11 + 1 = 0 1+1+1=111 0-1=11 11-1 = 10

При сложении и вычитании иногда имеется два бита переноса. Биты переноса добавляются к столбцу даже при вычитании. Их удобно располагать над следующим битом слева и использовать (по возможности) упрощение 11 + 1 = 0. Если И переносится в столбец, который содержит два О, записываем в нем 1 и переносим 1 дальше. Приведем конкретные примеры сложения и вычитания.

Сложение Вычитание

11 1 11 11 1 11 1 1

10111 19 10101 21

+110 10 1 +(-11) - 1 О 1 1 1 О -(-38)

011000 8 1001111 59

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

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

Существует два способа изменить знак числа. Его можно прибавить к самому себе, сдвинутому влево на одну позицию (т.е. умноженному на -1), либо вычесть его из 0. В этом случае нет такого простого и удобного правила, как "дополнить и прибавить 1", присущего арифметике на основе дополнительного кода. При работе с дополнительным кодом это правило используется для создания вычитающего модуля на основе сумматора (для вычисления А-В формируется сумма А + В + \). В случае работы с числами в системе счисления по основанию -2 построить такое простое устройство невозможно.

Умножение в системе счисления по основанию -2 достаточно простое. При этом используются простые правила: 1x1 = 1 и умножение на О дает 0; сложение в столбик выполняется с применением правил сложения чисел в системе счисления по основанию -2.

Деление, однако, оказывается существенно сложнее. Это действительно очень интересная и сложная задача- разработка реального аппаратного алгоритма деления, т.е. алгоритма, основанного на повторяющихся вычитаниях и сдвигах. В листинге 12.1 показан алгоритм, предназначенный для работы на 8-битовом компьютере. Он реализует модульное деление (когда остаток от деления неотрицателен).

Листинг 12.1. Деление в системе счисления с основанием -2

int divbm2(int n, int d) 4 =- n/d no основанию -2 {

int r, dw, c, q, i;

r = n; Инициализация остатка

dw = (-128)*d; Позиция d

с = (-43)*d; Инициализация компаранда

if (d > 0) с = с + d;

q = 0; Инициализация частного

for (i = 7; i >= 0; i--) {

if (d > 0 * (ibl) == 0 * r >= c) {

q = q I (1 << i); Установка бита частного г = г - dw; Вычитание сдвинутого d

dw = dw/(-2); Позиция d

if (d>0) c=c-2*d; Установка компаранда else с = с + d; для следующей итерации

с = с/(-2);

return q; Возврат частного

по основанию -2 Остаток г, О <= г < d

Хотя эта программа написана на С и протестирована на машине с дополнительным кодом, это не играет никакой роли - данный код следует рассматривать абстрактно. Входные величины п и d и все внутренние переменные, за исключением q, являются просто числами без какого-либо конкретного представления. Выходная величина q является строкой битов, интерпретируемой как число в системе счисления по основанию -2.

Здесь требуется небольшое пояснение. Если бы входные величины были числами в системе счисления по основанию -2, то алгоритм было бы очень трудно выразить в выполнимом виде. Например, проверка "if (d>o)" должна была бы установить, находится ли старший значаший бит числа d в четной позиции. Сложение в выражении "с = c+d" также должно было быть реализовано по правилам сложения в системе счисления по основанию -2. Такой код был бы слишком сложен для чтения. Поэтому, рассматривая данный алгоритм, вы должны воспринимать п и d как числа без конкретного представления. Приведенный код просто показывает, какие именно арифметические операции должны быть выполнены, независимо от используемого способа кодирования. Если бы числа были представлены в системе счисления по основанию -2, как при аппаратной реализации данного алгоритма, умножение на -128 представляло бы собой сдвиг влево на семь позиций, а деление на -2 - сдвиг вправо на одну позицию.

В качестве примеров приведем вычисляемые этим кодом значения:.

divbm2(6,2) = 7 (шесть, деленное на 2, равно 111.,) divbm2(-4,3) = 2 (минус четыре, деленное на 3, равно 10 ,) divbm2(-4,-3) = 6 (минус четьфе, деленное на минус три, равно 110 2)

Шаг q = q (i<<i) ; прсдставляет собой просто установку i-ro бита числа q. Следующая строка- г= r-dw; - представляет уменьшение остатка на сдвинутое влево значение делителя d.

Этот алгоритм трудно описать детально, но постараемся представить главную идею.

Рассмотрим определение значения первого бита частного, бита 7 числа q. При основании системы счисления, равном -2, 8-битовое число, у которого старший бит равен 1, находится в диапазоне от -170 до -43. Таким образом, игнорируя возможность переполнения, первый (старший) бит частного будет равен 1 тогда (и только тогда), когда частное алгебраически не превышает-43.

Поскольку n = qd + r и для положительного делителя справедливо соотношение rud-l, то для положительного делителя первый бит частного будет равен 1 тогда и только тогда, ко-