Позиционные системы счисления

ЧОУ ВО «Волгоградский институт бизнеса» Кафедра информатики и математики Дисциплина «Информатика и программирование» Позиционные системы счисления Система счисления — это совокупность приемов и правил, по которым числа записываются и читаются. Существуют позиционные и непозиционные системы счисления. В непозиционных системах счисления вес цифры (т. е. тот вклад, который она вносит в значение числа) не зависит от ее позиции в записи числа. Так, в римской системе счисления в числе ХХХII (тридцать два) вес цифры Х в любой позиции равен просто десяти. В позиционных системах счисления вес каждой цифры изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Например, в числе 757,7 первая семерка означает 7 сотен, вторая — 7 единиц, а третья — 7 десятых долей единицы. Сама же запись числа 757,7 означает сокращенную запись выражения 700 + 50 + 7 + 0,7 = 7 . 102 + 5 . 101 + 7 . 100 + 7 . 10—1 = 757,7. Любая позиционная система счисления характеризуется своим основанием. Основание позиционной системы счисления — количество различных цифр, используемых для изображения чисел в данной системе счисления. За основание системы можно принять любое натуральное число — два, три, четыре и т.д. Следовательно, возможно бесчисленное множество позиционных систем: двоичная, троичная, четверичная и т.д. Запись чисел в каждой из систем счисления с основанием q означает сокращенную запись выражения an-1 qn-1 + an-2 qn-2 + ... + a1 q1 + a0 q0 + a-1 q-1 + ... + a-m q-m, где ai — цифры системы счисления; n и m — число целых и дробных разрядов, соответственно. Например: В каждой системе счисления цифры упорядочены в соответствии с их значениями: 1 больше 0, 2 больше 1 и т.д. Продвижением цифры называют замену еѐ следующей по величине. Продвинуть цифру 1 значит заменить еѐ на 2, продвинуть цифру 2 значит заменить еѐ на 3 и т.д. Продвижение старшей цифры (например, цифры 9 в десятичной системе) означает замену еѐ на 0. В двоичной системе, использующей только две цифры — 0 и 1, продвижение 0 означает замену его на 1, а продвижение 1 — замену еѐ на 0. Целые числа в любой системе счисления порождаются с помощью Правила счета [44]: Для образования целого числа, следующего за любым данным целым числом, нужно продвинуть самую правую цифру числа; если какая-либо цифра после ЧОУ ВО «Волгоградский институт бизнеса» Кафедра информатики и математики Дисциплина «Информатика и программирование» продвижения стала нулем, то нужно продвинуть цифру, стоящую слева от неѐ. Применяя это правило, запишем первые десять целых чисел в двоичной системе: 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001; в троичной системе: 0, 1, 2, 10, 11, 12, 20, 21, 22, 100; в пятеричной системе: 0, 1, 2, 3, 4, 10, 11, 12, 13, 14; Кроме десятичной широко используются системы с основанием, являющимся целой степенью числа 2, а именно: двоичная (используются цифры 0, 1); восьмеричная (используются цифры 0, 1, ..., 7); шестнадцатеричная (для первых целых чисел от нуля до девяти используются цифры 0, 1, ..., 9, а для следующих чисел — от десяти до пятнадцати — в качестве цифр используются символы A, B, C, D, E, F). Полезно запомнить запись в этих системах счисления первых двух десятков целых чисел: 10-я 2-я 8-я 16-я 10-я 2-я 8-я 16-я 10 1010 12 A 1 1 1 1 11 1011 13 B 2 10 2 2 12 1100 14 C 3 11 3 3 13 1101 15 D 4 100 4 4 14 1110 16 E 5 101 5 5 15 1111 17 F 6 110 6 6 16 10000 20 10 7 111 7 7 17 10001 21 11 8 1000 10 8 18 10010 22 12 9 1001 11 9 19 10011 23 13 Из всех систем счисления особенно проста и поэтому интересна для технической реализации в компьютерах двоичная система счисления. Люди предпочитают десятичную систему, вероятно, потому, что с древних времен считали по пальцам, а пальцев у людей по десять на руках и ногах. Не всегда и не везде люди пользуются десятичной системой счисления. В Китае, например, долгое время пользовались пятеричной системой счисления. ЧОУ ВО «Волгоградский институт бизнеса» Кафедра информатики и математики Дисциплина «Информатика и программирование» А компьютеры используют двоичную систему потому, что она имеет ряд преимуществ перед другими системами: для ее реализации нужны технические устройства с двумя устойчивыми состояниями (есть ток — нет тока, намагничен — не намагничен и т.п.), а не, например, с десятью, — как в десятичной; представление информации посредством только двух состояний надежно и помехоустойчиво; возможно применение аппарата булевой алгебры для выполнения логических преобразований информации; двоичная арифметика намного проще десятичной. Недостаток двоичной системы — быстрый рост числа разрядов, необходимых для записи чисел. Двоичная система, удобная для компьютеров, для человека неудобна из-за ее громоздкости и непривычной записи. Перевод чисел из десятичной системы в двоичную и наоборот выполняет машина. Однако, чтобы профессионально использовать компьютер, следует научиться понимать слово машины. Для этого и разработаны восьмеричная и шестнадцатеричная системы. Числа в этих системах читаются почти так же легко, как десятичные, требуют соответственно в три (восьмеричная) и в четыре (шестнадцатеричная) раза меньше разрядов, чем в двоичной системе (ведь числа 8 и 16 — соответственно, третья и четвертая степени числа 2). Перевод восьмеричных и шестнадцатеричных чисел в двоичную систему очень прост: достаточно каждую цифру заменить эквивалентной ей двоичной триадой (тройкой цифр) или тетрадой (четверкой цифр). Например: Чтобы перевести число из двоичной системы в восьмеричную или шестнадцатеричную, его нужно разбить влево и вправо от запятой на триады (для восьмеричной) или тетрады (для шестнадцатеричной) и каждую такую группу заменить соответствующей восьмеричной (шестнадцатеричной) цифрой. Например, ЧОУ ВО «Волгоградский институт бизнеса» Кафедра информатики и математики Дисциплина «Информатика и программирование» Для перевода целого десятичного числа N в систему счисления с основанием q необходимо N разделить с остатком ("нацело") на q , записанное в той же десятичной системе. Затем неполное частное, полученное от такого деления, нужно снова разделить с остатком на q , и т.д., пока последнее полученное неполное частное не станет равным нулю. Представлением числа N в новой системе счисления будет последовательность остатков деления, изображенных одной q-ичной цифрой и записанных в порядке, обратном порядку их получения. Пример: Переведем число 75 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную: Ответ: 7510 = 1 001 0112 = 1138 = 4B16. Для перевода правильной десятичной дpоби F в систему счисления с основанием q необходимо F умножить на q , записанное в той же десятичной системе, затем дробную часть полученного произведения снова умножить на q, и т. д., до тех пор, пока дpобная часть очередного пpоизведения не станет pавной нулю, либо не будет достигнута требуемая точность изображения числа F в q-ичной системе. Представлением дробной части числа F в новой системе счисления будет последовательность целых частей полученных произведений, записанных в порядке их получения и изображенных одной q-ичной цифрой. Если требуемая точность перевода числа F составляет k знаков после запятой, то предельная абсолютная погрешность при этом равняется q -(k+1) / 2. Пример. Переведем число 0,36 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную: ЧОУ ВО «Волгоградский институт бизнеса» Кафедра информатики и математики Дисциплина «Информатика и программирование» Для чисел, имеющих как целую, так и дробную части, перевод из десятичной системы счисления в другую осуществляется отдельно для целой и дробной частей по правилам, указанным выше. Перевод в десятичную систему числа x, записанного в q-ичной cистеме счисления (q = 2, 8 или 16) в виде xq = (anan-1 ... a0 , a-1 a-2 ... a-m)q сводится к вычислению значения многочлена x10 = an qn + an-1 qn-1 + ... + a0 q0 + a-1 q -1 + a-2 q-2 + ... + a-m q-m средствами десятичной арифметики. Примеpы: Рассмотрим только те системы счисления, которые применяются в компьютерах — десятичную, двоичную, восьмеричную и шестнадцатеричную. Для определенности возьмем произвольное десятичное число, например 46, и для него выполним все возможные последовательные переводы из одной системы счисления в другую. Порядок переводов определим в соответствии с рисунком: ЧОУ ВО «Волгоградский институт бизнеса» Кафедра информатики и математики Дисциплина «Информатика и программирование» На этом рисунке использованы следующие обозначения: в кружках записаны основания систем счисления; стрелки указывают направление перевода; номер рядом со стрелкой означает порядковый номер соответствующего примера в сводной таблице 4.1. Например: означает перевод из двоичной системы в шестнадцатеричную, имеющий в таблице порядковый номер 6. ЧОУ ВО «Волгоградский институт бизнеса» Кафедра информатики и математики Дисциплина «Информатика и программирование» Сводная таблица переводов целых чисел Таблица 4.1. Рассмотрим основные арифметические операции: сложение, вычитание, умножение и деление. Правила выполнения этих операций в десятичной системе хорошо известны — это сложение, вычитание, умножение столбиком и деление углом. Эти правила применимы и ко всем ЧОУ ВО «Волгоградский институт бизнеса» Кафедра информатики и математики Дисциплина «Информатика и программирование» другим позиционным системам счисления. Только таблицами сложения и умножения надо пользоваться особыми для каждой системы. Сложение Таблицы сложения Сложение в двоичной системе легко составить, используя Правило Счета. Сложение в восьмеричной системе Сложение в шестнадцатиричной системе При сложении цифры суммируются по разрядам, и если при этом возникает избыток, то он переносится влево. Пример 1. Сложим числа 15 и 6 в различных системах счисления. Шестнадцатеричная: F16+616 Ответ: 15+6 = 2110 = 101012 = 258 = 1516. Проверка. Преобразуем полученные суммы к десятичному виду: ЧОУ ВО «Волгоградский институт бизнеса» Кафедра информатики и математики Дисциплина «Информатика и программирование» 101012 = 24 + 22 + 20 = 16+4+1=21, 258 = 2 . 81 + 5 . 80 = 16 + 5 = 21, 1516 = 1 . 161 + 5 . 160 = 16+5 = 21. Пример 2. Сложим числа 15, 7 и 3. Шестнадцатеричная: F16+716+316 Ответ: 5+7+3 = 2510 = 110012 = 318 = 1916. Проверка: 110012 = 24 + 23 + 20 = 16+8+1=25, 318 = 3 . 81 + 1 . 80 = 24 + 1 = 25, 1916 = 1 . 161 + 9 . 160 = 16+9 = 25. Пример 3. Сложим числа 141,5 и 59,75. Ответ: 141,5 + 59,75 = 201,2510 = 11001001,012 = 311,28 = Проверка. Преобразуем полученные суммы к десятичному 11001001,012 = 27 + 26 + 23 + 20 + 2-2 = . 2 1 . . 311,28 = 3 8 + 18 + 1 8 + 2 8-1 = C9,416 = 12 . 161 + 9 . 160 + 4 . 16-1 = 201,25 Вычитание C9,416 виду: 201,25 201,25 ЧОУ ВО «Волгоградский институт бизнеса» Кафедра информатики и математики Дисциплина «Информатика и программирование» Пример 4. Вычтем единицу из чисел 102, 108 и 1016 Пример 5. Вычтем единицу из чисел 1002, 1008 и 10016. Пример 6. Вычтем число 59,75 из числа 201,25. Ответ: 201,2510 - 59,7510 = 141,510 = 10001101,12 Проверка. Преобразуем полученные разности к 7 3 2 10001101,12 = 2 + 2 + 2 + 2 215,48 = 2 . 82 + 1 . 81 + 5 . 80 + 8D,816 = 8 . 161 + D . 160 + 8 . 16-1 = 141,5. = 215,48 = десятичному + 2-1 = 4 . 8-1 = 8D,816. виду: 141,5; 141,5; Умножение Выполняя умножение многозначных чисел в различных позиционных системах счисления, можно использовать обычный алгоритм перемножения чисел в столбик, но при этом результаты перемножения и сложения однозначных чисел необходимо заимствовать из соответствующих рассматриваемой системе таблиц умножения и сложения. Умножение в двоичной системе Умножение в восьмеричной системе ЧОУ ВО «Волгоградский институт бизнеса» Кафедра информатики и математики Дисциплина «Информатика и программирование» Ввиду чрезвычайной простоты таблицы умножения в двоичной системе, умножение сводится лишь к сдвигам множимого и сложениям. Пример 7. Перемножим числа 5 и 6. Ответ: Проверка. 111102 368 . 5 Преобразуем = 24 = 6 = полученные + 23 1 38 3010 = 111102 = произведения к десятичному + 22 + 21 = + 68 = 368. виду: 30; 30. Пример 8. Перемножим числа 115 и 51. . Ответ: 115 51 = 586510 = 10110111010012 = 133518. Проверка. Преобразуем полученные произведения к десятичному виду: 10110111010012 = 212 + 210 + 29 + 27 + 26 + 25 + 23 + 20 = 5865; 133518 = 1 . 84 + 3 . 83 + 3 . 82 + 5 . 81 + 1 . 80 = 5865. Деление Деление в любой позиционной системе счисления производится по тем же правилам, как и деление углом в десятичной системе. В двоичной системе деление выполняется особенно просто, ведь очередная цифра частного может быть только нулем или единицей. Пример 9. Разделим число 30 на число 6. ЧОУ ВО «Волгоградский институт бизнеса» Кафедра информатики и математики Дисциплина «Информатика и программирование» Ответ: 30 : 6 = 510 = 1012 = 5 8. Пример 10. Разделим число 5865 на число 115. Восьмеричная: 133518 :1638 Ответ: 5865 : 115 = 5110 = Проверка. Преобразуем полученные частные к 5 4 1 1100112 = 2 + 2 + 2 + 2 = 51; 638 = 6 . 1100112 = десятичному 81 + 3 . 80 638. виду: = 51. Пример 11. Разделим число 35 на число 14. Восьмеричная: 438 : 168 Ответ: 35 : 14 = Проверка. Преобразуем полученные 10,12 = 21 + . . -1 2,48 = 2 8 + 4 8 = 2,5. 2,510 = частные 2 Вопросы для самоконтроля 1. Что такое позиционная система счисления? 2. Что такое основание системы счисления? 3. Что такое придвижение цифры? к -1 10,12 = десятичному = 2,48. виду: 2,5; ЧОУ ВО «Волгоградский институт бизнеса» Кафедра информатики и математики Дисциплина «Информатика и программирование» 4. Сформулируйте правило перевода из двоичной системы счисления в восьмеричную? 5. Сформулируйте правило перевода из десятичной системы счисления в двоичную?.