Представление целых чисел
Представление целых чисел
Любое целое число можно рассматривать как вещественное, но с нулевой дробной частью, т. е. можно было бы ограничиться представлением в компьютере вещественных чисел и реализацией арифметических действий над ними. Однако для эффективного использования памяти, повышения скорости выполнения вычислений и введения операции деления нацело с остатком целые числа представляются специально для них предназначенными способами.
Введение специальных способов представления целых чисел оправдано тем, что достаточно часто в задачах, решаемых с помощью компьютера, многие действия сводятся к операциям над целыми числами. Например, в задачах экономического характера данными служат количества акций, сотрудников, деталей, транспортных средств и т. д., по своему смыслу являющиеся целыми числами. Целые числа используются и для обозначения даты и времени, и для нумерации различных объектов: элементов массивов, записей в базах данных, машинных адресов и т. п.
Для компьютерного представления целых чисел обычно используется несколько различных способов представления, отличающихся друг от друга количеством разрядов и наличием или отсутствием знакового разряда. Беззнаковое представление можно использовать только для неотрицательных целых чисел, отрицательные числа представляются только в знаковом виде.
При беззнаковом представлении все разряды ячейки отводятся под само число. При представлении со знаком самый старший (левый) разряд отводится под знак числа, остальные разряды — под собственно число. Если число положительное, то в знаковый разряд помещается О, если число отрицательное — 1. Очевидно, в ячейках одного и того же размера можно представить больший диапазон целых неотрицательных чисел в беззнаковом представлении, чем чисел со знаком. Например, в одном байте (8 разрядов) можно записать положительные числа от 0 до 255, а со знаком — только до 127. Поэтому, если известно заранее, что некоторая числовая величина всегда является неотрицательной, то выгоднее рассматривать ее как беззнаковую.
Говорят, что целые числа в компьютере хранятся в формате с фиксированной запятой.
Представление целых положительных чисел
Для получения компьютерного представления беззнакового целого числа в А-разрядной ячейке памяти достаточно перевести его в двоичную систему счисления и дополнить полученный результат слева нулями до k разрядов. Понятно, что существует ограничение на числа, которые мы можем записать в k-разрядную ячейку.
Максимально представимому числу соответствуют единицы во всех разрядах ячейки (двоичное число, состоящее из k единиц). Для k-разрядного представления оно будет равно 2к - 1. Минимальное число представляется нулями во всех разрядах ячейки, оно всегда равно нулю. Ниже приведены максимальные числа для беззнакового представления при различных значениях k:
При знаковом представлении целых чисел возникают такие понятия, как прямой, обратный и дополнительный коды.
Определение 1. Представление числа в привычной для человека форме «знак-величина», при которой старший разряд ячейки отводится под знак, остальные k - 1 разрядов — под цифры числа, называется прямым кодом.
Например, прямые коды двоичных чисел 110012 и -110012 для восьмиразрядной ячейки равны 00011001 и 10011001 соответственно. Положительные целые числа представляются в компьютере с помощью прямого кода. Прямой код отрицательного целого числа отличается от прямого кода соответствующего положительного числа содержимым знакового разряда. Но вместо прямого кода для представления отрицательных целых чисел в компьютере используется дополнительный код.
Отметим, что максимальное положительное число, которое можно записать в знаковом представлении в k разрядах, равно 2 - 1, что практически в два раза меньше максимального числа в беззнаковом представлении в тех же k разрядах.
Задание. Определите максимальное положительное кисло в восьмиразрядном и шестнадцатиразрядном знаковых способах представления чисел.
Решение. Максимальное положительное число в 8 битах равно 127 (27 - 1), в 16 битах — 32767 (215 - 1).
Пример 1. Число 53 = 1101012 в восьмиразрядном представлении имеет вид:
Это же число 53 в 16 разрядах будет записано следующим образом:
В обоих случаях неважно, знаковое или беззнаковое представление при этом используется.
Пример 2. Для числа 200 = 110010002 представление в 8 разрядах со знаком невозможно, так как максимальное допустимое число в таком представлении равно 127, а в беззнаковом восьмиразрядном представлении оно имеет вид:
Представление целых отрицательных чисел
Для представления в компьютере целых отрицательных чисел используют дополнительный код, который позволяет заменить арифметическую операцию вычитания операцией сложения, что существенно увеличивает скорость вычислений. Прежде чем вводить определение дополнительного кода, сделаем следующее важное замечание.
! В k-разрядной целочисленной компьютерной арифметике 2к = 0.
Объяснить это можно тем, что двоичная запись числа 2k состоит из одной единицы и k нулей, а в ячейку из k разрядов может уместиться только k цифр, в данном случае только k нулей. В таком случае говорят, что значащая единица вышла за пределы разрядной сетки.
Определение 2. k-разрядный дополнительный код отрицательного числа m — это запись в k разрядах положительного числа 2k - |m|, где |m| — модуль отрицательного числа m, |m| < 2k-1.
Разберемся, что и до чего дополнительный код дополняет. Дополнительный код отрицательного числа m — это дополнение модуля этого числа до 2k (или до нуля в k-разрядной арифметике):
(2 - |m|) + |m| = 2k =0.
Алгоритм получения дополнительного k-разрядного кода отрицательного числа
1. Модуль числа представить прямым кодом в k двоичных разрядах.
2. Значения всех разрядов инвертировать (все нули заменить на единицы, а единицы — на нули), получив, таким образом, k-разрядный обратный код исходного числа.
3. К полученному обратному коду, трактуемому как k-разрядное неотрицательное двоичное число, прибавить единицу.
Обратный код является дополнением исходного числа до числа 2k - 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| в следующем виде:
2k - |m| = 2k-1 + (2k-1 - |m|).
Здесь первое слагаемое 2 k-1 соответствует единице в левом знаковом разряде. То есть при представлении отрицательного числа m дополнительным кодом в самом левом (знаковом) разряде записывается знак отрицательного числа (единица), а в остальных разрядах — число 2 k-1 -|m|. Следовательно, минимальное отрицательное (максимальное по модулю) число m, которое можно представить в k разрядах, равно -2 k-1 (это ограничение и было приведено в определении 2).
Задание. Постройте дополнительный восьмиразрядный код для чисел -128, -127 и -0.
Решение. Ответы приведены в таблице ниже:
Отметим, что для числа -128 прямой код совпадает с дополнительным, а дополнительный код числа -0 совпадает с обычным нулем. При преобразовании обратного кода для числа -0 в его дополнительный код правила обычной двоичной арифметики нарушаются, а именно:
1111 11112 + 1 = 1000000002 = 2k = 0.
Восстановить модуль исходного десятичного отрицательного числа по его дополнительному коду можно двумя способами.
Способ 1: (обратная цепочка преобразований): вычесть единицу из дополнительного кода, инвертировать полученный код и перевести полученное двоичное представление числа в десятичное.
Способ 2: по приведенному выше алгоритму построить дополнительный код для имеющегося дополнительного кода искомого числа и представить результат в десятичной системе счисления.
Пример 4. Получим десятичное значение числа по его дополнительному коду 100101112
Способ 1:
1) из дополнительного кода вычтем 1:
10010111 - 1 = 10010110 (получили обратный код);
2) инвертируем полученный код: 01101001 (получили модуль отрицательного числа);
3) переведем полученное двоичное значение в десятичную систему счисления:
011010012 = 26 + 25 + 23 + 1 = 64 + 32 + 8 + 1 = 105. Ответ: -105.
Способ 2:
1) инвертируем имеющийся дополнительный код: 01101000;
2) прибавим к результату 1: 01101000 + 1 = 01101001 (получили модуль отрицательного числа);
3) переведем полученное двоичное значение в десятичную систему счисления:
011010012 = 26 + 25 + 23 + 1 = 64 + 32 + 8 + 1 = 105.
Ответ: -105.
Целые числа со знаком, представимые в k разрядах, принадлежат диапазону [-2 k-1 , 2 k-1 - 1], который не является симметричным относительно 0. Это следует учитывать при программировании. Если, например, изменить знак у наибольшего по модулю отрицательного числа, то полученный результат окажется уже не представимым в том же числе разрядов.
Ниже приведены значения границ диапазонов для знаковых представлений в ячейках с различной разрядностью: