Представление целых чисел без знака и со знаком в памяти ЭВМ.

Любая информация (данные, команды) представляется в ЭВМ в виде двоичных кодов. Отдельные элементы двоичного кода, имеющие значение 0 или 1, называют разрядами или битами. Поэтому каждый из однородных элементов ячейки памяти компьютера, находящийся в одном из двух устойчивых состояний и хранящий один бит двоичного кода называется разрядом. Структурной единицей представления двоичного кода являются: 8-разрядный формат – байт, 32-разрядный формат – машинное слово, 16-разрядный формат – полуслово и 64-разрядный формат – двойное слово.

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

Для компьютерного представления целых чисел можно использовать несколько различных типов данных, отличающихся количеством разрядов и наличием или отсутствием знакового разряда. Выпишем значение границ диапазонов для различных типов данных, указывая число разрядов и названия соответствующих типов в Turbo-Pascal.

Таблица 1. Границы диапазонов для различных типов данных

В целях упрощения выполнения арифметических операций применяют специальные коды для представления чисел в компьютере. Использование кодов позволяет свести операцию вычитания чисел к арифметическому сложению кодов этих чисел. Применяются прямой, обратный и дополнительный коды чисел. Прямой код используется для представления положительных и отрицательных чисел в запоминающем устройстве компьютера. Обратный и дополнительный коды используются для замены операции вычитания операцией сложения, что упрощает устройство арифметического блока ЭВМ.

Прямой код двоичного числа совпадает по изображению с записью двоичного числа. Знаковым разрядом обычно является старший разряд в разрядной сетке, значение которого для положительных чисел равно 0, а для отрицательных чисел 1. Прямой код числа 53 = 110101₂ в восьмиразрядном знаковом представлении имеет вид:

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

Условимся при записи кода знаковый разряд отделять от других разрядов запятой. Например, если для записи кода выделен один байт, то для положительного двоичного числа 1101 прямой код соответствует записи 0,0001101, а для отрицательного двоичного числа –1101 прямой код 1,0001101.

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

• модуль числа представить прямым кодом в k двоичных разрядах;

• инвертировать значение всех бит и таким образом получить обратный код исходного числа;

• к полученному обратному коду прибавить единицу в младший разряд и тем самым получить дополнительный код исходного числа.

Обратный и дополнительный код положительного числа совпадает с прямым кодом. Дополнительный код чисел в 8-разрядном знаковом представлении будет следующим:

Исходное число	+13	–13
Прямой код	0,0001101	1,0001101
Прямой код модуля числа	0,0001101	0,0001101
Обратный код	0,0001101	1,1110010
Дополнительный код	0,0001101	1,1110011

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

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

Для формулирования алгоритма реализации аппаратного прибавления единицы succ(a,k) договоримся, что любое число, записанное в k разрядах, будем обозначать как <начало> <последний разряд>, где <начало> – это первый слева k–1 разрядов, а <последний разряд> – самый правый разряд в записи числа. Рекурсивный алгоритм succ(a,k) прибавления единицы к k левым разрядам числа а, следующий:

1. если k = 0, то конец;

2. если а – четное, то вносим единицу в <последний разряд>; конец;

3. если а – нечетное, то вносим ноль в <последний разряд>; succ(a,k)=succ(<начало>,k–1); конец.

Компьютерная операция умножения целых чисел реализуется через операцию сложения, умножения и деления на 2. Операция вычитания целых чисел заменяется сложением с числом противоположного знака. Целочисленное деление с остатком с сводится к сравнению (проверка знака у разности этих чисел) и вычитанию. Однако, если в делении участвуют отрицательные числа, то остаток компьютерного деления может не совпадать с математическим понятием остатка, что следует контролировать при программировании.

Методические указания

Сложения чисел в обратном и дополнительном кодах имеет ряд особенностей. Если результатом арифметических действий является код отрицательного числа, то необходимо дополнительный код данного числа преобразовать в прямой код. При этом алгоритм преобразования можно выполнить как в обратном, так и прямом порядке.

Пример 5.

Получить десятичное значение числа по его дополнительному коду 10010111.

1. Из дополнительного кода вычтем единицу и получим обратный код.

10010111

–             1

10010110

2. Инвертируем обратный код и получим модуль отрицательного числа 01101001.

3. Переведем полученное значение в десятичную систему счисления 01101001₂=105.

Ответ: –105.

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

Пример 6.

а) Сложить X и Y в обратном и дополнительном кодах.

X= 111, Y= –11.

Сложим числа, пользуясь правилами двоичной арифметики: X+Y = 111 – 11 = 100.

Сложим числа, используя различные коды.

Прямой код	Сложение в обратном коде	Сложение в дополнительном коде
X пр=0,0000111 Yпр=1,0000011	Xобр=         0,0000111 Yобр=         1,1111100                1 0,0000011                                +1 (X+Y)обр= 0,0000100	Xдоп=        0,0000111 Yдоп=        1,1111101                 1)0,0000100 отбрасывается (X+Y)доп= 0,0000100

Так как результат сложения является кодом положительного числа (знаковый разряд содержит нулевое значение), то (X+Y)_обр=(X+Y)_доп=X+Y=100.

Ответ: 100.

б) Сложить X и Y в обратном и дополнительном кодах.

X= –101,Y= –11.

Сложим числа, пользуясь правилами двоичной арифметики X+Y= – 101 –110 = –1011.

Сложим числа, используя различные коды.

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

Из обратного кода:

(X+Y)_обр=1,1110100 (X+Y)_пр=1,0001011.

Из дополнительного кода:

(X+Y)_доп=1,1110101 (X+Y)_пр=1,0001010+0,0000001=1,0001011.

Таким образом, X+Y= –1011 и полученный результат совпадает с обычной записью.

Ответ: –1011.

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

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

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

Пример 7.

Проверить правильность результата сложения чисел 86 и 104, представленных в 8-разрядном знаковом типе.

X=86	Xпр=0,1010110
Y=43	Yпр=0,0101011
(X+Y)=86+43=129	(X+Y)обр=1,0000001
Результат:           129	(X+Y)пр = 1,1111111 = -127

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

Ответ: результат неверный.

Рассмотрим выполнение алгоритмов сложения и умножения целых чисел в компьютерном исполнении. Обозначим целочисленное деление на 2 (сдвиг на один разряд вправо) для нечетного и для четного числа как a>>1, а умножение на 2 (сдвиг на один разряд влево) как a<<1.

Тогда рекурсивный алгоритм сложения двух целых двоичных чисел add(a,b) запишем следующим образом:

1. если а = 0, то add(a,b) = b; конец;

2. если b = 0, то add(a,b) = а; конец;

3. а, b – четные:
   add(a,b) = add(a>>1,b>>1)<<1, конец;

4. а, b – нечетные:
   add(a,b) = add(a>>1,b>>1+1)<<1, конец;

5. а, b имеют различную четность:
   add(a,b) = add(a>>1,b>>1)<<1+1, конец.

Проиллюстрируем на примере работу данного алгоритма.

Пример 8.

Сложить двоичные числа 1011 и 1110.

Вначале выполним рекурсивный спуск:

add(1011,1110) = add(101,111)<<1 + 1;

add(101,111) = add(10,11+1)<<1= add(10,100)<<1;

add(10,100) = add(1,10)<<1;

add(1,10) = add(0,1)<<1 + 1;

add(0,1) =1.

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

add(1,10) = 1<< + 1=10 + 1 = 11

add(10,100) = 11<<1 = 110

add(101,111) = 110<<1 = 1100

add(1011,1110) = 1100<<1 + 1 = 11000 +1=11001

Выполним проверку результата.

1011

+  1110

11001

Ответ:11001.

Рекурсивный алгоритм умножения целых двоичных чисел mult(a,b) запишем следующим образом:

1. если а = 0, то mult(a,b)= 0; конец;

2. а, – четное: mult(a,b)= mult(a>>1,b)<<1; конец;

3. а, – нечетное: mult(a,b)= mult(a>>1,b)<<1 + b; конец.

Проиллюстрируем на примере работу данного алгоритма.

Пример 9.

Умножить в 8-разрядном беззнаковом формате 23 на 10.

10 = 1010₂; 23 = 10111₂.

Выполним рекурсивный спуск:

mult(1010,10111) = mult(101,10111)<<1;

mult(101,10111) = mult(10,10111)<<1 + 10111;

mult(10,10111) = mult(1,10111)<<1;

mult(1,10111) = mult(0,10111)<<1 + 10111;

mult(0,10111) = 0.

Выполним рекурсивный подъем:

mult(1,10111) =0<<1 + 10111 = 10111;

mult(10,10111) = 10111<<1 = 101110;

mult(101,10111) = 101110<<1 + 10111 = 1110011;

mult(1010,10111) = 1110011<<1 = 11100110.

Выполним проверку результата:

10111

+     1010

10111

10111

11100110

Ответ:11100110.