Документ взят из кэша поисковой машины. Адрес оригинального документа : http://al.cs.msu.ru/files/bordachenkova.number.representation.2009.doc Дата изменения: Mon Nov 19 15:14:52 2012 Дата индексирования: Sat Feb 2 22:32:50 2013 Кодировка: koi8-r

ПРЕДСТАВЛЕНИЕ ЦЕЛЫХ ЧИСЕЛ В ЭВМ.


Бордаченкова Е.А.

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

Для удобства вычислений будем считать, что ячейка состоит из 8
разрядов (битов). Байт - 8 битов. Слово "байт" используется как для
обозначения ячейки (например, при описании ОП), так и для обозначения
содержимого ячейки. Путаницы при этом не возникает, так как всегда ясно,
идет речь о физическом устройстве, или о математическом объекте.


П.1. Числа без знака.

Как использовать данные нам 8 битов для изображения числа? Первая
мысль, которая приходит в голову - считать, что эти биты являются цифрами в
записи числа в двоичной системе счисления. Тогда самый правый бит является
коэффициентом при 20, второй справа - при 21 и т.д.

|27|26|25|24|23|22|21|20|
| | | | | | | | |
|12|64|32|16|8 |4 |2 |1 |
|8 | | | | | | | |

При этих условиях байт 10010101 изображает число
1(27+0(26+0(25+1(24+0(23+1(22+0(21+1(20=128+16+4+1=149.
Такое представление числа называется прямым кодом числа. Этим способом
можно представлять (изображать в виде байта) все целые числа от 0 (байт
00000000) до 255 (байт 11111111). Если мы трактуем содержимое байта таким
образом, оно (содержимое) называется числом без знака.
Итак, байт может содержать число без знака, или содержимое байта может
быть числом без знака.


П.2. Числа со знаком.

Хотелось бы иметь возможность работать и с отрицательными числами
(например, для того, чтобы применять операцию вычитания). В нашем
распоряжении имеется всего 28=256 возможных значений байта. Какое множество
целых чисел мы хотели бы изобразить с помощью этих комбинаций? Было бы
удобно, чтобы изображаемое множество было связное (в него входили бы подряд
идущие целые числа); чтобы положительных и отрицательных чисел было
одинаковое количество. Следовательно, нас интересует множество из 256
подряд идущих чисел, расположенное симметрично относительно 0. Например,
множество (-128,127(.
[pic]
Как изобразить эти числа с помощью байтов? Пусть байты от 0 (00000000)
до 127 (01111111) изображают сами себя - целые числа от 0 до 127. Тогда
байты от 128 (10000000) до 255 (11111111) должны соответствовать
отрицательным числам.
Замечание: Обратим внимание на старший (самый левый) бит байта. У
байтов, изображающих положительные числа, он равен 0. У байтов,
изображающих отрицательные числа, он равен 1. Поэтому старший бит часто
называют знаковым. При этом считается, что 0 изображает знак "+", а 1 (
знак "-". Если считать, что байт изображает число описанным способом,
говорят, что байт содержит число со знаком.
Пусть

|-1 |представляется байтом 11111111 (255 в двоичной системе) |
|-2 |представляется байтом 11111110 (254 в двоичной системе) |
| | ( ( ( |
|-10 |представляется байтом 11110110 (246 в двоичной системе) |
|-128 |представляется байтом 10000000 (128 в двоичной системе) |


Такое представление отрицательных чисел называется представлением в
дополнительном коде, поскольку представление числа x и представление числа
-x дополняют друг друга до 256 (28).
Определение. Пусть x - число из диапазона [-128, -1]. Представлением
числа x в дополительном коде называется число 256 - ( x (.
Замечания.
1. Можно дать другое, эквивалентное приведенному, определение понятия
"представление числа со знаком": для любого числа x((-128,127(
представление x есть двоичное восьмиразрядное число x mod 256.
2. Мы рассмотрели две возможных трактовки содержимого байта. Причем, в
обоих случаях каждый байт из 00000000 ( 01111111 изображает одно и то
же положительное число. А каждый байт из диапазона 10000000 ( 11111111
изображает два разных числа. Например, байт 11110000 изображает число
без знака 240 и число со знаком -16.
[pic]


П.3. Способы получения дополнительного кода числа.

Пусть число x принадлежит интервалу [-128, 0[. Есть несколько способов
получения его представления в дополнительном коде.
1 способ. По определению дополнительного кода.

|Представление x = |256-( x ( = 128 |(128 -( x ( ) |
| |+ | |
| |'1' в знаковом |представление числа в двоичной |
| |разряде |системе с использованием 7 |
| | |разрядов |
| | |(т.к. 0( 128 -( x ((127 ) |

2 способ. Через обратный код.

|Представление x = |256-( x ( =|255 - ( x (|+ 1 |
| | |инвертированное |
| | |представление числа ( x ( |

В инвертированном представлении все нули заменены единицами, и наоборот.
Такое представление называется обратным кодом числа ( x (.
Таким образом, можно сформулировать следующий алгоритм:
1. выписать представление числа ( x ( (прямой код ( x (),
2. получить обратный код ( x ( (инвертировав все разряды прямого кода),
3. прибавить 1.
3 способ. Вычитанием из 255.

|Представление x = |256 - ( x ( = 255 |(( x ( - 1) |
| |- | |
| | |0( ( x ( ( 128, |
| | |следовательно |
| | |0( ( x ( - 1( 128, |
| | |значит данное |
| | |положительное число |
| | |представимо в виде байта|

Отсюда вытекает алгоритм:
1. получить представление числа ( x ( - 1,
2. вычесть полученное число из 255.
Заметим, что выполнить вычитание из 255 в двоичной системе довольно
просто, так как 255=111111112.
Примеры. Получить представление в дополнительном коде для следующих
чисел.
Пример 1. x= -118.
Применим первый способ.
128 + (128 - 118) = 128 + 10 = [pic]2
Ответ: 10001010.
Пример 2. x= -100.
128 + (128 - 100) = 128 + 28 = 128 + (16 + 8 + 4 ) = [pic]2
Ответ: 10011100.
Пример 3. x= -15.
Используем второй способ.
а) прямой код числа ( x ( : 15 = 8 + 4+ 2+ 1 = 000011112
б) обратный код: 111100002
в) дополнительный код: 111100012
Ответ: 11110001.
Пример 4. x= -30
а) прямой код числа ( x ( : 30 = 16 + 8 + 4 + 2 = 000111102
б) обратный код: 111000012
в) дополнительный код: 111000102
Ответ: 11100010.
Пример 5. x= -47.
Используем третий способ.
а) ( x ( - 1 = 46 = 32 + 8 + 4+ 2 = 001011102
б) 255 - (( x ( - 1) = 111111112 - 001011102 = 110100012

Рассмотрим следующую задачу. Пусть есть байт [pic], изображающий число
x([-127,127]. Как получить байт [pic] - изображение числа -x?
Из соотношения ((-a) mod b + a mod b) mod b = 0 можно вывести, что
[pic]
Следовательно, [pic] = 256 - [pic] для всех x ( 0. Для вычисления
значения 256 - [pic] подходит алгоритм получения дополнительного кода через
обратный код ([pic]((0, 255]).
При x=0 применение алгоритма получения дополнительного кода через
обратный код даёт нулевой байт.
Таким образом, получить число со знаком, обратное данному, можно,
применив алгоритм вычисления дополнительного кода числа.При этом, если
применить этот алгоритм второй раз, вернемся к исходному числу ( что вполне
оправдано: -(-x)= x ).
Напомним, что представимое множество целых чисел со знаком не совсем
симметрично: в него входит число -128, и не входит число 128. Отсюда
следует, что применение операции получения обратного для числа -128 будет
некорректным. Если формально применить алгоритм получения дополнительного
кода, получим
-128 = 100000002
1. Прямой код 10000000
2. Обратный код 01111111
3. +1 10000000
Как видим, получается исходное число -128.
Данный пример показывает, что число -128 является в некотором смысле
особенным; при программировании это следует учитывать.
Замечание. Все рассмотрения пунктов 1(3 легко можно повторить для
любой другой (не равной 8) размерности ячейки.

Примеры.

Определить, какое число без знака и какое число со знаком содержит
байт.
Пример 1. Дан байт 00110111.
1). Число без знака получается переводом данного числа в десятичную
систему:
32 + 16 + 4 + 2 + 1 = 55.
2) Число со знаком. Мы знаем, что байты из интервала [0, 127] изображают
число со знаком, совпадающее с числом без знака.
Ответ: число без знака 55;
число со знаком 55.
Пример 2. Дан байт 10111001.
1). Число без знака получается переводом данного числа в десятичную
систему:
128 + 32 + 16 + 8 + 1 = 185.
2) Число со знаком. Так как 185 > 127, число 185 является дополнительным
кодом для некоторого отрицательного числа x: 185 = 256 - | x |, | x | = 256
- 185 = 71. Поскольку x<0, то x= -71.
Ответ: число без знака 185;
число со знаком -71.


П.4. Арифметические операции (сложение и вычитание).


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

Пример 1. 120 + 43
120 = 011110002, 43 = 001010112
....
01111000 (120)
+00101011 (43)

10100011 (163)


Пример 2. 120 - 43
....
01111000 (120)
-00101011 (43)

01001101 (77).

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



Пример 3. 200 + 60
.....
11001000 (200)
+00111100 (60)

1(00000100 (4).
(
не уместилась в байте.

При сложении чисел 200 и 60 произошел выход за разрядную сетку. Поскольку
мы располагаем только восемью разрядами, в ответе имеем число 4;
коэффициент при 28, получившийся в результате переноса, потерялся.
Вспомним, что в виде чисел без знака представимы числа из диапазона [0,
255]. Число 260 = 200 + 60 не принадлежит допустимому диапазону, что и
привело к неверному результату сложения.

Пример 4. 10 - 20
.... .
00001010 (10)
-00010100 (20)

11110110 (246).
При выполнении вычитания приходится делать заём из несуществующего разряда.
В итоге получается неправильный ответ. Правильный результат -10 = 10 - 20
не принадлежит представимому диапазону, следовательно, вычитание не может
выполниться корректно.
Рассмотрим теперь байты - числа со знаком. Используемое нами
представление (для отрицательных чисел - в дополнительном коде) позволяет
применять обычные алгоритмы вычисления в столбик.
Обозначим P(a) - представление числа a (a([-128,127]). Пусть x и y -
числа из интервала [-128, 127]. Пусть надо вычислить x + y (или x - y ),
то есть получить представление P(x + y) ( или P(x - y) ) для числа x + y
(x - y соответственно).
Напомним, что
P(a) = a mod 256.
Воспользуемся известным соотношением
( a( b ) mod c = ( a mod c ( b mod c ) mod c.
Если число x + y (число x - y) представимо в виде числа со знаком
(принадлежит отрезку [-128, 127]), его представление можно получить,
выполнив соответствующую арифметическую операцию над представлениями чисел
x и y :
P(x(y) = (x(y) mod 256 = (x mod 256 ( y mod 256 ) = ( P(x)( P(y) ) mod
256.
Взятие результата по модулю 28 обозначает тот факт, что вычисления
производятся с использованием восьми разрядов, лишние возникающие цифры
(или заём из несуществующего разряда) не учитываются.

Примеры.

Пример 5. Вычислить 110 + (-3)
......
01101110 (110)
+11111101 (-3)

1(01101011 (107).


Пример 6. Вычислить 20 - (-103)
..... ..
00010100 (20)
-10011001 (-103)

01111011 (123).
При выполнении вычитания мы вынуждены сделать заем из несуществующего
разряда, что не отразилось на правильности результата, так как вычисления
производятся по модулю 256.
Следующий пример показывает, как вычисление может дать неверный
результат.
Пример 7. Вычислить 110+110
.. ...
01101110 (110)
+01101110 (110)

11011100 (-36).
Поскольку результат сложения 220 нельзя представить как число со знаком, в
результате сложения получился неверный ответ. (Если считать, что мы
работаем с числами без знака, ошибки не происходит. Рассматривая байт
11011100 как число без знака, имеем 110111002 = 220)
Замечание: Подчеркнём, что существование алгоритмов сложения и
вычитания, применимых как к числам без знака, так и к числам со знаком,
вытекает из использования представления чисел в дополнительном коде.
Для выполнения умножения и деления приходится применять различные
алгоритмы для чисел без знака и для чисел со знаком.


П.5 Арифметические флаги.


Выполнение арифметических операций с числами не всегда приводит к
математически правильному результату. В самом деле, математический
результат может выйти за диапазон представимости чисел, в этом случае
машинный результат будет отличаться от математического (см. примеры 3, 7
пункта 4). Чтобы отследить подобную ситуацию, в процессоре компьютера
имеются специальные (однобитовые) регистры - флаги. Есть четыре флага,
отвечающих за арифметические операции (арифметические флаги). Некоторые
флаги сигнализируют об ошибке при выполнении арифметической операции. Если
ошибки нет, они устанавливаются в 0, если ошибка есть - в 1. Другие флаги
сигнализируют о получении отрицательного результата или нуля. Флаги имеют
названия:
CF - carry flag (флаг переноса)
OF - overflow flag (флаг переполнения)
SF - sign flag (флаг знака)
ZF - zero flag (флаг нуля).
Флаги имеют следующий смысл.
CF: Отвечает за работу с числами без знака. Он устанавливается в 1, если
в результате выполнения операции с числами без знака получился результат,
не представимый как число без знака (то есть не принадлежащий интервалу

[0, 255]).
OF: Отвечает за работу с числами со знаком. Он устанавливается в 1, если
в результате выполнения операции с числами со знаком получился результат,
не представимый как число со знаком (то есть не принадлежащий интервалу

[-128, 127]).
SF: Отвечает за работу с числами со знаком. Устанавливается в 1, если в
результате выполнения арифметической операции со знаковыми числами
получилось отрицательное число, и в 0 - в противном случае. Если результат
был вычислен неверно (OF = 1), SF неверно указывает его знак (противоречит
знаку результата); если правильный результат положительный, то SF равен 1,
если правильный результат отрицательный, то SF равен 0.
ZF: Устанавливается в 1, если результат по модулю 256 равен 0, и ZF=0 в
противном случае. Этот флаг используется при работе с числами без знака и
при работе с числами со знаком.
Процессор использует следующие правила при установлении значений
флагов.

|Флаг CF |CF=1, |при выполнении сложения произошёл перенос за |
| | |разрядную сетку; |
| |CF=0, |в противном случае |
| |CF=1, |при выполнении вычитания был сделан заём из-за |
| | |разрядной сетки; |
| |CF=0, |в противном случае |
|Флаг OF |OF=1, |при выполнении сложения перенос в знаковый разряд не|
| | |совпадает с переносом из знакового разряда (за |
| | |разрядную сетку); |
| |OF=0, |переносы совпадают |
| |OF=1 |при выполнении вычитания заём из знакового разряда |
| | |не совпадает с заёмом в знаковый разряд (из-за |
| | |разрядной сетки); |
| |OF=0 |заёмы совпадают |
|Флаг SF | совпадает со знаковым разрядом результата |
|Флаг ZF |ZF=1, |все разряды результата равны 0; |
| |ZF=0, |в противном случае |

Примеры. Определить, какие значения получат арифметические флаги в
результате выполнения следующих операций.
Пример 1. 200 + (-20).
CF: CF отвечает за работу с беззнаковыми числами. Следовательно, надо
записать этот пример так, чтобы оба операнда были числами без знака.
Числу

-20 соответствует код 256-20 = 236. Пример будет выглядеть так:

200+236 = 436. 436([0,255], следовательно, CF=1.
OF: OF отвечает за работу со знаковыми числами. Нам надо записать пример
так, чтобы оба операнда были числами со знаком. Числу 200 соответствует
число -(256-200)= -56. (200 является дополнительным кодом для числа
-56). Итак, пример запишется так: -56+(-20) = -76. Число -76
принадлежит интервалу [-128,127], следовательно, OF=0.
SF: OF=0 и результат -76 - отрицательный, значит, SF=1.
ZF: -76(0, следовательно, ZF=0.
Пример 2. (-100) + 150.
CF: Перепишем пример так, чтобы операнды были числами без знака:

156+150 = 306 > 255 , следовательно, CF=1.
OF: Перепишем пример так, чтобы операнды были числами со знаком:

(-100) + (-106) = -206 < -128, следовательно, OF=1.
SF: OF=1, -206<0, следовательно, SF=0 (противоречит знаку правильного
результата).
ZF: ZF=0.
Пример 3. 128 + 128.
CF: 128 + 128 = 256 > 255 , значит, CF=1.
OF: (-128) + (-128) = -256 < -128, значит, OF=1.
SF: OF=1, -256<0, следовательно, SF=0.
ZF: 256 mod 256 = 0, значит, ZF=1.
Замечание. В последующих примерах для краткости будем использовать
шестнадцатиричную систему вместо двоичной при записи содержимого байта. В
этом случае байт запишется в виде двух шестнадцатиричных цифр, каждая цифра
изображает четыре двоичных разряда.


|016 - 00002 |416 - 01002 |816 - 10002 |C16 - 1210 - |
| | | |11002 |
|116 - 00012 |516 - 01012 |916 - 10012 |D16 - 1310 - |
| | | |11012 |
|216 - 00102 |616 - 01102 |A16 - 1010 - |E16 - 1410 - |
| | |10102 |11102 |
|316 - 00112 |716 - 01112 |B16 - 1110 - |F16 - 1510 - |
| | |10112 |11112 |


Пример 4. 6A16 - D616

|CF: | .( . . |Поскольку был произведен заем из-за разрядной|
| |01101010 |сетки в старший разряд, CF=1 |
| |-11010110 | |
| |10010100 | |
|OF: | . (. . |Заём в старший разряд есть, а заёма из |
| |01101010 |старшего разряда нет, следовательно, OF=1 |
| |-11010110 | |
| |10010100 | |
|SF: |SF=1, совпадает со старшим разрядом результата |
|ZF: |ZF=0, в результирующем байте есть биты, равные 1 |



Пример 5. 7516 + 5C16

|CF: | (. .... |Нет переноса за разрядную сетку, CF=10 |
| |0 1110101 | |
| |+0 1011100 | |
| |1 1010001 | |
|OF: | .(.... |Перенос в старший разряд есть, переноса из |
| |0 1110101 |старшего разряда нет, значит, OF=1 |
| |+0 1011100 | |
| |1 1010001 | |
|SF: |SF=1 |
|ZF: |ZF=0 |



Пример 6. B716 - CC16

|CF=1 |.(. . | |
| |10110111 | |
| |-11001100 | |
| |11101011 | |
|OF=0 | ..( . |Были сделаны заём из старшего разряда и |
| |10110111 |заём в старший разряд из-за разрядной сетки|
| |-11001100 | |
| |11101011 | |
|SF=1 | |
|ZF=0 | |



Пример 8. 8016 + 8016

|CF=1 | .( | |
| |10000000 | |
| |+10000000 | |
| |1(00000000 | |
|OF=1 | . ( | |
| |10000000 | |
| |+10000000 | |
| |1(00000000 | |
|SF=0, |совпадает со старшим разрядом результата. Единица вышла за |
| |разрядную сетку, не попала в результат. |
|ZF=1, |все биты результата равны 0 |