Математические основы информатики

Представление целых чисел

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

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

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

При беззнаковом представлении все разряды ячейки отводятся под само число. При представлении со знаком самый старший (левый) разряд отводится под знак числа, остальные разряды — под собственно число. Если число положительное, то в знаковый разряд помещается О, если число отрицательное — 1. Очевидно, в ячейках одного и того же размера можно представить больший диапазон целых неотрицательных чисел в беззнаковом представлении, чем чисел со знаком. Например, в одном байте (8 разрядов) можно записать положительные числа от 0 до 255, а со знаком — только до 127. Поэтому, если известно заранее, что некоторая числовая величина всегда является неотрицательной, то выгоднее рассматривать ее как беззнаковую.

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

Представление целых положительных чисел

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

Максимально представимому числу соответствуют единицы во всех разрядах ячейки (двоичное число, состоящее из k единиц). Для k-разрядного представления оно будет равно 2^к - 1. Минимальное число представляется нулями во всех разрядах ячейки, оно всегда равно нулю. Ниже приведены максимальные числа для беззнакового представления при различных значениях k:

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

Определение 1. Представление числа в привычной для человека форме «знак-величина», при которой старший разряд ячейки отводится под знак, остальные k - 1 разрядов — под цифры числа, называется прямым кодом.

Например, прямые коды двоичных чисел 11001₂ и -11001₂ для восьмиразрядной ячейки равны 00011001 и 10011001 соответственно. Положительные целые числа представляются в компьютере с помощью прямого кода. Прямой код отрицательного целого числа отличается от прямого кода соответствующего положительного числа содержимым знакового разряда. Но вместо прямого кода для представления отрицательных целых чисел в компьютере используется дополнительный код.

Отметим, что максимальное положительное число, которое можно записать в знаковом представлении в k разрядах, равно 2 - 1, что практически в два раза меньше максимального числа в беззнаковом представлении в тех же k разрядах.

Задание. Определите максимальное положительное кисло в восьмиразрядном и шестнадцатиразрядном знаковых способах представления чисел.

Решение. Максимальное положительное число в 8 битах равно 127 (2⁷ - 1), в 16 битах — 32767 (2¹⁵ - 1).            

Пример 1. Число 53 = 1101012 в восьмиразрядном представлении имеет вид:

Это же число 53 в 16 разрядах будет записано следующим образом:

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

Пример 2. Для числа 200 = 11001000₂ представление в 8 разрядах со знаком невозможно, так как максимальное допустимое число в таком представлении равно 127, а в беззнаковом восьмиразрядном представлении оно имеет вид:

Представление целых отрицательных чисел

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

!     В k-разрядной целочисленной компьютерной арифметике 2^к = 0.

Объяснить это можно тем, что двоичная запись числа 2^k состоит из одной единицы и k нулей, а в ячейку из k разрядов может уместиться только k цифр, в данном случае только k нулей. В таком случае говорят, что значащая единица вышла за пределы разрядной сетки.

Определение 2. k-разрядный дополнительный код отрицательного числа m — это запись в k разрядах положительного числа 2^k - |m|, где |m| — модуль отрицательного числа m, |m| < 2^k-1.

Разберемся, что и до чего дополнительный код дополняет. Дополнительный код отрицательного числа m — это дополнение модуля этого числа до 2^k   (или до нуля в k-разрядной арифметике): 

(2   - |m|) + |m| = 2^k  =0.

Алгоритм получения дополнительного k-разрядного кода отрицательного числа

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

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

3.  К полученному обратному коду, трактуемому как k-разрядное неотрицательное двоичное число, прибавить единицу.                                                                                 

Обратный код является дополнением исходного числа до числа 2^k - 1, состоящего из k двоичных единиц. Поэтому прибавление единицы к инвертированному коду позволяет получить его искомый дополнительный код.

Пример 3. Получим дополнительный код числа -52 для восьми- и шестнадцатиразрядной ячеек. 

Для восьмиразрядной ячейки:

0011 0100 — прямой код числа |-52| = 52;

1100 1011 — обратный код числа -52;

1100 1100 — дополнительный код числа -52. 

Для шестнадцатиразрядной ячейки: 

0000 0000 0011 0100 — прямой код числа |-52|; 

1111 1111 1100 1011 —обратный код числа -52; 

1111 1111 1100 1100 — дополнительный код числа-52.

Вопрос. Какое минимальное отрицательное число можно записать в k разрядах?

Ответ. Описанный выше алгоритм получения дополнительного кода для отрицательного числа знаковую единицу в левом разряде образует автоматически при |m| < 2 ^k-1 Если же 2 ^k-1 < |m| < 2 ^k , то попытка реализации данного алгоритма приведет к тому, что в левом разряде будет находиться цифра 0, соответствующая компьютерному представлению положительных чисел, что неверно.

Представим значение 2 ^k  - |m| в следующем виде: 

2^k - |m| = 2^k-1 + (2^k-1 - |m|).

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

Задание. Постройте   дополнительный   восьмиразрядный код для чисел -128, -127 и -0.

Решение. Ответы приведены в таблице ниже:

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

1111 1111₂ + 1 = 100000000₂ = 2^k = 0.   

Восстановить модуль исходного десятичного отрицательного числа по его дополнительному коду можно двумя способами.

Способ 1: (обратная цепочка преобразований): вычесть единицу из дополнительного кода, инвертировать полученный код и перевести полученное двоичное представление числа в десятичное.

Способ 2: по приведенному выше алгоритму построить дополнительный код для имеющегося дополнительного кода искомого числа и представить результат в десятичной системе счисления.

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

Способ 1:

1)  из дополнительного кода вычтем 1:

10010111 - 1 = 10010110 (получили обратный код);

2)  инвертируем полученный код: 01101001 (получили модуль отрицательного числа);

3)  переведем полученное двоичное значение в десятичную систему счисления:

01101001₂ = 2⁶ + 2⁵ + 2³ + 1 = 64 + 32 + 8 + 1 = 105. Ответ: -105.

Способ 2:

1)  инвертируем      имеющийся      дополнительный      код: 01101000;

2)  прибавим к результату 1: 01101000 + 1 = 01101001 (получили модуль отрицательного числа);

3)  переведем полученное двоичное значение в десятичную систему счисления:

01101001₂ = 2⁶ + 2⁵ + 2³ + 1 = 64 + 32 + 8 + 1 = 105.

Ответ: -105.   

Целые числа со знаком, представимые в k разрядах, принадлежат диапазону [-2 ^k-1 , 2 ^k-1 - 1], который не является симметричным относительно 0. Это следует учитывать при программировании. Если, например, изменить знак у наибольшего по модулю отрицательного числа, то полученный результат окажется уже не представимым в том же числе разрядов.

Ниже приведены значения границ диапазонов для знаковых представлений в ячейках с различной разрядностью: