Математические основы информатики

Перечисление чисел в целочисленной компьютерной арифметике

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

Для восьмиразрядного знакового представления:

Однако в k-разрядной компьютерной арифметике эти отрезки можно замкнуть в кольца и перечислять числа соответствующего представления по кругу.

Все целые числа любого k—разрядного представления можно зафиксировать на кольце по порядку, причем рядом с максимальным числом в том или ином представлении будет находиться минимальное, например:          

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

Поясним эти случаи. Рассмотрим вначале беззнаковые представления. Максимально допустимое число в k-разрядном беззнаковом представлении равно 2^k - 1 и состоит из k единиц в двоичном представлении. При прибавлении к такому числу единицы мы получаем 2^k , что в свою очередь соответствует нулю в k-разрядной арифметике. Вычитание же из нуля единицы является обратной операцией: вычитание единицы можно рассматривать и как прибавление к нулю минус единицы, по правилам же k-разрядной арифметики «минус единица» — это дополнение единицы до 2^k , т. е. число, которое при сложении с единицей даст 2^k. Очевидно, что таковым является число 2^k - 1, состоящее из k двоичных единиц, значит, в беззнаковом представлении 0 + (-1) = 2^k - 1, что является максимально представимым числом .

В знаковом k-разрядном представлении максимально допустимым является число 2^k-1 - 1 (k - 1 двоичная единица). При увеличении такого числа на 1 мы получаем 2^k-1, или единицу в знаковом бите и нули в остальных, что соответствует отрицательному числу с максимально возможным  модулем.  Вычитание  единицы  из  такого числа можно проводить по правилам обычной двоичной арифметики: 1 0...0 -1 = 0 1...1 = 2^k - 1.

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

Особенности реализации арифметических операций в конечном числе разрядов

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

•   старшие (левые) цифры результата, выходящие за отведенное количество разрядов, оказываются утерянными;

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

Пример 5. Выполним сложение 100₁₀ и 51₁₀ в знаковом восьмиразрядном представлении. В этом представлении числа имеют следующий вид: 100₁₀ = 0110 0100₂ и 51₁₀ = 0011 0011₂. При сложении этих чисел получим 1001 0111₂. Самая левая единица (знаковый разряд) указывает на то, что в 8 разрядах записано отрицательное число.

Так как все отрицательные числа в машине представляются дополнительным кодом, то для восстановления десятичного значения этого отрицательного числа надо воспользоваться алгоритмом получения исходного числа но его дополнительному коду (см. пример 4). В результате получим число -105.

Таким образом, в восьмиразрядной знаковой арифметике 100 + 51 = -105, т. е. при сложении двух положительных чисел мы получили отрицательное число!