Лекцция Системы счисления
.pdf
СИСТЕМЫ СЧИСЛЕНИЯ
Основные понятия и определения
Система счисления – совокупность приемов и правил наименования и обозначения чисел, позволяющих установить взаимно однозначное соответствие между любым числом и его представлением в виде конечного числа символов.
Таким образом, под системой счисления понимается способ представления любого числа с помощью некоторого алфавита символов, называемых цифрами.
Влюбой системе счисления выбирается алфавит, представляющий собой совокупность некоторых символов (слов или знаков), с помощью которого в результате каких-либо операций можно представить любое количество. Изображение любого количества называется числом, а символы алфавита – цифрами (от лат. cifra). Символы алфавита должны быть разными и значение каждого из них должно быть известно.
С давних времен для подсчетов и вычислений применялись самые различные системы счисления. Первые цифры (знаки для обозначения чисел) появились у египтян и вавилонян. В III тыс. до н.э. в Вавилоне возникла клинописная запись счета. Позднее появились другие способы записи счета, например, критская, латинская, арабская. Вавилонская система счета позволяла вести запись чисел в пределах 1 млн. и выполнять действия с простыми дробными числами. В V–IV вв. до н.э. на острове Крит применялась удобная для записи десятичная символика счета. У ряда народов (древние греки, сирийцы, финикияне) цифрами служили буквы алфавита. Аналогичная система применялась и в России до XVI в.
Древние римляне положили в основу алфавита счисления иероглифическое обозначение пальцев рук (все символы этой системы счисления можно изобразить с помощью пальцев рук). Ко времени расцвета римской культуры эти значки были заменены похожими на них латинскими. Этой системой пользовались в Средние века в Европе, её и сейчас часто применяют для обозначения глав, частей, разделов в различных документах, книгах, для обозначения месяцев и т.д.
ВДревнем Востоке довольно широко была распространена двенадцатеричная система, частично сохранившаяся и сейчас. Многие предметы (ножи, вилки, тарелки и т.д.) считают дюжинами. Число
1
месяцев в году – двенадцать. В английской системе мер: 1 фут = 12 дюймов, в денежной системе: 1 шиллинг = 12 пенсов. В Древнем Вавилоне существовала весьма сложная шестидесятеричная система. Она, как и двенадцатеричная система, в какой-то степени сохранилась до наших дней в системе измерения времени: 1 час = 60 мин, 1 мин = 60 с, в системе измерения углов: 1º = 60 мин, 1 мин = 60 с.
В современном мире наиболее распространенной является десятичная система счисления. Она возникла в Индии и была перенесена в Европу арабами в XIII в. Поэтому десятичную систему счисления стали называть арабской, а используемые для записи чисел цифры –
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 – арабскими.
Все системы счисления делятся на позиционные и непозицион-
ные.
Непозиционная система счисления – система, в которой символы, обозначающие то или иное количество, не меняют своего значения в зависимости от местоположения (позиции) в изображении числа.
Запись числа A в непозиционной системе счисления D может быть представлена выражением:
N
AD =D1 + D2 + ... + DN = Di,
i 1
где AD – запись числа A в системе счисления D; Di – символы системы.
Непозиционной системой счисления является, например, самая простая система с одним символом (палочкой). Для изображения ка- кого-либо числа в этой системе надо записать количество палочек, равное данному числу. Например, запись числа 12 в такой системе счисления будет иметь вид: ||||||||||||, где каждая «палочка» обозначает
1.Эта система неэффективна, так как форма записи очень громоздка.
Кнепозиционной системе счисления относится и римская система, запись чисел в которой осуществляется по следующим правилам:
1) если цифра слева меньше, чем цифра справа, то левая цифра вычитается из правой (IV: 1 < 5, поэтому 5 – 1=4, XL: 10 < 50, следовательно, 50 – 10=40);
2) если цифра справа меньше или равна цифре слева, то эти циф-
ры складываются (VI: 5 + 1=6, VIII: 5 + 1 + 1 + 1 = 8, XX: 10 + 10=20).
Так число 1964 в римской системе счисления имеет вид
MCMLXIV (М – 1000, СМ – 900, LX – 60, IV – 4), здесь «девятьсот»
2
получается посредством вычитания из «тысячи» числа «сто», «шестьдесят» – посредством сложения «пятидесяти» и «десяти», «четыре» – посредством вычитания из «пяти» «единицы».
В общем случае непозиционные системы счисления характеризуются сложными способами записи чисел и правилами выполнения арифметических операций. В настоящее время все наиболее распространенные системы счисления относятся к разряду позиционных.
Позиционная система счисления – это система, в которой значение цифры определяется ее местоположением (позицией) в изображении числа.
Упорядоченный набор символов (цифр) {a0, a1, ..., an}, используемый для представления любых чисел в заданной позиционной системе счисления, называют её алфавитом, число символов (цифр) алфавита p = n + 1 – её основанием, а саму систему счисления назы-
вают p-ичной.
Основание позиционной системы счисления – количество различных цифр, используемых для изображения чисел в данной системе счисления.
Самой привычной для нас является десятичная система счисле-
ния. Ее алфавит – {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, а основание p = 10, то есть в этой системе для записи любых чисел используется только десять разных символов (цифр). Эти цифры введены для обозначения первых десяти последовательных чисел, все последующие числа, начиная с 10, обозначаются уже без использования новых цифр. Десятичная система счисления основана на том, что десять единиц каждого разряда объединяются в одну единицу соседнего старшего разряда, поэтому каждый разряд имеет вес, равный степени 10. Следовательно, значение одной и той же цифры определяется её местоположением в изображении числа, характеризуемым степенью числа 10. Например, в изображении числа 222,22 цифра 2 повторяется пять раз. При этом первая слева цифра 2 означает количество сотен (ее вес равен 102); вторая – количество десятков (вес – 101), третья – количество единиц (вес – 100), четвертая – количество десятых долей единицы (вес – 10–1), пятая цифра – это количество сотых долей единицы (вес – 10–2), т.е. число 222,22 может быть разложено по степеням чис-
ла 10:
3
222.22 = 2∙102 + 2∙101 + 2∙100 + 2∙10–1 + 2∙10–2.
Соответственно, любое число N в позиционной системе счисления с основанием p может быть представлено в виде полинома от основания p (развернутая форма записи чисел):
N = anpn+an-1pn-1+ ... +a1p+a0+a-1p-1+a-2p-2+ ... ,
где N – число;
ai – коэффициенты (цифры числа);
p – основание системы счисления (p>1).
Обычно принято представлять числа в виде последовательности цифр (свернутая форма записи чисел):
N= anan-1 ... a1a0 . a-1a-2 ... .
Вэтой последовательности точка отделяет целую часть числа (коэффициенты при положительных степенях, включая нулевую степень) от дробной (коэффициенты при отрицательных степенях). Точка опускается, если нет отрицательных степеней (число целое).
Двоичная система счисления. В современной вычислительной технике, в устройствах автоматики и связи используется в основном двоичная система счисления, что обусловлено рядом преимуществ данной системы счисления перед другими системами. Так для её реализации нужны технические устройства лишь с двумя устойчивыми состояниями: одно из них обозначается 0, а другое – 1. Эти знаки называются двоичными цифрами, по-английски – binary digit или сокращенно bit (бит).
Одним битом могут быть выражены два понятия: 0 или 1 (да или нет, черное или белое, истина или ложь и т.п.). Если количество битов увеличить до двух, то уже можно выразить четыре различных понятия. Увеличивая на единицу количество разрядов в системе двоичного кодирования, мы увеличиваем в два раза количество значений, которое может быть выражено в данной системе, то есть общая фор-
мула имеет вид:
N = 2m,
где N – количество независимых кодируемых значений;
m – разрядность двоичного кодирования для данной системы. Так как в двоичной системе счисления используется две цифры: 0
и 1, то любое число может быть представлено в виде:
N = bnbn-1 ... b1b0 . b-1b-2 ... ,
где bi либо 0, либо 1.
4
Недостаток двоичной системы – быстрый рост числа разрядов, необходимых для записи больших чисел. Этот недостаток не имеет существенного значения для компьютера. Если же возникает необходимость кодировать информацию «вручную», например, при составлении программы на машинном языке, то используют восьмеричную или шестнадцатеричную системы счисления. Числа в этих системах читаются почти так же легко, как десятичные, требуют соответственно в три (восьмеричная) или в четыре (шестнадцатеричная) раза меньше разрядов, чем в двоичной системе (числа 8 и 16 – соответственно третья и четвертая степени числа 2), а перевод их в двоичную систему счисления и обратно осуществляется гораздо проще в сравнении с десятичной системой счисления.
Восьмеричная система счисления употребляется как вспомога-
тельная для записи информации в сокращенном виде. Используются восемь цифр: 0, 1, 2, 3, 4, 5, 6, 7. Для представления одной цифры восьмеричной системы используется три двоичных разряда (триада) (таблица 1).
Таблица 1 − Системы счисления
Двоичная |
Восьмеричная |
Десятичная |
Шестнадцатеричная |
|||
(основание 8) |
|
(основание 16) |
||||
(основание 2) |
(основание 10) |
|
||||
|
триады |
|
|
тетрады |
||
|
|
|
|
|
||
0 |
0 |
000 |
0 |
0 |
|
0000 |
1 |
1 |
001 |
1 |
1 |
|
0001 |
|
2 |
010 |
2 |
2 |
|
0010 |
|
3 |
011 |
3 |
3 |
|
0011 |
|
4 |
100 |
4 |
4 |
|
0100 |
|
5 |
101 |
5 |
5 |
|
0101 |
|
6 |
110 |
6 |
6 |
|
0110 |
|
7 |
111 |
7 |
7 |
|
0111 |
|
|
|
8 |
8 |
|
1000 |
|
|
|
9 |
9 |
|
1001 |
|
|
|
|
A |
|
1010 |
|
|
|
|
B |
|
1011 |
|
|
|
|
C |
|
1100 |
|
|
|
|
D |
|
1101 |
|
|
|
|
E |
|
1110 |
|
|
|
|
F |
|
1111 |
Шестнадцатеричная система счисления. Для изображения чи-
сел употребляют 16 цифр. Первые десять цифр этой системы обозначаются цифрами от 0 до 9, старшие шесть цифр – латинскими буква-
5
ми: 10 – A, 11 – B, 12 – C, 13 – D, 14 – E, 15 – F. Шестнадцатеричная система используется для записи информации в сокращенном виде. Для представления одной цифры шестнадцатеричной системы (таблица 1) счисления используется четыре двоичных разряда (тетрада).
Системы счисления используются для построения на их основе различных кодов в системах передачи, хранения и преобразования информации.
Перевод чисел из одной системы счисления в другую
При переводе чисел из десятичной системы счисления в си-
стему с основанием p > 1 обычно используют следующий алгоритм:
1)Если переводится целая часть числа, то она делится на p, после чего запоминается остаток от деления. Полученное частное вновь делится на p, остаток запоминается. Процедура продолжается до тех пор, пока частное не станет равным нулю. Остатки от деления на p выписываются в порядке, обратном их получению.
2)Если переводится дробная часть числа, то она умножается на p, после чего целая часть запоминается и отбрасывается. Вновь полученная дробная часть умножается на p и т.д. Процедура продолжается до тех пор, пока дробная часть не станет равной нулю. Целые части выписываются после двоичной запятой в порядке их получения. Результатом может быть либо конечная, либо периодическая двоичная дробь. Поэтому, когда дробь является периодической, приходится обрывать умножение на каком-либо шаге и довольствоваться приближенной записью исходного числа в системе с основанием p.
Перевод целых десятичных чисел в двоичную, восьмеричную и шестнадцатеричную системы осуществляется последовательным
делением десятичного числа на основание той системы, в которую оно переводится, до тех пор, пока не получится частное, меньшее этого основания. Число в новой системе записывается в виде остатков деления, начиная с последнего.
Пример. |
|
|
|
|
|
|
|
а) Перевести 18110 → «8» с.с. |
б) Перевести 62210 → «16» с.с. |
||||||
181 |
8 |
|
|
622 |
16 |
|
|
176 |
22 |
8 |
|
48 |
38 |
16 |
|
5 |
16 |
2 |
|
142 |
32 |
2 |
|
|
6 |
|
|
128 |
6 |
|
|
Результат: 18110 = 2658. |
14 |
|
|
|
|||
|
|
|
|
Результат: 62210 = 26E16. |
|||
6
Перевод правильных дробей из десятичной системы счисления
вдвоичную, восьмеричную и шестнадцатеричную системы счис-
ления. Для перевода правильной десятичной дроби в другую систему эту дробь надо последовательно умножать на основание той системы,
вкоторую она переводится. При этом умножаются только дробные части. Дробь в новой системе записывается в виде целых частей произведений, начиная с первого.
Пример. Перевести 0.312510 → «8» с.с.
0 3125 8
Замечание. Конечной десятичной дроби в другой системе счисления может соответствовать бесконечная (иногда периодическая) дробь. В этом случае количество знаков в представлении дроби в новой системе берется в зависимости от требуемой точности.
Пример. Перевести 0.6510 → «2» с.с. Точность − 6 знаков.
0 |
|
65 2 |
Результат: |
|
|
||||
|
|
|
|
0.6510 → 0.10(1001)2. |
1 |
|
3 |
2 |
|
|
|
|||
0 |
|
6 |
2 |
|
1 |
|
2 |
2 |
|
0 |
|
4 |
2 |
|
0 |
|
8 |
2 |
|
1 |
|
6 |
2 |
|
|
|
… |
|
|
Для перевода неправильной десятичной дроби в систему счисления с недесятичным основанием необходимо отдельно перевести
целую часть и отдельно дробную. |
|
|
|
|
||||||
Пример. Перевести 23.12510 → «2» с.с. |
|
|
||||||||
1) Переведем целую часть |
2) Переведем дробную часть |
|||||||||
23 |
2 |
|
|
|
|
|
0 |
125 2 |
|
|
|
22 |
11 |
2 |
|
|
|
0 |
250 2 |
||
1 |
10 |
5 |
2 |
|
|
0 |
500 2 |
|||
|
|
1 |
4 |
2 |
2 |
|
1 |
000 |
|
|
|
|
|
|
|
|
|
Таким образом, 2310 = 101112; |
|||
|
|
|
1 |
2 |
1 |
|
||||
|
|
|
|
0 |
|
|
0,12510 = 0.0012. |
|
||
|
|
|
|
|
|
|
|
|
|
|
Результат: 23.12510 = 10111.0012. |
|
|
|
|
||||||
7
Необходимо отметить, что целые числа остаются целыми, а правильные дроби – дробями в любой системе счисления.
При переводе чисел из системы счисления с основанием p в де-
сятичную систему счисления необходимо пронумеровать разряды целой части справа налево, начиная с нулевого, и в дробной части, начиная с разряда сразу после запятой слева направо (начальный номер – 1). Затем вычислить сумму произведений соответствующих значений разрядов на основание системы счисления в степени, равной номеру разряда. Это и есть представление исходного числа в десятичной системе счисления.
Пример.
а) Перевести 10101101.1012 → «10» с.с.
10101101.1012 = 1∙27 + 0∙26 + 1∙25 + 0∙24 + 1∙23 + 1∙22 + 0∙21 + 1∙20 + 1∙2−1 + 0∙2−2 + 1∙2−3 = 173.62510;
б) Перевести 703.048 → «10» с.с.
703.048 = 7∙82 + 0∙81 + 3∙80 + 0∙8−1 + 4∙8−2 = 451.062510;
в) Перевести B2E.416 → «10» с.с.
B2E.416 = 11∙162 + 2∙161 + 14∙160 + 4∙16−1 = 2862.2510.
Замечание. Очевидно, что если в каком-либо разряде стоит нуль, то
соответствующее слагаемое можно опускать. Например,
1000011111.0101(2)=1 29 + 1 24 + 1 23 + 1 22 + 1 21 + 1 20 + 1 2-2 + 1 2-4 = 512 + 16 + 8 + 4 + 2 + 1 + 0,25 + 0,0625 = 543,3125(10).
Если необходимо перевести число из двоичной системы счис-
ления в систему счисления, основанием которой является сте-
пень двойки, достаточно объединить цифры двоичного числа в группы по столько цифр, каков показатель степени, и использовать приведенный ниже алгоритм. Например, если перевод осуществляется в восьмеричную систему, то группы будут содержать три цифры (8 = 23). Итак, в целой части будем производить группировку справа налево, в дробной – слева направо. Если в последней группе недостает цифр, дописываем нули: в целой части – слева, в дробной – справа. Затем каждая группа заменяется соответствующей цифрой новой системы.
Для перевода восьмеричного или шестнадцатеричного числа в двоичную форму достаточно заменить каждую цифру этого числа соответствующим трехразрядным двоичным числом (триадой) или четырехразрядным двоичным числом (тетрадой) (таблица 1), при этом отбрасывают ненужные нули в старших и младших разрядах.
8
Пример. |
|
|
|
|
|
||
а) |
3 |
0 |
5 |
. 4 |
8 |
= 11000101.1 . |
|
|
|
|
|
|
|
2 |
|
|
011 |
000 |
101 |
100 |
|
||
б) |
7 |
B |
2 |
|
. |
E |
16 = 11110110010.1112. |
|
|
|
|
|
|
||
|
0111 |
1011 |
0010 |
1110 |
|||
Для перехода от двоичной к восьмеричной или шестнадцате-
ричной системе поступают следующим образом: двигаясь от точки влево и вправо, разбивают двоичное число на группы по три (четыре) разряда, дополняя, при необходимости, нулями крайние левую и правую группы. Затем триаду (тетраду) заменяют соответствующей восьмеричной (шестнадцатеричной) цифрой.
Пример.
а) Перевести 1101111001.11012 → «8» с.с.
001 |
101 |
111 |
001. |
110 |
100 |
2 |
= 1571.648. |
|
|
|
|
|
|
||
1 |
5 |
7 |
1 |
6 |
4 |
|
|
б) Перевести 111111011.1001112 → «16» с.с.
0111 |
1111 |
1011 |
.1001 |
1100 |
= 7FB.9C16. |
|
|
|
2 |
||
7 |
F |
B |
9 |
C |
|
Перевод из восьмеричной в шестнадцатеричную систему и обратно осуществляется через двоичную систему с помощью триад и тетрад.
Пример. Перевести 175.248 → «16» с.с.
1 |
7 |
5 . |
2 |
4 |
0111 |
1101. |
0101 |
= 7D.516 |
|
|
|
|
|
8 = 1111101.01012 = |
2 |
||
001 |
111 |
101 |
010 |
100 |
7 |
D |
5 |
|
Результат: 175.248 = 7D.516.
Выполнение арифметических операций
Арифметические операции над числами в любой позиционной системе счисления производятся по тем же правилам, что и в десятичной системе, так как все они основаны на правилах выполнения действий над соответствующими полиномами. При этом нужно только пользоваться теми таблицами сложения и умножения, которые имеют место при данном основании p системы счисления.
Правила выполнения арифметических действий над двоичными, восьмеричными и шестнадцатеричными числами задаются соответствующими таблицами сложения и умножения [1]. В таблице 2 показаны правила для двоичных чисел.
9
Таблица 2 Основные арифметические операции
Двоичное сложение |
Двоичное вычитание |
Двоичное умножение |
0+0=0 |
0–0=0 |
0 0=0 |
0+1=1 |
1–0=1 |
0 1=0 |
1+0=1 |
1–1=0 |
1 0=0 |
1+1=10 |
10–1=1 |
1 1=1 |
При сложении двоичных чисел в каждом разряде производится сложение цифр слагаемых и переноса из соседнего младшего разряда, если он имеется. При этом необходимо учитывать, что 1+1 дают нуль в данном разряде и единицу переноса в следующий.
Пример. Выполнить сложение двоичных чисел.
а) X = 1101, Y = 101. |
|
||
|
1 1 |
← единицы переноса |
|
X = |
1101 |
|
|
|
+ |
|
|
Y = |
|
101 |
|
X+Y = |
10010 |
|
|
Результат: 1101 + 101 = 10010. |
|||
б) X = 1101, Y = 101, Z = 111. |
|||
|
1 |
← единицы переноса |
|
|
111 |
|
|
X = |
1101 |
|
|
|
+ |
|
|
Y = |
101 |
|
|
|
+ |
|
|
Z = |
|
111 |
|
X+Y+Z = |
11001 |
|
|
Результат: 1101 + 101 + 111 = 11001.
При вычитании двоичных чисел в данном разряде при необходимости занимается 1 из старшего разряда. Эта занимаемая 1 равна двум 1 данного разряда.
Пример. Заданы двоичные числа X =10010 и Y=101. Вычислить X–Y.
10