Лекция №3 Системы счисления. Методы перевода.
План лекций:
позиционные и непозиционные системы счисления;
порождение целых чисел в позиционных системах счисления;
Соответствие чисел в различных системах счисления;
двоичная система счисления;
перевод чисел из одной системы счисления в другую;
арифметические операции в позиционных системах счисления.
Система счисления– совокупность приемов и правил для записи чисел цифровыми знаками или символами. Способ записи чисел цифровыми знаками существует бесчисленное множество. Системы счисления делятся на позиционные и непозиционные. Самый простой способ записи чисел может быть описан выражением
где АВ– запись числа А в системе счисления В; (0)
Вi– символы системы, образующие базу В = {B1,B2, . . . , Bk}.
По этому принципу построены непозиционные системы счисления.
В непозиционныхсистемах вес цифры (т.е. тот вклад, который она вносит в значение числа) не зависит от ее позиции в записи числа. (Непозиционная система счисления– система, для которой значение символа не зависит от его положения в числе). Принцип построения таких систем не сложны. Для их образования используют в основном операции сложения и вычитания. Примером такой системы счисления является римская система, использующая набор следующих символов:I,X,V,L,C,D,Mи т.д., которые соответствуют следующим величинам:I(1)V(5)X(10)L(50)C(100)D(500)M(1000).
В ней несколько чисел приняты за основные (например, I,V,X), а остальные получаются из основных путем сложения (какVI,VII) или вычитания (какIV,IX). Например, число ХХХII (тридцать два) вес цифры Х в любой позиции равен просто десяти. ЧислоCCXXXII(двести тридцать два) состоит из двух сотен, трех десятков и двух единиц. В римской системе счисления цифры в числе записываются в порядке убывания слева направо в этом случае их значение складываются:
XXVIIозначает 10+10+5+1+1=27;
MMMDозначает 1000+1000+1000+500=3500;
MDCCLXVII=1000+500+100+100+50+10+5+1+1=1767.
Если слева записана меньшая по значению цифра чем справа то их значение уменьшается:
IVозначает 5-1=4
XIXозначает 10+(10-1)=19
MCMXCIVозначает 1000+(-100+1000)+(-10+100)+(-1+5)=1994
MCMXCVIII= 1000+(-100+1000)+(-10+100)+5+1+1+1=1998;
В этой системе существует отклонение от правила независимости значения цифры от положения в числе. В числах LХ и Х L символ Х принимает различные значения. В первом случае это +10, а во втором -10.
Если складывать и вычитать в такой системе еще можно без особого труда, то умножать очень сложно, а деление представляет собой почти непосильную проблему.
Вместе с тем в римской системе счисления есть одна важная идея: вклад буквы в число зависит не только от самой буквы, но и от порядка следования (позиции) букв в записи числа. Так, например, буква I дает вклад +1 в число VI и вклад -1 в число IV. Развитие этой идей приводит к современным позиционным системам нумерации.
Исторически первыми системами счисления были именно непозиционные системы. Одним из основных недостатков является трудность записи больших чисел. Запись больших чисел в таких системах либо очень громоздка, либо алфавит системы чрезвычайно велик.
В вычислительной технике непозиционные системы не применяются, но продолжают ограниченно использоваться для указания порядковых числительных (часов, столетий, номеров съездов или конференций и т.п.).
В общем случае системы счисления можно построить по следующему принципу:
АВ = а1В1 + а2В2 + . . . + а n Вn , (1)
где AB – запись числа А в системе счисления с основанием
Bi; ai – цифра (символ) системы счисления с основанием Bi ;
Bi – база, или основание системы.
Если предположить, что Bi = qi , то с учетом (1)
Bi = qi B i-1. (2)
Позиционная система счисления– система, удовлетворяющая равенству (2). Естественная позиционная система счисления имеет место, еслиq – целое положительное число.
В позиционной системе счислениязначение цифры определяется ее положением в числе: один и тот же знак принимает различное значение. Например, в десятичном числе 555 первая цифра означает пять единицы, средняя – пять десятка, а левая – пять сотни.
Различие весов цифр в числе 555 становится очевидным, если это число записать в виде суммы 5*102+5*101+ 5*100, в этой записи число 10 – основание системы счисления. Любая позиционная система счисления характеризуется основанием.Основание (базис)естественной позиционной системы счисления – количество знаков или символов, используемых для изображения числа в данной системе. Основанием системы счисления может быть любое число, больше единицы. К числу таких систем относится современная десятичная система счисления (оснn=10).В ней для обозначения первых десяти чисел служат цифры 0,1,...9.
Несмотря на кажущуюся естественность такой системы, она явилась результатом длительного исторического развития. Возникновение десятичной системы счисления связывают со счетом на пальцах.
В отличии от непозиционной системы счисления, позиционная система счисления применяется в ЭВМ. Для позиционной системы счисления справедливо равенство
(3) или
где Аq – произвольное число, записанное в системе счисления с основаниемq;
n+1,m- количество целых и дробных разрядов.
В позиционной системе счисления число может быть представлено в виде суммы произведений коэффициентов на степени основания системы счисления. Значение каждого знака в числе зависит от позиции, которую занимает знак в записи числа. Позиция цифры в числе – разряд. Именно поэтому такие системы счисления называют позиционными.
Примеры:
692(10)=6*102+ 9*101+ 2*100
23,43(10)= 2*101 + 3*100 + 4*10-1+ 3*10-2
101(2) = 1*22+ 0*21+ 1*20 =5(10)
11101,011(2)= 1*24+1*23+1*22+0*21+1*20+ 0*2-1+1*2-2+1*2-3=29,375(10)
112(3)= 1*32+ 1*31+ 2*30= 14(10)
15,2(8)= 1*81+5*80+2*8-1= 13,25(10)
A1F,4(16)=A*162+ 1*161+F*160+ 4*16-1= 2591,25(10)(А=10,F=15)
FF(16)= 15*161+ 15*160= 255(10)
Десятичная система счисления
Десятичная система счисления пришла из Индии, где она появилась не позднее VIв.н.э. В этой системе счисления всего десять цифр: 0,1,…9, но информацию несет не только цифра, но также и место, на котором она стоит. В числе 777, например, три одинаковые цифры обозначают количество и единиц, и десятков, и сотен. А вот в числе 700 первая цифра 7 обозначает число сотен, а две цифры 0 сами по себе вклад в число не дают, а нужны лишь для указания позиции цифры 7.
Двоичная (бинарная) система счисления.
В компьютерах применяется, как правило позиционная двоичная система счисления, т.е. система счисления с основанием 2. Использует две цифры 0 и 1, а также символы "+" и "–" для обозначения знака числа и запятую(точку) для разделения целой и дробной части. Процессор обрабатывает информацию, которая представлена в виде электрических сигналов. Поэтому очень удобно для процессора кодировать числа с помощью всего двух состоянии: есть напряжение или нет напряжения сигнала. Присутствие напряжения называют уровнем логической единицы, отсутствие – уровнем логического нуля. Почему логического? Потому что, на самом деле, мы подразумеваем 0 или 1 под уровнем напряжения. Если в вашей квартире отключили электричество, то можно сказать, что в розетке присутствует уровень логического нуля. Таким обр., процессор кодирует все числа с помощью всего двух знаков: 0 и 1. Эти знаки называются двоичными цифрами, по английский – binary digit или сокращенно bit (бит).
Двоичная система счисленияявляется минимальной системой, в которой реализуется принцип позиционности в цифровой форме записи числа. В двоичной системе счисления значение каждой цифры по месту при переходе от любого данного разряда к следующему старшему увеличивается вдвое. Одним битом могут быть выражены два понятия: 0 или 1. Если количество битов увеличить до двух, то уже можно выразить четыре различных понятия:
00 01 10 11
Тремя битами можно закодировать восемь различных значений:
000 001 010 011 100 101 110 111
Увеличивая на единицу количество разрядов в системе двоичного кодирования, мы увеличиваем в два раза количество значений, которое может быть выражено в данной системе, то есть общая формула имеет вид: N= 2m ,
где N– количество независимых кодируемых значений;
m- разрядность двоичного кодирования, принятая в данной системе.
Но предположим, что у нас в распоряжении всего две цифры 0 и 1. Можно ли выразить все числа с помощью всего двух цифр? Можно.
0 1 2 3 4 5 6 7 8 9 10 11 / - 10 я
0 1 10 11 100 101 110 111 1000 1001 1010 1011 / - 2 я
История развития двоичной системы счисления– одна из ярких страниц в истории арифметики. Официальное «рождение» двоичной арифметики связывают с именем Г.В. Лейбница: он в 1703 году опубликовал статью, в которой были рассмотрены правила выполнения всех арифметических операций над двоичными числами. Но Лейбниц не рекомендовал двоичную систему для практических вычислений; он считал ее полезной лишь при рассмотрении теоретических вопросов.
До начала 30 – годов двоичная система счисления оставалась вне поля зрения прикладной математики. Потребность в создании простых по конструкции и надежных счетных устройств и удивительная простота двоичной арифметики привели к более глубокому изучению двоичной системы как системы, пригодной для аппаратурной реализации.
Первые двоичные вычислительные механические машины были построены во Франции и Германии. Пионером в проектировании вычислительных устройств двоичного действия на электронно-ламповой основе является инженер Дж. Атанасов. Одновременно с ним (1937 г) двоичную машину, но на релейной (электромагнитной) основе спроектировал Дж. Стибиц. В 1941 году немецкий инженер К. Цузе построил сначала механическую, а затем и релейную двоичную вычислительную машину.
Утверждение двоичной арифметики в качестве обще принятой основы при конструировании ЭВМ с программным управлением состоялось под влиянием работы А. Беркса, Х. Гольдстайна и Дж фон Неймана «О проекте первой ЭВМ с хранимой в памяти программой». Работа была написана в 1946 году. В этой работе наиболее аргументировано обоснованы причины отказа от десятичной арифметики и перехода к двоичной системе счисления как основе машинной арифметики.
Недостаток двоичной системы - быстрый рост числа разрядов, необходимых для записи чисел. Двоичная система, удобная для компьютеров, для человека неудобна из-за ее громоздкости и непривычной записи.
Главное достоинство двоичной системы в том, что сложение и умножение цифр легко моделировать, позволяет создать специфические алгоритмы вычитания и деления двоичных чисел, наиболее подходящие для аппаратной реализации.
В компьютерах используются также восьмеричная и шестнадцатеричная системы счисления.
Восьмеричная система счисления
Восьмеричную систему счисления можно рассматривать как более короткий вариант записи двоичных чисел, тк как число восемь является степенью числа два. В этой системе счисления используется восемь цифр 0,1,….7, а так же символы "+" и "–" для обозначения знака числа и запятую (точку) для разделения целой и дробной частей числа. Широко использовалась в программировании в 1950-70 гг. К настоящему времени практически полностью вытеснена шестнадцатеричной системой счисления, однако функции перевода числа из десятичной системы в восьмеричную и обратно сохраняются в микрокалькуляторах и многих языках программирования.
Число в этой системе счисления записывается как сумма единиц, восьмерок, шестьдесят четверок и так далее. То есть веса соседних разрядов различаются в восемь раз. Точно также записываются и числа, меньшие единицы. В том случае разряды числа будут называться как восьмые, шестьдесят четвертые и так далее доли единицы.
Пример записи восьмеричного числа:
А8 = 125,468 = 1*82+ 2*81+5*80+ 4*8-1+ 6*8-2=6410+ 1610+ 510 +410/810+ 610/ 6410= 85,5937510
Во второй строке приведенного примера фактически осуществлен перевод числа, записанного в восьмеричной форме в десятичное представление того же самого числа. То есть мы фактически рассмотрели один из способов преобразования чисел из одной формы в другую.
Так как в формуле используются простые дроби, то возможен вариант, что точный перевод из одной формы представления в другую становится невозможным. В этом случае ограничиваются заданным количеством дробных разрядов.
Шестнадцатеричная система счисления
Эту систему счисления можно считать еще одним вариантом записи двоичного числа. В этой системе счисления используется 16 цифр. Здесь уже не хватает десяти цифр, поэтому приходится придумать недостающие шесть цифр. В их обычном смысле 0,1,2 … 9, а затемА=10, В=11, с=12, D=13,E=14,F=15. Также символы "+" и "–" для обозначения знака числа и запятую (точку) для разделения целой и дробной частей числа. Внедрена американской корпорациейIBM. Широко используется в программировании дляIBM– совместимых компьютеров. С другой стороны, в некоторых языках сохранились и следы использования этой системы счисления в прошлом. Например, в романских языках (испанском, французском и др.) числительные от 11 до 16 образуются по одному правилу, а от 17 до 19 – другому. А в русском языке известен пуд, равный 16 килограммам.
Пример: 89110– ?16
891 : 16 =55 остаток 11 (в 16-ой системе счисления 11=В)
55 : 16 = 3 остаток 7
3 : 16 = 0 остаток 3 Ответ: 37В16
Пример: 3Е5А116+ ?10
3Е5А116= 3*164 + Е*163 + 5*162+ А *161 + 1*160= 3*65536+14*4096+5*256+10*16+1=
196608+57344+1280+160+1=25539310
Естественным обобщением двоичной системы являются системы с основанием q= 8 иq= 16, наиболее употребляемые в программировании.
Взаимосвязь между системами счисления с основаниями q= 2, q= 8 и q= 16 определяетсядвумятеоремами:
Теорема 1.Для записи целого двоичного числа в системе счисления с основаниемq= 2n достаточно данное двоичное число разбить на грани справа налево (т.е. от младших разрядов к старшим) поnцифр в каждой грани. Затем каждую такую грань следует рассмотреть какn– разрядное двоичное число и записать его как цифру в системе с основаниемq= 2n.
Пример: число 1011000010001100102заменить равным ему числом восьмеричной системы счисления, т.е. системы с основаниемq= 23
101 100 001 000 110 010 1012= 581002= 48 0012= 18
5 4 1 0 6 2 0002= 08 1102= 680102 = 28
Итак 101 100 001 000 110 0102= 541 0628
Теорема 2. Для замены целого числа, записанного в системе с основаниемq= 2n, равным ему числом в двоичной системе счисления, достаточно каждую цифру данного числа заменитьn– разрядным двоичным числом.