Вопрос 50.doc

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

Будем исходить из того, что для записи числа в устройствах компьютера выделяется фиксированное количество двоичных разрядов. Память компьютера имеет байтовую структуру, однако, размер одной адресуемой ячейки обычно составляет несколько байт. Например, в компьютерах IBM ячейка памяти объединяет 2 байта (16 двоичных разрядов) - такая комбинация связанных со­седних ячеек, обрабатываемая совместно, называется машин­ным словом. Для представления числа в регистре арифметико-логического устройства процессора, где формируется результат операции, имеется еще один дополнительный одноразрядный ре­гистр, который называется регистром переноса и который можно рассматривать в качестве продолжения (т.е. 17-го бита) регистра результата.

Конечный размер разрядной сетки порождает понятие «наи­большее целое число», которого в обычном (немашинном) пред­ставлении чисел просто не существует. Если количество разря­дов k и р = 2, то, согласно формуле, что ,. В частности, при к=16: . Другими словами, целого числа, скажем, 65636 и более в компьютере просто не может существовать и, следовательно, появление в ходе вычислений чисел, превышающих (Z₂), должно интерпре­тироваться как ошибка. Минимальным целым числом в беззнако­вом представлении, очевидно, является . В языке программирования PASCAL целые числа без знака, для записи которых отводится 2 байта, определены как тип Word. Тип устанавливает способ кодирования числа, количество отво­димых для записи ячеек памяти (т.е. разрядность числа), а также перечень допустимых операций при обработке. Выход за границу 65535 возможен только путем увеличения количества разрядов для записи числа, но это порождает новый тип со своим Z; на­пример, тип Longint, числа которого занимают 4 байта.

Рассмотрим, как с беззнаковыми числами выполняются ариф­метические операции, не меняющие типа числа; очевидно, к ним относятся сложение и умножение.

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

0+0=   0     0+1=1

1 +0=   1     1 + 1 =10

В последнем случае в том разряде, где находились слагаемые, оказывается 0, а 1 переносится е старший разряд. Место, где со­храняется переносимая в старший разряд 1 до того, как она будет использована в операции, называется битом переноса .

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

0*0 = 0        0 *1 = 0;

1 *0 = 0        1*1 = 1.

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

Кодирование целых чисел, имеющих знак, можно осуществить двумя способами. В первом варианте один (старший) разряд ма­шинном слове отводится для записи знака числа; при этом усло­вились кодировать знак «+» нулем, знак «-» - единицей. Под за­пись самого числа, очевидно, остается 15 двоичных разрядов, что обеспечивает наибольшее значение числа   = 32767₁₀. Такое представление чисел называется прямым кодом. Однако его применение усложняет порядок обработки чисел; например, опе­рация сложения двух чисел с разными знаками должна быть заме­нена операцией вычитания меньшего из большего с последующим присвоением результату знака большего по модулю числа. Другими словами, операция сопровождается большим количеством проверок условий и выработкой признаков, в соответствии с которыми выби­рается то или иное действие.

Альтернативным вариантом является представление чисел со знаком в дополнительном коде. Идея построения дополнительно­го кода достаточно проста: на оси целых положительных чисел, помещающихся в машинное слово (0 --65535), сместим положение «0» на середину интервала; числа, попадающие в первую половину (0 -32767) будем считать положительными, а числа из второй половины (32768 - 65535) - отрицательными. В этом случае судить о знаке числа можно будет по его величине и в явном виде выделе­ние знака не потребуется. Например, 100000000000001₂ = 32769₁₀ является кодом отрицательного числа, а 000000000000001₂ = 1₁₀ -кодом положительного. Принадлежность к интервалу кодов поло­жительных или отрицательных чисел видна по состоянию старше­го бита - у кодов положительных чисел его значение «0», отрица­тельных - «1». Это напоминает представление со знаком, но не является таковым, поскольку используется другой принцип коди­рования. Его применение позволяет заменить вычитание чисел их суммированием в дополнительном коде.

Дополнением (D) k-разрядного целого числа Z в системе счисления р называется величина D(Z_P, k) = p^k - Z.

Данную формулу можно представить в ином виде: D(Z_P, k) = = ((P^k - 1) - Z) + 1. Число - 1 согласно , состоит из k наи­больших в данной системе счисления цифр (р - 1), например, 9999₁₀, FFF16 или 1111111₂. Поэтому (p^k - 1) - Z можно получить путем дополнения до р-1 каждой цифры числа Z и последующим прибавлением к последнему разряду 1.

Так как в двоичной системе счисления дополнением 1 является 0, а дополнением 0 является 1, построение D(Z₂, k) сводится к ин­версии данного числа, т.е. замена нулей единицами и единиц ну­лями, и прибавлением 1 к последнему разряду. Другими словами, дополнение двоичного числа формируется в два этапа:

•      строится инвертированное представление исходного числа;

•      к инвертированному представлению прибавляется 1 по прави­лам двоичной арифметики.

Дополнительный код (DK) двоичных целых чисел строится по следующим правилам:

Ø для Z2 > 0 дополнительный код совпадает с самим число

Ø   для Z2 < О дополнительный код совпадает с дополнением модуля числа.

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

Подобным же образом число из дополнительного кода перево­дится в прямой при выполнении операции умножения; перемно­жаются всегда положительные числа .Знаковый бит результата, очевидно, будет содержать 0, если знаки чисел одинаковы, и 1 при противоположных знаках. Над множеством целых чисел со знаком операция деления не определена, поскольку в общем случае ее результатом будет вещественное число. Однако допустимыми являются операции целочисленного деления и нахождения остатка от целочисленного деления (те, что обозначены div и mod). Точнее, значения обеих величин находятся одновременно в одной процедуре, которая в конечном счете сводится к последовательности вычитаний или, еще точнее, сложений с дополнительным кодом делителя. Примем обо значения: - делимое; делитель; L - результат целочисленного деления  на  R- остаток от целочисленного деления  на . Эти величины связаны между собой довольно очевидным соотношением: , из которого следует алгоритм нахождения значений L и R для за­данных  и  .

Таким образом, операции div и mod, как, впрочем, и операция умножения, реализуются программно, т.е. сводятся к последова­тельности небольшого числа более простых действий. При этом уровень программной реализации может быть различным. Если реализация выполнена на уровне команд центрального процессо­ра, то эти операции оказываются доступны из любого приложения (любой прикладной программы). Если же в системе команд про­цессора эти микропрограммы отсутствуют, их приходится описы­вать в виде процедур в самих приложениях и, следовательно, они будут доступны только в этих приложениях.