Print bookPrint book

§ 25. Кодирование числовых данных

Site: Профильное обучение
Course: Информатика. 10 класс (Повышенный уровень)
Book: § 25. Кодирование числовых данных
Printed by: Guest user
Date: Sunday, 3 March 2024, 6:22 AM

25.1. Перевод дробных и смешанных чисел

Рассмотрим перевод правильной десятичной дроби в любую другую позиционную систему счисления.

Для перевода десятичной дроби F в систему счисления с основанием q ( F10 → Fq) необходимо F умножить на q, затем дробную часть произведения снова умножить на q и т. д., до тех пор, пока дробная часть произведения не станет равной нулю, либо пока не будет достигнута требуемая точность представления F в системе счисления q (определенное количество цифр в записи результата).

Схема перевода десятичной дроби в двоичную систему счисления выглядит следующим образом:

При повторении значений дробной части (правый столбец таблицы), повторяющуюся группу цифр в записи целых частей (левый столбец таблицы), нужно записать как период дроби.

В примере 25.1 выполнены переводы ( F10  Fqдесятичных дробей в позиционную систему счисления с основанием ( F10  Fq).  

Для смешанных чисел перевод выполняется отдельно для целой и дробной части (пример 25.2).

В ситуации перевода дробей Zp  Zq, когда основания систем счисления (p и q) являются степенями двойки, двоичную систему счисления удобно использовать для перевода как промежуточную по схеме Zp  Z2 → Zq. В этом случае разделение цифр в записи числа на группы начинается с нулевого разряда и выполняется так же, как и при переводе целых чисел (пример 25.3). При этом разряды в записи чисел нумеруются с 0, и цифра в нулевом разряде соответствует единицам. Нумерация разрядов возрастает влево от нулевого разряда и убывает вправо, т. е. в дробной части числа нумерация разрядов отрицательная.

Алгоритм перевода дробных и смешанных чисел из системы счисления с основанием p в систему счисления с основанием 10 (Zp  Z10 ), так же как для целых чисел, вытекает из способа представления числа в системе счисления с основанием  (пример 25.4).

Пример 25.1. Перевод правильной десятичной дроби в другие системы счисления.

1)     

2)     

3)     

 4)     

 0,91610 ≈ 0,22(с предельной абсолютной погрешностью 3–4).

Пример 25.2. Перевод смешанного числа из десятичной системы счисления в систему счисления с другим основанием.

41,62510 → х16

4110 = 2916

41,62510 = 29,А16

Пример 25.3. Перевод Z8  Z2 → Z16.

362,538 = 011¢110¢010,101¢011 = 0¢1111¢0010,1010¢1100 = F2,AB16

Пример 25.4. Перевод смешанного числа из системы счисления с основанием p в систему счисления с основанием 10.

Для перевода необходимо:

  1. Представить число в виде суммы разрядных слагаемых по степеням p.
  2. Выполнить арифметические операции в десятичной системе счисления.

Переведем в десятичную систему счисления шестнадцатеричное число 29,А16:

begin mathsize 14px style 29 comma A subscript 16 space equals space 2 space times 16 to the power of 1 space plus space 9 space times space 16 to the power of 0 space plus space A space times space 16 to the power of – 1 end exponent space equals space 32 space plus space 9 space 10 over 16 space equals space 41 comma 625 subscript 10 end style

25.2. Выполнение арифметических действий в различных позиционных системах счисления

Правила выполнения арифметических действий (сложения, вычитания, умножения и деления) в десятичной системе счисления хорошо известны. Эти же правила применимы к выполнению арифметических действий и в других позиционных системах счисления.

В примере 25.5 рассмотрены правила выполнения поразрядных арифметических действий в двоичной системе счисления.

Рассмотрим алгоритмы выполнения каждого из арифметических действий в позиционных системах счисления с произвольным основанием .

Сложение

Чтобы в системе счисления с основанием  получить сумму S двух чисел A и B, нужно просуммировать образующие их цифры по разрядам  от младшего разряда к старшему по следующим правилам:

  1. Если ai + bi < p, то , si = ai + bi значение (i + 1)-ого разряда не изменяется.
  2. Если ai + bi ≥ p, то , si = ai + bi – p, значение ( i + 1)-ого разряда увеличивается на 1. Это связано с тем, что  единиц i-го разряда соответствует одной единице ( i + 1)-го разряда, а в каждом разряде не может находиться более (p – 1) единиц.

Пример 25.6. Сложить числа 11112 и 1012.

  1. Складываем значения в нулевых разрядах слагаемых: 1 + 1 = 102. Записываем 0 и 1, переносим в первый разряд.
  2. В первых разрядах складываем: 1 + 0 = 1 и добавляем 1 из нулевого разряда. Получаем 1 + 0 + 1 = 102. Записываем 0, а 1 переносим во второй разряд.
  3. Складываем значения во вторых разрядах: 1 + 1 + 1 = 3(112), 3 ≥ 2, значит, записываем 1, и 1 переносим в третий разряд.
  4. Вычисляем в третьем разряде: 1 + 1 = 2. Так как 2 ≥ 2, то записываем 0, а 1 переносим в четвертый разряд.

В примере 25.7 выполнено сложение двоичных смешанных чисел.

Пример 25.8. Сложить числа 63548 и 7438.

  1. Вычисляем: 4 + 3 = 7.
  2. Складываем: 5 + 4 = 9. 9 ≥ 8, значит, записываем 1 (так как 9 – 8 = 1), а 1 переносим во второй разряд.
  3. Вычисляем: 3 + 7 = 10. Добавляем 1 из первого разряда 10 + 1 = 11.  11 ≥ 8, значит, записываем 3 (11 – 8 = 3 ), а 1 переносим в третий разряд.
  4. В третьем разряде: 6 + 1 = 7.

Пример 25.9. Сложить числа 5B416 и C5216.

  1. В нулевом разряде: 4 + 2 = 6.
  2. Вычисляем: B(11) + 5 = 16. 16 ≥ 16, значит, записываем 0 (16 – 16 = 0), а 1 переносим во второй разряд.
  3. Складываем: 5 + C(12) = 17. Добавляем 1 из второго разряда: 17 + 1 = 18. 18 ≥ 16, значит, записываем 2 (18 – 16 = 2), а 1 переносим в третий разряд.

Вычитание

Чтобы в системе счисления с основанием  получить разность R двух чисел A и B ( A > B), нужно вычислять разности образующих их цифр по разрядам i от младшего к старшему по следующему правилу:

  1.  Если  ai  ≥  bi, то ri = ai – bi, значение в (i + 1 )-м разряде не изменяется.
  2. Если ai  <  bi, то ri = p + ai – bi, то значение в (i + 1 )-м разряде уменьшается на 1. При этом, если ai = 0, то занимаем одну разрядную единицу (равную основанию системы счисления p) в (i + 1)-м разряде и продолжаем занимать до ближайшего к i-му старшего разряда (включительно), где ai ≠ 0.

Пример 25.10. Найти разность чисел 10002 и 112.

  1. В нулевом разряде: 0 < 1. Занимаем в первом разряде. Так как в двух следующих разрядах записан 0, то продолжаем занимать до третьего разряда, где записано 1. Получаем 2 – 1 = 1 (102 – 12 = 12). В результат записываем 1.
  2. В первом разряде после того, как заняли, осталось 1 (2(102) – 1). Вычитаем: 1 – 1 = 0. В результат записываем 0.
  3. Во втором разряде осталось 1. Вычитаем: 1 – 0 = 1. В результат записываем 1.
  4. В третьем разряде остается 0.

Пример 25.11. Найти разность чисел 74508 и 7368.

  1. В нулевом разряде:  0 < 6. Занимаем в первом разряде 8(108). Вычитаем: 8 – 6 = 2. В результат записываем 2.
  2. В первом разряде осталось 4. Вычитаем: 4 – 3 = 1. В результат записываем 1.
  3. Во втором разряде: 4 < 7. Занимаем в третьем разряде 8. Вычисляем: 8 + 4 – 7 = 5. В результат записываем 5.
  4. В третьем разряде остается 6, что и записываем в результат.

В примере 25.12 рассмотрено вычитание чисел в шестнадцатеричной системе счисления, которое выполняется по аналогичному алгоритму.

Умножение

Чтобы в системе счисления с основанием p получить произведение М числа A и числа  B < p, надо вычислить произведение цифр числа А по разрядам от младшего к старшему и числа В в соответствии с правилами:

  1. Если ai · b < p, то  mi = ai · b и значение в (i + 1)-м разряде не изменяется.
  2. Если ai · b < p, то  mi = ai · b modp, а значение в ( i + 1 )-м разряде увеличивается на ai · b divp.

Пример 25.13. Найти произведение чисел 12123 и 23.

  1. Вычисляем: 2 · 2 = 4. Так как 4 ≥ 3, в результат записываем 4 mod 3 = 1. Значение в первом разряде увеличиваем на  4 div 3 = 1.
  2. Вычисляем: 1 · 2 + 1 = 3, 3 ≥ 3, значит, в результат записываем 3 mod 3 = 0, а второй разряд увеличиваем на 3 div 3 = 1.
  3. Вычисляем: 2 .  2 + 1 = 5. В результат записываем 5 mod 3 = 2. Третий разряд увеличиваем на 5 div 3 = 1.
  4. Повторяем п. 2. В третьем разряде результата записываем 0, а в четвертом — 1.

В примерах 25.14 и 25.15 по аналогичному алгоритму выполнено умножение многозначного числа на однозначное число в других системах счисления.

Умножение многозначного числа на многозначное число выполняется столбиком. При этом два множителя располагаются один под другим так, чтобы разряды чисел совпадали (находились в одном столбце).

В примерах 25.16 и 25.17 выполнено умножение многозначного числа на многозначное число.

*Деление

Операцию деления нельзя свести к поразрядным операциям над цифрами, составляющими число. Деление чисел в системе счисления с произвольным основанием  выполняется так же, как и в десятичной системе счисления. А это значит, что при выполнении деления применяются правила умножения и вычитания чисел в системе счисления с основанием p. В отличие от других арифметических действий деление выполняется начиная со старшего разряда делимого.

Пример 25.18. Найти частное чисел 1010102 и 1112.

  1. Сравниваем значение в самом старшем разряде и делитель. Если делитель больше значения в данном разряде, то рассматриваем это значение и значение в следующем разряде как число. Повторяем операцию до момента, когда полученное число сравняется либо превысит значение делителя ( 1 <  111, 10 < 111, 101 < 111, 1010 > 111).
  2. Подбираем такое число (1), при котором произведение делителя и этого числа (111) будет максимально близким по значению (но не больше) к числу, полученному в п. 1. Записываем это число в частное первым.
  3. Вычитаем произведение (п. 2) от числа, образованного значениями выбранных разрядов (1010 – 111).
  4. Остаток пишем после черты (11).
  5. Сносим значение следующего разряда к остатку (1) и проверяем, больше или равно получившееся число (111) делителя. Если нет, то сносим значение еще одного разряда до тех пор, пока не образуется число больше или равное делителя, при этом не забываем записывать нули в частное.
  6. Проделываем все вышеперечисленное до тех пор, пока цифры в делимом не закончатся или в остатке не получится число меньше делителя.

Пример 25.19. Найти частное чисел 133518 и 1638.

  1. Сравниваем:1 <  163, 13 < 163, 133 < 163. 1335 > 163.
  2. Подбираем: 6 · 163 = 1262 < 1335.
  3. Вычитаем: 1335 – 1262 = 53.
  4. Сносим 1 и получаем 531 > 163.
  5. Подбираем: 3 .  163 = 531.
  6. Вычитаем: 531 – 531 = 0.

Пример 25.20. Найти частное чисел 8D2F6C16 и DF16.

  1. Сравниваем: 8 < DF, 8D < DF, 8D2 > DF.
  2. Подбираем: А . DF = 8B6 < 8D2.
  3. Вычитаем: 8D2 – 8B6 = 1C.
  4. Сносим F и получаем 1CF > DF.
  5. Подбираем: 2 . DF = 1BE < 1CF.
  6. Вычитаем: 1CF – 1BE = 11.
  7. Сносим 6 и получаем 116 > DF.
  8. Подбираем: 1 . DF = DF.
  9. Вычитаем: 116 – DF = 37.
  10. Сносим C и получаем 37C > DF.
  11. Подбираем: 4 . DF = 37C.
  12. Вычитаем: 37C – 37C = 0.

В компьютерных устройствах выполнение любого действия основано на использовании простейших микроопераций – сложение и сдвиг (операция вычитания сводится к операции сложения). Это позволяет иметь единое арифметико-логическое устройство для выполнения операций, связанных с обработкой данных.

Пример 25.5. Правила двоичной арифметики.

1. Сложение.

2. Вычитание.

3. Умножение.

Пример 25.6. Сложение целых чисел в двоичной системе счисления.

11112 + 1012 = x2

Ответ: 101002

Пример 25.7. Сложение смешанных чисел в двоичной системе счисления.

101,10012 + 1,11112 = x2

Ответ: 111,12

Пример 25.8. Сложение чисел в восьмеричной системе счисления.

63548 + 7438 = x8

Ответ: 73178

Пример 25.9. Сложение чисел в шестнадцатеричной системе счисления.

5B416 + C5216 = x16

Ответ: 120616

Пример 25.10. Вычитание чисел в двоичной системе счисления.

10002 – 112 = x2

Ответ: 1012

Пример 25.11. Вычитание чисел в восьмеричной системе счисления.

74508 – 7368 = x8

Ответ: 65128

Пример 25.12. Вычитание чисел в шестнадцатеричной системе счисления.

21B116 – AFE16 = x16

Ответ: 16B316

Пример 25.13. Умножение многозначного числа на однозначное число в троичной системе счисления.

12123 . 23 = x3

Ответ: 102013

(Пример 25.14. Умножение многозначного числа на однозначное число в восьмеричной системе счисления.

40328 . 78 = x8

Ответ: 342668

Пример 25.15. Умножение многозначного числа на однозначное число в шестнадцатеричной системе счисления.

623216 . A16 = x16

Ответ: 3D60816

Пример 25.16. Умножение чисел в двоичной системе счисления.

101012 . 1012 = x2

Ответ: 11010012

Пример 25.17. Умножение чисел в пятнадцатеричной системе счисления.

6AE15 . 3B15 = x15

Поразрядное умножение на B:

B(11) . E(14) = 154 = 10 . 15 + 4;
B(11) . A(10) + 10 = 120 = 8 . 15 + 0;
B(11) . 6 + 8 = 74 = 4 . 15 + E(14).

Поразрядное умножение на 3:

. E(14) = 42 = 2 . 15 + C(12);
. A(10) + 2 = 32 = 2 . 15 + 2;
. 6 + 2 = 20 = 1 . 15 + 5.

Поразрядное сложение:

4;
0 + C = C;
2 + E(14) = 16 = 1 . 15 + 1;
4 + 5 + 1 = A(10);
1.

Ответ: 1A1C415

Пример 25.18. Деление чисел в двоичной системе счисления.

1010102 : 1112 = x2

Поразрядное вычитание:

[1]0 – 1 = 1;
[1]0 – 1 = 1;
1 – 1 = 0 – незначащий;
0  – незначащий.

Ответ: 1102

Пример 25.19. Деление чисел в восьмеричной системе счисления.

133518 : 1638 = x8

Поразрядное умножение на 6:

. 3 = 18 = 2 . 8 + 2;
. 6 + 2 = 38 = 4 . 8 + 6;
. 1 + 4 = 10 = 1 . 8 + 2.

Поразрядное вычитание:

5 – 2 = 3;
8 + 3 = 11; 11 – 6 = 5;
1.

Поразрядное умножение на 3:

. 3 = 9 = 1 . 8 + 1;
. 6 + 1 = 19 = 2 . 8 + 3;
. 1 + 2 = 5.

Ответ: 638

Пример 25.20. Деление чисел в шестнадцатеричной системе счисления.

8D2F6C16 : DF16 = x16

Поразрядное умножение на A:

A(10) . F(15)  = 150 = 9 . 16 + 6;
A(10) . D(13)  + 9 = 139 = 8 . 16 + B(11).

Поразрядное вычитание (8D2 – 8B6):

[16]2 – 6 = 16 + 2 – 6 = C(12);
D(13) – 1 – B(11) = 1.

Поразрядное умножение на 2:

. F(15) = 30 = 1 . 16 + E(14);
. D(13) + 1 = 27 = 1 . 16 + B(11).

Поразрядное вычитание (1CF – 1BE):

F(15) – E(14) = 1;
C(12) – B(11) = 1;
1 – 1 = 0 – незначащий.

Поразрядное вычитание (116 – DF):

[16]6 – F(15) = 16 + 6 – 15 = 7;
[16] – D(13) = 3.

Поразрядное умножение на 4:

. F(15) = 60 = 3 . 16 + C(12);
. D(13) + 3 = 55 = 3 . 16 + 7.

Ответ: A21416

Вопросы к параграфу

1. Как перевести правильную десятичную дробь в другую систему счисления?

2. Как перевести смешанное число из десятичной системы счисления в любую другую систему счисления?

3. Какой алгоритм используется при переводе смешанного числа из системы счисления с любым основанием в десятичную систему счисления?

4. Каковы правила двоичной арифметики?

5. Как выполняется операция сложения чисел в любой позиционной системе счисления?

6. Как выполняется операция вычитания чисел в любой позиционной системе счисления?

7. Как выполняется операция умножения чисел в любой позиционной системе счисления?

8. Правила выполнения каких арифметических действий используются при выполнении деления в любой позиционной системе счисления?

Упражнения

    

1Переведите числа в десятичную систему счисления:

  1. 11001,012; 1001101,112
  2. 120,213; 203,3214
  3. 456,148; 615,718
  4. BD5,8C16; ABC,4E16

2. Укажите количество единиц в двоичной записи чисел:

12,25; 22,75; 47,3125.

3. Переведите числа из десятичной системы счисления в указанную.

  1. 32,25; 418,75 → Z8.
  2. 159,5; 175,09375 → Z16.
  3. 45,75; 21,625 → Z4.
  4. 13,68; 37, 448 → Z5.
4. Заполните таблицу, выполнив перевод чисел в различные системы счисления:

Двоичная с/с

Восьмеричная с/с

Десятичная с/с

Шестнадцатеричная с/с

11011,101

 

 

 

 

155,3

 

 

 

 

77,375

 

 

 

 

6F,A

5.  Переведите десятичные дроби в указанную систему счисления с указанием периода:

  1. 0,1; 0,75 → Z2.
  2. 0,5; 0,09375 → Z8.
  3. 0,9; 0,625 → Z16.
  4. 0,68; 0, 448 → Z3.

6. Переведите дробь 0,36 → Z2 → Z8→ Z16, оставив в результате указанное количество цифр:

Система счисления

Количество цифр после запятой.

2-7

8-4

16-3

7. Вычислите.

  1. 110012 + 1012
  2. 11110,112 + 10011,012
  3. 100112 - 1012
  4. 11011,1012 – 1111,112
  5. 7708 + 2368
  6. B0916 + 7FA16
  7. 10346,78 + 56,48
  8. A,B16 + E,F16
  9. 7508 – 2368
  10. B0916 – 7FA16
  11. 403,58 – 64,78
  12. D,116 – B,9216

8. Вычислите значение суммы, результат запишите в виде десятичного числа.

  1. 10112 + 178 + 1E16.
  2. 10102 + 238 + E916.

9. Вычислите значение разности, результат запишите в виде восьмеричного числа.

  1. A716 – 110102.
  2. 101112 – 3D16.

10. Вычислите значение выражений, результат запишите в виде шестнадцатеричного числа.

  1. 2068 + AF16 – 1012.
  2. 10112 + 218. 1216.
  3. A16. (101102 – 148).
  4. 2568 + 10110,12. (608 + 1210) – 1F16.

11. Вычислите.

  1. 11012 . 112
  2. 1101000011012 : 1012
  3. 5738 . 458
  4. 102168 : 328
  5. B0916 . DA16
  6. 1425016 : 3916
  7. 16438 : 168
  8. B933,116 : A1D16