Основы программирования

         

Интерпретация положительных и отрицательных чисел


В кольце вычетов невозможно определить порядок, согласованный с операциями (т.е. так, чтобы, к примеру, сумма двух положительных чисел была положительной). Таким образом, в компьютере нет, строго говоря, положительных и отрицательных целых чисел, поскольку компьютерные целые числа - это на самом деле элементы кольца вычетов. Выбирая либо неотрицательную, либо симметричную систему остатков, можно интерпретировать эти числа либо как неотрицательные в диапазоне от нуля до m-1, либо как отрицательные и положительные числа в диапазоне от -k до k, где k - целая часть от деления m на 2.

В программировании симметричная система остатков более популярна, поскольку трудно обойтись без отрицательных чисел. При этом следует понимать, что сумма двух положительных чисел может оказаться отрицательной, или, наоборот, сумма двух отрицательных чисел - положительной. Иногда в программировании такую ситуацию называют переполнением. Привычные свойства целочисленных операций в компьютере выполняются лишь для небольших чисел, когда результат операции не превосходит числа m = 232. В случае целочисленных переменных переполнение не является экстраординарной ситуацией и не приводит к аппаратным ошибкам или прерываниям. (Это, кстати, отличает компьютерные целые числа от вещественных.) Переполнение - совершенно нормальная ситуация, если вспомнить, что компьютер работает с элементами кольца вычетов по модулю m, а не с настоящими целыми числами.

Следует также отметить, что симметричная система остатков кольца Zm в случае четного m (а m для компьютера равно 232, т.е. четно) не вполне симметрична. Поскольку ноль не имеет знака, то число положительных остатков не может равняться числу отрицательных.

Какой остаток выбрать в классе эквивалентности числа k = m/2? Для этого элемента выполняется непривычное с точки зрения школьной математики равенство

k+k

0 (mod m),

т.е.

k

-k (mod m)

Как отрицательный остаток -k, так и положительный k в равной мере подходят для представления этого класса эквивалентности.
По традиции выбирается отрицательный остаток. Таким образом, в компьютере количество отрицательных целых чисел на единицу больше, чем количество положительных. Так как m = 232 = 4294967296, то k = 231 = 2147483648, и симметричная система остатков состоит из элементов

-2147483648, -2147483647, ..., -2, -1, 0, 1, 2, ..., 2147483647.

В двоичном представлении старший разряд у отрицательных целых чисел равен единице, у положительных - нулю. Двоичные разряды представления целого числа в программировании нумеруют от 0 до 31 справа налево. Старший разряд имеет номер 31 и часто называется знаковым разрядом. Таким образом, знаковый разряд равен единице у всех отрицательных чисел и нулю у неотрицательных. Двоичное представление максимального по абсолютной величине отрицательного числа k состоит из единицы и тридцати одного нуля:

-214748364810 = 100000000000000000000000000000002

Двоичное представление числа -1 состоит из тридцати двух единиц:

-110 = 111111111111111111111111111111112

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

214748364710 = 011111111111111111111111111111112

Следует отметить, что в программировании часто используют также короткие целые числа, двоичная запись которых занимает восемь разрядов, т.е. один байт, или шестнадцать разрядов, т.е. два байта. Работа с такими короткими целыми числами поддерживается на аппаратном уровне. В языке Си однобайтовым целым числам соответствует тип char (тип char в Си - это именно целые числа, символы представляются их целочисленными кодами), двухбайтовым - тип short. Однобайтовые целые числа - это элементы кольца вычетов Zm, где m = 28 = 256. Симметричная система остатков в этом случае состоит из элементов

-128, -127, ..., -2, -1, 0, 1, 2, ..., 127.

В случае двухбайтовых целых чисел (тип short) m = 216 = 65536, а симметричная система остатков состоит из элементов

-32768, -32767, ..., -2, -1, 0, 1, 2, ..., 32767.


Содержание раздела