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

Из уже построенных арифметик над и легко выделить основы двоичной арифметики. Существуют две так называемые двоичные арифметики. Первая – это так называемая знаковая и модульная форма, определённая на , т.е. (определённое в предыдущем параграфе) с добавленным знаком, расширяющим элементы . Знак обычно кодируют в бинарной форме: для « » и для « ». Вторая арифметика (двоичная арифметика дополнений) – это с элементами во всех n позициях. Этот вид двоичной арифметики используется в большинстве компьютеров. Поэтому ограничим наши рассмотрения . Чтобы сделать обсуждение более конкретным, рассмотрим , элементы которого лежат в пределах от (т.е. содержит различных чисел). Число представляется в как . Поэтому легко найти двоичное дополнение. Для этого надо слегка изменить все двоичные цифры, называемые битами, чтобы получить дополнение до , а затем прибавить , чтобы получить дополнение до 2.

П р и м е р 3.1.

. //

Очевидно, что могут возникнуть проблемы, вызванные ограниченностью чисел. Мы не можем их избежать, од­нако следует знать, когда возможна «ошибка». Форма дополнения делает проверку условия переполнения от­носительно легкой, использующей только значения стар­шего значащего бита. (В это бит с номером .) Этот бит обозначает знак представляемого числа и назы­вается знаковым битом или знаковым разрядом. Перед тем как проверить, какое значение имеет знаковый бит, напомним, что прибавление к максимальному положительному числу в дает максимальное отрицатель­ное число (наибольшее отрицательное число — это отри­цательное число, отстоящее дальше всего от нуля). Дру­гими словами, числа повторяются ц иклическим образом. В мы имеем ситуацию, изображенную на рис. 4.1.

Рис. 4.1

Что же произойдёт, если мы сложим два числа и , где

и (в , a = 16)?

Сумма будет ограничена:

.

Само по себе это неравенство ничего не даёт. Поэтому мы рассмотрим три случая:

( I ) если и

тогда ;

( II ) если и

тогда ;

( III ) если и

тогда .

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

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

а) оба числа отрицательны;

б) оба числа положительны;

в) числа имеют различные знаки.

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

П р и м е р 3.2. Напомним, что вычисления проводятся в :

. //

Вернёмся теперь к умножению и делению. Сначала рассмотрим умножение. Напомним, что в (или, более точно, в для достаточно большого n) умножение на 10 можно получить «сдвигом» всех цифр на одну позицию влево и записью в 0-й позиции цифры 0. (В умножение на m также всегда можно осуществить сдвигом влево.)

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

П р и м е р 3.3. (Вычисления проводятся в .)

. //

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

П р и м е р 3.4. (Вычисления проводятся в .)

.

Поэтому

. //

Точно так же, как умножение производилось сдвигами влево, деление на положительные степени числа 2 осуществляется сдвигом вправо. (Деление на другие целые числа должно получаться путём сведения к вычитанию степеней числа 2. Этот процесс мы обсуждать не будем.) Однако специального рассмотрения требуют отрицательные числа. Отметим также, что в общем случае ожидаемый результат (т.е. арифметически ожидаемый результат в R) будет не целым, а дробным.

П р и м е р 3.5. Попытаемся в вычислить , и сдвигом на , и позиции соответственно. Имеем

(12)

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

Следовательно, приводит к

.

Действие битов (со значением ), «выпадающих» из числа в результате сдвига вправо, должно усекать результат. Поэтому даёт . Существует общепринятая практика округлять число (вверх независимо от знака) прибавлением к числу утерянного последнего бита. Это соответствует обычному арифметическому правилу округления, поскольку в первом бите остатка представляет собой . Следовательно, даёт .

У п р а ж н е н и е 4.3.

1. Быстрый способ вычисления дополнения до 2 от данного битового элемента в заключается в следующем. Начиная с правого конца, копируем все идущие подряд нули и первую встретившуюся единицу. Затем все оставшиеся биты изменяем. Показать, что этот способ работает в большинстве случаев, и рассмотреть случаи, когда он не работает.

2. Пусть в производятся следующие вычисления. Складывают два числа и (обозначим их сумму через ). Если от отнять , то получим некоторый результат , а если от отнять , то получим некоторое число . Что можно сказать о и ? Как отличаются результаты, если вычисления производятся в ?