Целочисленная арифметика в ограниченном числе разрядов
Перечисление чисел в целочисленной компьютерной арифметике
Мы выяснили, что в k-разрядном знаковом или беззнаковом представлении целых чисел количество представимых чисел ограничено и зависит от k. Представимые числа можно перечислить по возрастанию. Например, для восьмиразрядного беззнакового представления допустимые числа располагаются на отрезке следующим образом:
Для восьмиразрядного знакового представления:
Однако в k-разрядной компьютерной арифметике эти отрезки можно замкнуть в кольца и перечислять числа соответствующего представления по кругу.
Все целые числа любого k—разрядного представления можно зафиксировать на кольце по порядку, причем рядом с максимальным числом в том или ином представлении будет находиться минимальное, например:
Действительно, результатом прибавления единицы в арифметике с фиксированным количеством разрядов является следующее по часовой стрелке за исходным значение на кольце, а результатом вычитания единицы — следующее значение по ходу против часовой стрелки. Данный факт очевиден, кроме случаев перехода от максимально допустимого числа к минимальному при прибавлении единицы и от минимального к максимальному при вычитании.
Поясним эти случаи. Рассмотрим вначале беззнаковые представления. Максимально допустимое число в k-разрядном беззнаковом представлении равно 2k - 1 и состоит из k единиц в двоичном представлении. При прибавлении к такому числу единицы мы получаем 2k , что в свою очередь соответствует нулю в k-разрядной арифметике. Вычитание же из нуля единицы является обратной операцией: вычитание единицы можно рассматривать и как прибавление к нулю минус единицы, по правилам же k-разрядной арифметики «минус единица» — это дополнение единицы до 2k , т. е. число, которое при сложении с единицей даст 2k. Очевидно, что таковым является число 2k - 1, состоящее из k двоичных единиц, значит, в беззнаковом представлении 0 + (-1) = 2k - 1, что является максимально представимым числом .
В знаковом k-разрядном представлении максимально допустимым является число 2k-1 - 1 (k - 1 двоичная единица). При увеличении такого числа на 1 мы получаем 2k-1, или единицу в знаковом бите и нули в остальных, что соответствует отрицательному числу с максимально возможным модулем. Вычитание единицы из такого числа можно проводить по правилам обычной двоичной арифметики: 1 0...0 -1 = 0 1...1 = 2k - 1.
Достоинством рассмотренных форматов представления целых чисел является простота реализации алгоритмов арифметических операций (например, вычитание, благодаря использованию дополнительного кода для представления отрицательных чисел, сводится к сложению).
Особенности реализации арифметических операций в конечном числе разрядов
Целочисленная арифметика в ограниченном числе разрядов несколько отличается от обычной. При выполнении арифметических действий в целочисленной k-разрядной арифметике возможно возникновение следующих ситуаций, незнание которых может привести к неверному результату при выполнении верных алгоритмов:
• старшие (левые) цифры результата, выходящие за отведенное количество разрядов, оказываются утерянными;
• при сложении или умножении двух положительных чисел, имеющих знаковое представление, можно получить отрицательное число, если в результате сложения (умножения) в левом знаковом бите окажется единица.
Пример 5. Выполним сложение 10010 и 5110 в знаковом восьмиразрядном представлении. В этом представлении числа имеют следующий вид: 10010 = 0110 01002 и 5110 = 0011 00112. При сложении этих чисел получим 1001 01112. Самая левая единица (знаковый разряд) указывает на то, что в 8 разрядах записано отрицательное число.
Так как все отрицательные числа в машине представляются дополнительным кодом, то для восстановления десятичного значения этого отрицательного числа надо воспользоваться алгоритмом получения исходного числа но его дополнительному коду (см. пример 4). В результате получим число -105.
Таким образом, в восьмиразрядной знаковой арифметике 100 + 51 = -105, т. е. при сложении двух положительных чисел мы получили отрицательное число!