16. Позиционные системы счисления (лекция 16)

Позиционная запись числа A подразумевает его представление в виде суммы

где - цифры от 0 до q -1, q -основание системы счисления, k -число разрядов в целой части числа, m -то же в дробной части. В дальнейшем мы всюду будем пользоваться обозначением общего числа разрядов:

n = k + m

Фактически число записывается как ряд цифр, а для указания начала отсчета степеней основания системы служит q-ичная запятая или “точка”.

Общие принципы арифметики в любой из позиционных систем одинаковы. Различия сводятся к неодинаковому количеству используемых цифр. Чем больше допустимых цифр, тем больше получается парных сочетаний этих цифр в элементарных операциях. В десятичной арифметике таблицы элементарных операций сложения или умножения имеют размер 10х10 = 100, а в шестнадцатеричной - 16х16 = 256.

Самые простые правила у двоичной арифметики. Таблицы сложения и умножения имеют размер 2х2, причем функция суммы двух цифр совпадает с логической функцией неравнозначности, а функции переноса и произведения одинаковы и совпадают с конъюнкцией. В результате действия над многоразрядными числами тоже оказываются очень простыми. Примеры:

Особенно заметное упрощение получается при умножении и делении чисел. Умножение превращается в ряд сдвигов и сложений, а при делении не приходится подбирать очередную цифру частного - вычитание то происходит, то не происходит.

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

При q > 2 действия намного усложняются. При выполнении операций “вручную” каждое элементарное действие приходится разбивать на два шага. Складывая две цифры, мы сперва в уме находим сумму по правилам десятичной арифметики, затем переводим её в систему счисления с заданным основанием и только после этого делаем соответствующую запись. Аналогично действуем при умножении. Сперва две цифры перемножаются в уме в десятичной системе, затем к результату (в уме) прибавляется перенос. Только после этого результат перемножения двух цифр переводится в нужную систему.

Примеры:

Из систем с основанием, отличным от 2, основной интерес представляют две системы: десятичная и шестнадцатеричная. Первая из них необходима, по крайней мере, для ввода и вывода чисел, а вторая, как и другие системы с основанием, кратным целой степени двойки, обладает определенными преимуществами перед другими системами. По сравнению с двоичной системой запись числа в шестнадцатеричной системе гораздо компактнее, так как одна шестнадцатеричная цифра заменяет тетраду двоичных цифр:

Шестнадцатеричная система не создает никаких проблем для машинной арифметики, так как при сложении и вычитании сохраняются правила двоичной арифметики. Фактически в сложении участвуют двоичные эквиваленты шестнадцатеричных чисел. Пример:

Десятичные числа в машине тоже заменяются двоичными тетрадами, но правила арифметики получаются гораздо более сложными. Они будут рассмотрены позже, а сейчас перейдем к вопросу о переводе чисел из одной системы счисления в другую.

Проще всего этот вопрос решается, если у обеих систем: “старой” и “новой” основание равно целой степени двойки. При этом для перевода чисел достаточно в качестве промежуточной формы записать двоичный эквивалент, а затем перегруппировать разряды по-новому, начиная от запятой вправо и влево. Переведем восьмеричное число 35,3 в шестнадцатеричную систему:

Описанное преобразование является частным случаем. В более общем случае перевод выполняется с помощью специального вычисления. Из определения позиционного числа вытекает формула для преобразования целых чисел из системы с основанием p в систему с основанием q:

Этой формуле соответствует следующий алгоритм преобразования (все действия выполняются по правилам q–ичной арифметики):

  1. Умножить старшую цифру исходного числа на старое основание p, выраженное в новой системе q,
  2. Прибавить к предыдущему результату следующую цифру числа,
  3. Умножить предыдущий результат на p,
  4. Повторить пункт 2,
  5. Повторять п.п. 3 и 4 до исчерпания разрядов числа.

Для правильных дробей аналогичное по смыслу преобразование задает формула:

.

Соответствующий алгоритм в словесном описании:

  1. Разделить младшую цифру исходного числа на p,
  2. Прибавить к предыдущему результату следующую цифру числа,
  3. Разделить предыдущий результат на p,
  4. Повторять п.п. 2 и 3 до исчерпания разрядов числа.

Заметим, что выполнение указанных действий неизбежно связано с округлением результата. Все действия описанных алгоритмов выполняются по правилам арифметики с “новым” основанием.

Существуют также алгоритмы, противоположные описанным. Для целых чисел:

  1. Разделить A(p) на q(p). Деление выполняется по правилам “старой” арифметики с основанием p. Остаток от деления запомнить, - это будет младшая цифра искомого числа,
  2. Предыдущее частное снова разделить на q и запомнить остаток,
  3. Повторять п. 2, пока не получится частное, меньшее, чем q. Число A(q) представится рядом остатков, записанных в порядке, обратном их получению, а старшей цифрой будет последнее частное.

Переведем по этому алгоритму десятичное число 106 в троичную систему:

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

  1. Умножить дробь A(p) на q(p) по правилам “старой” арифметики. Целую часть произведения запомнить. Это будет старшая цифра искомой дроби,
  2. Дробную часть предыдущего произведения вновь умножить на q и запомнить целую часть произведения,
  3. Повторять п. 2, пока не будет получено нужное число разрядов новой дроби A(q). Она запишется как ряд целых частей произведений, записанных в порядке их получения.

Переведем по этому способу в десятичную систему двоичную дробь 0,00111101 с точностью до двух значащих цифр:

Если число является смешанной дробью, то при любом варианте алгоритма его нужно переводить по частям: целую и дробную части по отдельности с последующим объединением результатов.

Содержание

Hosted by uCoz