Системы счисления и цифровые системы

1. Основы информатики © Казиев В.М. [email protected] Тема 3. Системы счисления и цифровые системы

2.

Алфавит Х из р символов и правила записи и обработки числовых величин с
помощью X называется системой счисления (нумерацией) с основанием р.
Число х в системе с основанием р обозначается как (х)р или хр.
Система счисления – система кодирования числовых величин, позволяющая
выполнять и декодирование, т.е. по любой количественной величине
однозначно находить его кодовое представление и по любой кодовой записи
– восстанавливать соответствующую ей числовую величину.
Все системы счисления строятся по общему принципу: определяется
величина р – основание системы, а любое число х записывается в виде
комбинации степеней веса р от 0–ой до n–ой степени следующим образом:
(x)10=xnpn+xn–1pn–1+...+x1p1+x0p0.
Наиболее используемые в информатике системы счисления, кроме,
естественно, десятичной системы – это:
1) двоичная, над алфавитом Х = {0,1};
2) восьмеричная, над Х = {0, 1, 2, 3, 4, 5, 6, 7};
3) шестнадцатеричная, над Х={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С, D, Е, F}, где
символы А, В, С, D, Е, F имеют десятичные веса 10, 11, 12, 13, 14, 15.

3.

4.

Процедура перевода десятичных чисел в р–ную систему счисления:
1) перевести отдельно целую часть числа х, для чего последовательно делить
сперва целую часть [х]10 , а затем все частные (получаемые при делении) на р
до тех пор, пока не получим в очередном частном число меньшее р;
изображение [х]p получается последовательным приписыванием к
последнему частному остатков от деления – от последнего до первого;
2) перевести отдельно дробную часть (мантиссу) числа то есть {x}10 , для чего
последовательно умножать сперва исходную мантиссу, а затем мантиссы
получаемых чисел на р до тех пор, пока не получим мантиссу, равную нулю,
или нужное количество цифр в {х}p; изображение {х}p получаются
приписыванием к целой части первого произведения второй такой же цифры
и т.д., до последней цифры целой части;
3) результат будет иметь вид: (х)р=[х]p,{х}p .
Пример. Найти: 12,810 =?2 . Переводим целую часть: 1210=11002;
переводим дробную часть (снизу подчеркнуты цифр идущие в изображение
мантиссы в двоичной системе): 0,8´2=1,6; 0,6´2=1,2; 0,2´2=0,4; 0,4´2=0,8;
0,810=0,1100110...2; результат перевода: 12,810 =1100,1100110011...2 .

5.

Для перевода из 2-ной в 8-ную и наоборот, из 2-ной в 16-ную и наоборот, из
8-ной в 16-ную и наоборот используется таблица вида:
10
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
0
1
-
ОСНОВАНИЕ СИСТЕМЫ
8
000
001
010
011
100
101
110
111
-
16
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

6.

При переводе в 8–ную систему (из нее), группируем в тройки биты, в 16–ую
(из нее) - в четверки битов. Можно добавлять, если нужно, незначащие нули
(слева от целой части и справа от мантиссы) или отбрасывать их.
Пример. Рассмотрим переводы в смешанных системах.
а) Из 2–ой системы в 8–ую (двоично–восьмеричное изображение):
101,101112 = 101 , 101 1102 = 5,568;
58 , 5 8 68
б) из 8–ой системы в 2–ую (восьмерично–двоичное изображение):
6,248 = 6 , 2
48 = 110,01012;
1102, 0102 1002
в) из 2–ой системы в 16–ую (двоично–шестнадцатеричное изображение):
101,101112 = 0101 , 1011 10002 = 5,В816;
516 , 11(В)16 816
г) из 16–ой системы в 2–ую (шестнадцатерично–двоичное изображение):
1A,F316 = 1
A , F
316 = 11010,111100112.
00012 10102, 11112 00112

7.

Сложение в двоичной системе счисления осуществляется по правилам:
0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 = 210 = 102 (1 - в старший разряд).
Таблица вычитания в двоичной системе счисления имеет вид:
0–0 =0, 1–0 =1, 1–1=0, 0–1=10 –1 = 1 (1 забираем у старшего разряда).
Таблица умножения в двоичной системе счисления имеет вид:
0 0 = 0, 0 1 = 0, 1 0 = 0, 1 1 = 1.
Таблица деления в двоичной системе счисления имеет вид:
0 : 0 = не определено, 1 : 0 = не определено, 0 : 1 = 0, 1 : 1 = 1.
Обратным кодом числа в системе с основанием р называется число в этой
системе, получаемое заменой цифры, символа в каждом разряде числа на его
дополнение до максимальной цифры в системе (то есть до р–1).
Дополнительный код = обратный код + единица в младшем разряде.
Пример. а) 10011 - двоичный код, 01100 -обратный, 01101- дополнительный;
б) 457 -восьмеричный код, 321 -дополнительный;
в) А9 - шестнадцатеричный код, 57 - дополнительный.
7

8.

Вычитание с помощью дополнительного кода: найти
дополнительный код вычитаемого такой же разрядности, как и
уменьшаемое и сложить этот код с уменьшаемым. Результатом
вычитания будет полученная сумма без учета старшего разряда
(отбрасывается).
Пример. Выполним вычитание напрямую и через сложение (через
дополнительный код):
как разность
через дополнительный код
_ 1101102
+ 1101102
101012
1010112
1000012
11000012 (старшая 1 – отброшена)

9.

Различия в представлении чисел в обычной и в машинной (n-разрядной)
арифметике (математике).
Точность в математике – понятие абстрактное и в практической
математике может быть иллюзия точности – если нет корректной
договорённости о возможных значениях неизбежных погрешностей в
рамках рассматриваемых вычислений и времени.
Так как диапазон n-разрядных чисел системы счисления с основанием p
находится в пределах |(x)p| pn–1, то для представления дробных чисел
этот диапазон ещё снижается, так как часть разрядов необходимо
отвести под изображение мантиссы. Таким образом, имеются так
называемые “зоны нечувствительности” форм представления чисел в
n-разрядных арифметиках.

10.

В 1937 году Конрадом Цузе для увеличения диапазона чисел,
представимых в арифметике двоичных чисел, повышения точности
этого представления чисел предложено представление чисел в
плавающей, нормализованной форме – число x представляется в виде:
x=m pk, где m – мантисса числа, k – целый порядок числа, p–1 |m|<1.
Пусть даны два числа x=m pk и y=n pl (k>l). Тогда можно проверить,
что результаты выполнения операций будут равны:
x+y=(m+n pl–k) pk ,
x—y=(m–n pl–k) pk ,
x y=(m n) pk+l ,
x/y=(m/n) pk–l ,
Если из n двоичных разрядов числа, m разрядов - мантисса, k –
порядок, один – знак числа и один – знак порядка (0 – плюс, 1 – минус),
диапазон «плавающих» чисел резко увеличивается (m+k+2=n):
–(0.111 . . . 1)2 (10)2+(111 . . . 1)2 x +(0.111 . . . 1)2 (10)2+(111 . . . 1)2
(многоточие соответствует k единицам).

11.

12.

Решение задач
1. Примеры переводов: 11012 = 1 23+1 22+0 21+1 20=8+4+1=1310 ,
1578 = 1 82+5 81+ 7 80=64+40+7=11110 ,
A6F16 = 10 256+6 16+15 1=267110 .
2. Найдём 29,2510=?8. Решение: 1) 2910=358; 2) 0,2510=0,28; 3) 29,2510=35,28.
3. Найдём 79,2610=?16. Решение: 1) 7910 = 4F16; 2) 0,2610 = 0,4016; 3) 79,2610 =
4F,416 . При переводе дробной части мы ограничились нахождением двух
значащих цифр после запятой, ибо перевод точно сделать невозможно.
4. Вычислить наибольшее и наименьшее 5-разрядное целое число в системе
счисления с основанием 3.
Решение: Таким образом, в системе счисления с основанием 4 и числом
разрядов 5 представим диапазон следующих чисел:
–242=1–35 (x)4 35–1=242.
12

13.

5. Найти все ошибки в утверждениях а) – г) и объяснить причины их
появления: а) 1111111111=210–1; б) 7777777777=7 1111111111=7 (210–1);
в) 7777777777=810–1; г) из б) и в) следует, что 7 210–6=810 или 230=7168(!).
Решение: В б) произошло «умышленное смешение» двоичной и десятичной
систем счисления в одном и том же равенстве.
6. Доказать, что максимальное 2n-разрядное двоичное число равно сумме
максимального n-разрядного троичного числа и квадрата максимального nразрядного четверичного числа.
Решение: По условию имеем, в скобках - количество повторений, например,
1…(4)…1=1111): 1…(2n)…1=2…(n)…2+3…(n)…32).
Отсюда получаем: 9…(2n)…9/9=2 9…(n)…9/9+(3 (9…(n)…9)/9)2.
Используя, например, формулу: 9…(n)…9=10n–1, (доказывается
математической индукции) получим: (102n–1)/9=2(10n–1)/9+((10n–1)/3)2
или 102n–1=2(10n–1)+(10n–1)2= 2(10n–1)+102n–2 10n+1=102n–1. Например,
максимальное 200-разрядное 2-чное равно сумме максимального 100разрядного 3-чного и квадрата максимального 100-разрядного 4-чного числа.
13

14.

7. Может ли при каком-то р количество (112)p+2 равняться количеству
(1214)p?
Решение: Пусть (112)p+2=(1214)p для некоторого p. Переведем в 10-ую
систему равенство. Получим: (p+2)2+p+2+2=p3+2p2+p+4 или
p2(p+1)=4(p+1). Так как p+1 0, то p2=4 или p=2. Так как в изображении
чисел равенства есть цифра 4, то p>4, т.е. найденное p - не подходит.
Ответ – нет.
8. Число x=(2420)р кратно числу y=(7)10. Найти основание системы р,
если 7<p<20.
Решение: Так как число 2420 в системе счисления с основанием р
можно записать в виде (2420)р=2р3+4р2+2р1=2р(р2+2р+1)=2р(р+1)2 и
по условию делится на простое число 7, то либо р, либо р+1 делится на
7, т.е. р=7а или р=7а–1, где а=1,2,... . Например, при 7<р<20 возможны
решения р=14, p=13 (при а=2).

15.

9. Сформулировать достаточный признак делимости числа (х)р на kую степень десятичного числа р.
Решение: Вспоминая десятичное разложение по степеням основания:
(x)p=(x0x1…xn)p= x0pn+x1pn–1+…+xn,
можно сформулировать следующий достаточный признак: число х
оканчивающееся на k<n+1 нулей делится на pk–1. Например, число
110002=2410 делится на 22=4, число 32008=166410 делится на 81.
10. Найти основание системы счисления, в которой выполнено
сложение (звездочки - цифры, возможно различные):
(33*5*)p+(1*643)p=(52424)p.
Решение: Так как во втором разряде (5+4) получается число меньшее
9, то основание системы будет меньше 9, а так как в третьем разряде
(*+6) есть цифра 6 (определенная только в системах счисления с
р 7), то 7 р 8. Из второго разряда (5+4=2) следует, что был перенос
в старший разряд единицы основания, т.е. 5+4–р=2 или p=7.

16.

Дома (сдавать на листках с указанием фамилии, подробным решением на
следующем занятии).
1. Перевести в двоичную, восьмеричную и шестнадцатеричную системы 3
десятичных числа. Ответ проверить обратным переводом.
2. Перевести в шестнадцатеричную систему 3 двоичных числа. Ответ проверить
обратным переводом.
3. Перевести в восьмеричную систему 3 шестнадцатеричных числа. Ответ
проверить.
4. Вычислить выражение 11100,0112+5А,816+42,258.. Укажите, какая система
счисления для выполнения всех операций является оптимальной с точки
зрения быстроты вычисления. Указание: чем больше основание системы, тем
«короче» числа и, следовательно, меньше действий.
5. Вычислить оптимальным способом выражение 1111,012–14,48–1F,С16.
+9,816+2,1258.. Указание: вычислите отдельно алгебраическую сумму всех
слагаемых с одинаковыми знаками.
6. В системе счисления с основанием р число (110)р в два раза больше суммы
чисел (13)р и (3)р. Найдите основание р этой системы счисления. Указание:
записать в десятичной системе и приравнять их, затем решить уравнение
относительно неизвестного основания системы.

17.

7. Не переводя непосредственным делением «в столбик» десятичное число
4097 в двоичную систему, определите количество нулей в его двоичном
представлении.
8. Записать в десятичном виде наибольшее двоичное число с 2 единицами и
10 нулями. Указание: использовать тот факт, что наибольшее двоичное
число с n нулями равно десятичному числу 2n–1 (почему?).
9. Число х=(111)p (рассматриваемое в системе счисления с основанием р,
1<р<20) представляет собой наименьшее число, кратное десятичному числу
31. Найдите основание р системы счисления, не перебирая всевозможные
значения р. Указание: записать х в десятичной системе счисления, затем
приравнять к 31 (почему?) и решить полученное уравнение относительно
неизвестного х.
10. Пусть даны два «нормализованных» числа x=0,25 218 и y=0,625 212.
Найти в такой же форме числа: x+y, x—y, x y, x/y. Указание: например,
x+y=(0,25+0,625 212–18) 218=(2–4+(2–1+2–3) 2–6) 218=214+211+29=
(0,5+0,0625+0,015625) 215=0,5781256 215.