Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Кодирование числовой информации: позиционные и непозиционные системы счисления. Двоичная система счисления
1.2. Перевод чисел из двоичной системы счисления в систему счисления с основанием 2n
1.3. Перевода чисел из систем счисления с основанием 2n в двоичную систему
2. Арифметические операции в позиционных системах счисления
2.1. Арифметические операции в двоичной системе счисления
2.2. Арифметические операции в восьмеричной системе счисления
3. Компьютерное представление чисел
3.1. Представление целых чисел в формате с фиксированной запятой
3.2. Представление вещественных чисел в формате с плавающей запятой
Рассмотрим, как кодируется числовая информация. С числами связано важное понятие системы счисления. Система счисления – способ наименования и изображения чисел с помощью знаков (символов), имеющих определенные количественные значения. Все системы счисления делятся на две группы:позиционные и непозиционные системы счисления. Для записи чисел в различных системах счисления используется некоторое количество отличных друг от друга знаков.
В позиционной системе счисления количественное значение каждой цифры зависит от ее места (позиции) в числе. В непозиционной системе счисления цифры не меняют своего количественного значения при изменении их расположения в числе.
Наиболее известным примером непозиционной системы счисления является римская. В качестве цифр этой системе счисления используется семь знаков:I(1), V(5), X(10), L(50), C(100), D(500), M(1000). Значение цифры не зависит от ее положения в числе. Например, в числе ХХХ (30) цифра Х встречается трижды и в каждом случае обозначает одну и ту же величину – число 10, три числа по 10 в сумме дают 30.
Первая позиционная система счисления была придумана еще в Древнем Вавилоне, причем вавилонская нумерация была шестидесятеричной, то есть в ней использовалось шестьдесят цифр! Интересно, что до сих пор при измерении времени мы используем основание, равное 60. Наиболее распространенными в настоящее время позиционными системами счисления являются десятичная, двоичная, восьмеричная и шестнадцатеричная. Каждая позиционная система счисления имеет определенный алфавит и основание. Десятичная система счисления имеет алфавит, который состоит из десяти всем известных арабских цифр от 0 до 9 и основание, равное 10, восьмеричная – восемь цифр от 0 до 7 и основание 8, шестнадцатеричная – десять цифр от 0 до 9 и шесть первых заглавных букв латинского алфавита A,B,C,D,E,F.
Примеры чисел, представленных в позиционных системах счисления: 975,4810, 348, 41D16, 101102. Позиционный характер этих систем легко понять на примере развернутой формы записи одного из чисел:
975,4810=9х102+7х101+5+100+4х10-1+8х10-2
Количество различных знаков, используемых для изображения числа в позиционной системе счисления, называется основанием системы счисления.
В общем случае запись любого смешанного числа в системе счисления с основанием q будет иметь вид (формула 1):
Аq=an-1 • qn-1 + an-2 • qn-2 + …+ a0 • q0 +a-1 • q-1 + a-2 • q-2 + …+ a-m • q-m
Здесь Аq – само число, q – основание системы счисления, а – цифры данной системы счисления, n – число разрядов целой части числа, m – число разрядов дробной части числа.
Существуют алгоритмы перевода чисел из одних систем счисления в другие.
1.1 Алгоритм перевода десятичного числа в систему счисления с основанием q и обратно
Для перевода смешанного числа следует переводить его целую и дробную части отдельно:
1. Для перевода целой части (или простого целого) числа необходимо разделить его на основание системы счисления q и продолжать делить частные от деления до тех пор, пока частное не станет равным 0. Значения получившихся остатков, записанные в обратной последовательности, образуют целую часть числа с основанием q.
2. Для перевода дробной части числа (или числа, у которого «0» целых) необходимо умножить ее на основание q. Затем, отбрасывая у результата целую часть, продолжать процесс умножения до тех пор, пока дробная часть произведения не окажется равной нулю или не будет достигнута нужная точность дроби. Целые части произведений, записанные после запятой в прямой последовательности (начиная с первого), образуют дробную часть числа в системе счисления с основанием q.
Рассмотрим перевод смешанного числа из десятичной в двоичную систему счисления на примере числа 46,625.
1. Переводим целую часть числа:
Остаток
46:2=23 0
23:2=11 1
11:2=5 1
5:2=2 1
2:2=1 0
1:2=0 1
Запишем остатки, начиная с последнего - 101110, т.е. 4610=1011102
2. Переводим дробную часть числа:
0,625 × 2=1,250
0,250 × 2=0,500
0,500 × 2=1,000
Запишем целые части произведений, начиная с первого – 0,101, т.е. 0,62510 = 0,1012
Ответ: 46,62510 = 101110,1012
Для того чтобы выполнить обратное преобразование, необходимо число в системе счисления с основанием q записать в развернутом виде и выполнить необходимые вычисления.
Рассмотрим перевод двоичного числа 101110,1012 в десятичное число. Для этого запишем это двоичное число в развернутом виде, используя формулу:
Аq=an-1 • qn-1 + an-2 • qn-2 + …+ a0 • q0 +a-1 • q-1 + a-2 • q-2 + …+ a-m • q-m
и выполним необходимые вычисления.
Основание системы: q=2, число разрядов целой части числа: n=6, число разрядов дробной части числа: m=3, цифры двоичной системы счисления а представлены нулем или единицей.
101110,1012=1×25+0×24+1×23+1×22+1×21+0×20+1×2-1+0×2-2+1×2-3 =32+0+8+4+2+0+1/2+0+1/8=46,62510
Рассмотрим перевод шестнадцатеричного числа 9D,116 в десятичное:
9D,116=9×161+13×160+1×16-1=144+13+1/16=157,062510
1.2. Алгоритм перевода чисел из двоичной системы счисления в систему счисления с основанием 2n
Для того чтобы записать смешанное двоичное число в системе счисления с основание q=2n, нужно:
1. Целую часть данного двоичного числа разбить справа налево, а дробную – слева направо на группы по n цифр в каждой. Если в последних левой и/или правой группах окажется меньше n разрядов, то их надо дополнить слева и/или справа нулями до нужного числа разрядов.
2. Рассмотреть каждую группу как n-разрядной двоичное число и записать ее соответствующей цифрой в системе счисления с основанием q=2n.
Рассмотрим перевод смешанного двоичного числа 111100101,01112 в восьмеричную систему счисления.
Разбиваем целую и дробную части двоичного числа на триады и над каждой из них записываем соответствующую восьмеричную цифру:
|
7 4 5 , 3 4 111 100 101, 011 100 |
Ответ: 111100101,01112 = 745,348
1.3. Алгоритм перевода чисел из систем счисления с основанием 2n в двоичную систему
Для того чтобы записать смешанное число, записанное в системе счисления с основание q=2n, перевести в двоичную систему счисления, нужно каждую цифру этого числа заменить ее n-значным эквивалентом в двоичной системе счисления.
Рассмотрим перевод шестнадцатеричного числа 4AC,3516 в двоичную систему счисления.
В соответствии с алгоритмом запишем:
Ответ: 4AC,3516 = 10010101100,001101012
Арифметические операции во всех позиционных системах счисления выполняются по одним и тем же правилам, что и в десятиной системе, так как они основываются на правилах выполнения действий над соответствующими многочленами. При этом нужно только пользоваться теми таблицами сложения и умножения, которые соответствуют данному основанию q системы счисления.
2.1. Арифметические операции в двоичной системе счисления
Сложение производится согласно таблице сложения, которая для двоичных чисел имеет вид:
При сложении двух единиц происходит переполнение разряда и в данном разряде остается 0, а 1 переносится в следующий старший разряд. Примеры сложения двоичных чисел:
Вычитание производится согласно таблице вычитания, которая для двоичных чисел имеет вид:
В основе умножения лежит таблица умножения одноразрядных двоичных чисел:
Примеры умножения двоичных чисел:
|
|
|
1 |
1 |
0 |
|||||||
|
|
х |
|
1 |
1 |
|||||||
|
|
|
1 |
1 |
0 |
|||||||
|
|
1 |
1 |
0 |
|
|||||||
|
1 |
0 |
0 |
1 |
0 |
|||||||
|
|
|
|
1 |
1 |
0 |
1 |
1 |
, |
0 |
1 |
0 |
|
|
|
х |
|
|
|
|
|
|
1 |
0 |
1 |
|
|
|
|
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
|
|
|
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
|
||
|
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
Операция деление производится по тем же правилам, как и деление в десятичной системе счисления. В двоичной системе деление выполняется особенно просто, так как очередная цифра частного может быть только нулем или единицей.
Примеры деления двоичных чисел:
2.2. Арифметические операции в восьмеричной системе счисления
Таблицы сложения и умножения для системы счисления с основанием q=8:
|
+ 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 10 2 2 3 4 5 6 7 10 11 3 3 4 5 6 7 10 11 12 4 4 5 6 7 10 11 12 13 5 5 6 7 10 11 12 13 14 6 6 7 10 11 12 13 14 15 7 7 10 11 12 13 14 15 16 |
х 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 2 0 2 4 5 10 12 14 16 3 0 3 6 11 14 17 22 25 4 0 4 10 14 20 24 30 34 5 0 5 12 17 24 31 36 43 6 0 6 14 22 30 36 44 52 7 0 7 16 25 34 43 52 61
|
Примеры операций с числами в восьмеричной системе счисления:
3) 17408 х 32,58 = 63462,528 4) 462,28 : 318= 14,28
3. Компьютерное представление чисел
Информация в памяти ЭВМ записывается в форме цифрового двоичного кода. С этой целью ЭВМ содержит большое количество ячеек памяти и регистров (от лат. regestum – внесенное, записанное) для хранения двоичной информации. Ячейка – это часть памяти, вмещающая в себя информацию, доступную для обработки отдельной командой процессора. Наибольшую последовательность бит, которую компьютер может обрабатывать как единое целое (содержимое ячейки памяти), называют машинным словом.
Элементарная ячейка памяти ЭВМ имеет длину 8 бит (1 байт). Каждый байт имеет свой номер (его называют адресом). Длина машинного слова зависит от разрядности процессора и может быть равной 16, 32, 64 битам и т.д. Адрес машинного слова в памяти компьютера равен адресу младшего байта, входящего в это слово. Машинное слово, состоящее из 16 бит (2-х байт) представлено на рис.1. Разряды нумеруются справа налево, начиная с 0. Самый левый является старшим разрядом (на рисунке с номером 15), самый правый – младшим (на рисунке с номером 0).
|
15 |
14 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
|
бит |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
байт |
байт |
||||||||||||||
|
Слово |
Рис. 2. Бит, байт, слово
В вычислительной технике используются два формата представления двоичных чисел:
- с фиксированной запятой (точкой);
- с плавающей запятой (точкой).
Формат с фиксированной запятой применяется к целым числам, формат с плавающей запятой - к вещественным (действительным) числам.
3.1. Представление целых чисел в формате с фиксированной запятой
Множество целых чисел, представимых в памяти ЭВМ, ограничено. Диапазон значений зависит от размера ячеек памяти, используемых для их хранения.
Так в n-разрядной ячейке может храниться 2n различных значений целых чисел. Так в 8-разрядной ячейке может храниться 28=256 различных значений, в 16-разрядной – 216=65536 различных значений.
Целые числа могут представляться в компьютере без знака и со знаком.
Целые числа без знака. Обычно занимают в памяти компьютера один или два байта. Максимальное значение целого числа без знака (положительного числа) достигается в случае, когда во всех ячейках хранятся единицы. Для n-разрядного представления оно будет равно .Для 8-разрядной ячейки максимальное значение целого положительного числа достигается в случае, когда во всех ячейках хранятся единицы и равно. Минимальное число соответствует восьми нулям, хранящимся в восьми битах ячейки памяти, и равно нулю. Следовательно, в 8-разрядной ячейке диапазон изменения целых чисел без знака: от 0 до 255. В 16-разрядной ячейке - от 0 до 65535 (всего 65536 значений).
Так, число 111000012 будет храниться в 8-разрядной ячейке памяти следующим образом:
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
В 16-разрядном представлении число 200610=111110101102 будет храниться следующим образом:
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
Итак, чтобы получить внутреннее представление целого числа без знака А, хранящегося в n-разрядном машинном слове, необходимо:
1) перевести число А в двоичную систему счисления;
2) полученный результат дополнить слева незначащими нулями до n разрядов.
Целые числа со знаком: прямой, обратный и дополнительный коды. Целые числа со знаком обычно занимают в памяти компьютера один, два или четыре байта. Для хранения целых чисел со знаком старший (левый) разряд в машинном слове отводится под знак числа (если число положительное, то в знаковый разряд записывается ноль, если число отрицательное – единица). Ровно половина из всех 2n чисел будут отрицательными; учитывая необходимость нулевого значения, положительных будет на единицу меньше.
Максимальное положительное число (с учетом выделения одного разряда на знак) для целых чисел со знаком в n-разрядном представлении равно .Минимальное отрицательное число (с учетом выделения одного разряда на знак) для целых чисел со знаком в n-разрядном представлении равно -.
Диапазоны значений целых чисел со знаком:
- в 8-разрядной ячейке: от -128 до 127;
- в 16-разрядной ячейке: от -32 768 до 32 767;
- в 32-разрядной ячейке: от -2 147 483 648 до 2 147 483 647.
Для представления отрицательного числа используется дополнительный код. Дополнительный код положительного числа совпадает с его прямым кодом.
Прямой код целого положительного числа может быть получен следующим образом: число переводится в двоичную систему счисления, а затем его двоичную запись слева дополняют необходимым количеством нулей в соответствии с разрядностью машинного слова. Например, прямой код числа 3710=1001012в 16-разрядной ячейке будет иметь вид 0000000000100101.
Для записи внутреннего представления целого число со знаком (-А) необходимо:
1) модуль числа записать в прямом коде в n двоичных разрядах;
2) получить обратный код числа, для этого значения всех бит инвертировать – все единицы заменить на нули и все нули заменить на единицы);
3) к полученному обратному коду прибавить единицу. Получим дополнительный код целого числа со знаком.
Например, внутреннее представление целого отрицательного числа -1607 в 16-разрядной ячейке запишется следующим образом: 1111 1001 1011 1001. Так как:
1) а) ½-1607½=160710=110010001112
б) прямой код в 16-разрядной ячейке:
0000 0110 0100 0111
2) обратный код:
1111 1001 1011 1000
3) дополнительный код (результат прибавления 1):
1111 1001 1011 1001 – это внутренне двоичное представление числа (-1607).
3.2. Представление вещественных чисел в формате с плавающей запятой
Числовые величины, которые могут принимать любые значения (целые и дробные) называются вещественными числами. В математике также используется термин «действительные числа». Решение большинства математических задач сводится к вычислениям с вещественными числами. Вещественные числа в памяти компьютера представляются в форме с плавающей точкой.
Форма с плавающей точкой использует представление вещественного числа А в виде произведения мантиссы m на основание системы счисления q в некоторой целой степени p, которую называют порядком:
А=m x qp
Например, число 139,76 можно записать в виде: 0,13976х103. Здесь m=0,13976 – мантисса, p=3 – порядок. Порядок указывает, на какое количество позиций и в каком направлении должна «переплыть», т.е. сместиться десятичная в мантиссе. Отсюда название «плавающая точка». Однако справедливы и следующие равенства:
139,76=13,976х101 = 1,3976х102 = 0,013976х104 = 13976 х10-2
Получается, что представление числа в форме с плавающей точкой неоднозначно? Чтобы не было неоднозначности, в ЭВМ используют нормализованное представление числа в форме с плавающей точкой. Мантисса в нормализованном представлении должна удовлетворять условию:
0.1q £m< 1q ,
то есть мантисса меньше единицы и первая значащая цифра - не ноль. Следовательно, для рассмотренного числа нормализованным представлением будет: 0,13976х103.
В разных типах ЭВМ применяются различные варианты представления чисел в форме с плавающей точкой. Для примера рассмотрим один из возможных.
Пусть в памяти компьютера вещественное число представляется в форме с плавающей точкой в двоичной системе счисления (q=2) и занимает ячейку размером 4 байта. В ячейке должна содержаться следующая информация о числе: знак числа, порядок и значащие цифры мантиссы. Вот как эта информация располагается в ячейке:
|
± маш. порядок |
М А Н |
Т И С |
С А |
1-й байт 2-й байт 3-й байт 4-й байт
В старшем бите 1-го байта хранится знак числа. В этом разряде 0 обозначает плюс, 1 – минус. Оставшиеся 7 бит первого байта содержат машинный порядок. В следующих трех байтах хранятся значащие цифры мантиссы.
Что такое машинный порядок? В семи двоичных разрядах помещаются двоичные числа в диапазоне от 0000000 до 1111111. В десятичной системе это соответствует диапазону от 0 до 127. Всего 128 значений. Знак порядка в ячейке не хранится. Но порядок, очевидно, может быть как положительным, так и отрицательным. Разумно эти 128 значений разделить поровну между положительными и отрицательными значениями порядка. В таком случае между машинным порядком и истинным (назовем его математическим) устанавливается следующее соответствие:
|
Машинный порядок |
0 |
1 |
2 |
3 |
… |
64 |
65 |
… |
125 |
126 |
127 |
|
Математический порядок |
-64 |
-63 |
-62 |
-61 |
… |
0 |
1 |
… |
61 |
62 |
63 |
Итак, машинный порядок смещен относительно математического на 64 единицы и имеет только положительные значения. Полученная формула записана в десятичной системе счисления. В двоичной системе счисления формула имеет вид:
При выполнении вычислений с плавающей точкой процессор это смещение учитывает.
Таким образом, из вышесказанного вытекает следующий алгоритм для получения представления действительного числа в памяти ЭВМ:
1) Перевести модуль данного числа в двоичную систему счисления;
2) Записать полученное двоичное число в нормализованном виде;
3) Определить машинный порядок с учетом смещения;
4) Учитывая знак заданного числа (0 – положительное; 1 – отрицательное), записать его представление в памяти ЭВМ.
Например, запишем внутреннее представление числа 139,76 в форме с плавающей точкой в 4-х байтовой ячейке:
1) Переведем десятичное 139,76 и запишем его 24-значащими цифрами:
139,7610 = 10001011,11000010100011112
2) Запишем полученное двоичное число в форме нормализованного двоичного числа с плавающей точкой:
10001011,11000010100011112 = 0,1000101111000010100011112 х101000,
где 0,1000101111000010100011112 – мантисса;
10 – основание системы счисления (210=102);
1000 – порядок (810=10002).
3) Определим машинный порядок:
Mq2 = 1000 + 1000000 = 1001000
4) Запишем представление числа в ячейке памяти:
|
01001000 |
10001011 |
11000010 |
10001111 |
Для того чтобы получить внутренне представление отрицательного числа -139,7610 достаточно в полученном выше представлении заменить в разряде знака числа 0 на 1. Никакого инвертирования, как для отрицательных целых чисел, здесь не происходит.
Задачи и упражнения
1. Переведите целые числа из десятичной системы счисления в двоичную, восьмеричную и шестнадцатеричную системы счисления:
а) 231 б) 564 в) 1023 г) 4096.
2. Переведите в десятичную систему счисления
а) двоичные числа: 10011101, 1100101001110, 1011110010101111;
б) восьмеричные числа: 321, 2367, 53621;
в) шестнадцатеричные числа: 3А, В14, 4А4С, А55DD.
3. Переведите десятичные дроби в двоичную, восьмеричную и шестнадцатеричную системы счисления: 0,5; 0,125; 0,654.
4. Переведите смешанные десятичные числа в двоичную, восьмеричную и шестнадцатеричную системы счисления, оставив пять знаков в дробной части нового числа:21,5; 432,54; 678,333.
5. Сложите, вычтите, умножьте и разделите двоичные числа 110101012 и 11102.
6. Выполните арифметические операции:
а) 1100000011,0112 х 101010111,12
б) 1510,28 – 1230,548
в) 3B3,816+38B,416
7. Получите двоичную форму внутреннего представления целых чисел 1689 и -1689 в 2-х байтовой ячейке.
8. Получите двоичную форму внутреннего представления действительных чисел 224,25 и -224,25 в формате с плавающей точкой в 4-х байтовой ячейке.
9. Запишите в десятичной системе счисления целое число, если его дополнительный код 1000000110101110.