Программирование на языке высокого уровня Факультет информационных технологий Новосибирский государственный университет Т.Г.Чурина

Системы счисления Лекции 1, 2

Значение и обозначение числа Число Значение (содержание) Обозначение (форма) Значение конкретного числа – это числовая величина, «чистая», отвлеченная от каких-либо измеряемых объектов и единиц измерения, количественная мера, выраженная в стандартных единицах. Обозначение (форма, внешнее представление) числа – это его название или знак в некотором языке или системе обозначений, позволяющих отличать данное число от других. 9, IX, девять, nine, 1001 (2) Значение числа инвариантно (не зависит от обозначения).

Система счисления ( с. с.) - это система правил, позволяющих конструировать названия чисел ( знаковые обозначения ) некоторым регулярным способом. Непозиционные системы счисления возникли первыми, они основаны на простом суммировании « весов » – цифр - « разновесов », занятых в записи числа. Например, римская с. с., где все цифры могут браться плюсом или минусом, в зависимости от позиции этой цифры относительно более « тяжелых ». IX, XI Позиционные системы счисления : число цифр конечно, вклад каждой цифры зависит от « веса » ее позиции ( разряда ) в записи числа.

Представление целых чисел в позиционных системах счисления с произвольным основанием Общие свойства b-ичных позиционных систем счисления (b-с.с.) определяются параметром b - основанием с.с., которое определяет количество цифр, используемых для записи числа: от 0 до b – 1, если b 10. Если b = 16, то используются буквы: 10 – A 11 – B 12 – C 13 – D 14 – E 15 – F

Запись целого числа 0 a i < b, i – индекс позиции (разряда), в которой расположена цифра a i. Запись числа называется k-значной, если индекс разряда первой значащей цифры числа равен k – 1. Примеры (2), , 7DAB (16), (5) - неправильная запись S =

Соотношение записи целого числа со значением S – запись числа. N(S) – его значение. S = b i – явно указывают веса разрядов, определяющих вклад каждой цифры в значение числа, b i называется единицей i -го разряда b -ичного числа. a i – количество полных единиц i -го разряда, которое останется после вычета всевозможного числа единиц старших разрядов.

Соотношение записи целого числа со значением Значение N i равно количеству полных единиц i-го разряда в числе.

Примеры N (10011 (2) )= =19 N (10011 (2) )=(((1 2+0) 2+0) 2+1) 2+1=19 N (30A (16) ) = = 778 N (30A (16) ) =(3 16+0) = 778

Теорема 1 Любое число однозначно представимо в виде цифр заданной b-с. с. Доказательство (от противного).

Алгоритм А1: (перевод b-ичного числа в 10-с.с.) Вход: b > 0, k > 0 (число цифр), набор a k-1, a k-2, …, a 1, a 0. ;(S – накапливает степень, N – значение) цикл по i := 1 до k – 1 конец цикла; Выход: N ( 2k - 2) операций * (k-1) операций +

Схема Горнера Алгоритм А2 : (перевод b-ичного числа в 10-с.с) Вход: b > 0, k > 0 (число цифр), набор цикл по i от k- 2 вниз до 0 N := N b + a i ; конец цикла ; Выход: N k-1 операция * k-1 операция +

Алгоритм A3: (перевод числа из 10-с. с. в b-с.с) Вход: N 0, b > 0 ; i := 0; цикл a i := N mod b; (mod – остаток от деления нацело) N := N div b ; (div – целое деление) i := i + 1; пока N 0; k := i; Выход: набор a i, k ( число значащих цифр) минимальное число операций деления = k

Пример : перевод из 10- с. с. в 2- с. с Целая часть | Остаток от деления на (10) = (2)

Перевод числа из b 1 - с. с. в b 2 - с. с. b 1 -с.с.b 2 -с.с. b 10 -с.с.

Представление действительных чисел Если в дробной части числа конечное число знаков k, то нижний индекс суммы равен к =(3+(7+5/10)/10)/10=(3+(7+(5+0)/10)/10)/10 S =

Связь дробной части числа со значением где i = k, …, 1 ;

Примеры N(«1.101 (2) ») = = = N f («1.101 (2) ») =(1 +(0 +(1 +0)/2)/2)/2 = (1 + ( )/2 )/2 = ( ) / 2 = N f («0.01 (3) ») = = = 0.(1)

Целая часть числа N f *b (0 < N f < 1) равна первой цифре дробной части числа N f Алгоритм А4: перевод дробной части из 10-с. с. в b-с.с Вход: N f ( 0 N f 1; i := -1; цикл ([x]-взятие целой части числа) ( остается в том же диапазоне ) i := i – 1; пока k := i; Выход: набор (число значащих цифр). Алгоритм А4 может не завершиться, если данное число не представимо конечной дробью в b-с.с Требуется k умножений (выражение N f *b можно вычислять в цикле один раз и хранить в промежуточной переменной).

Пример:

Теорема Т2 Несократимая дробь p/q конечно представима в системе счисления с основанием b в том и только в том случае, когда все числа из разложения q на простые множители входят в такое же разложение b (количество повторений не учитывается). Пример 121/675 конечна в 15-с.с.: 675 = 3 3 *5 2 ; 15 = 3*5; 1/675 = 5*15 -3 = (15) ; 121*5/15 -3 = (2* * )/15 -3 = 2/ / / /675 = 0.2A5 (15) ; 1/10 бесконечна в 2-с.с. !!!!

Алгоритм А5: Алгоритм А5: ( перевод дробной части из b-с.с. в 10-с.с) Вход : b > 1, к > 0 (число дробных цифр), набор (S накапливает степень, значение ) цикл по i от -1 вниз до -k ; конец цикла Выход: 2k операций *, / k операций +

Алгоритм А6 : перевод дробной части из b- с. с. в 10- с. с. ( из формулы (7) по схеме Горнера) Алгоритм А6 : перевод дробной части из b- с. с. в 10- с. с. ( из формулы (7) по схеме Горнера) Вход: b >1, k > 0 (число цифр), набор цикл по i от –k до -1 конец цикла; Выход: k операций + и /

Число N в b-с.с. имеющее k дробных цифр, при умножении на b становится целым (это умножение соответствует сдвигу точки на k позиций вправо) Алгоритм А7 найти целое N 1 = N * b 1 k (умножением или сдвигом точки); выполнить для N 1 один из алгоритмов А1 или А2, затем АЗ; разделить полученный результат на b 1 k в системе b 2

Пример Перевести (2) в 10-с.с. 1) умножим на (2) 2) переведем в 10-с.с. 45 3) разделим: 45/8 = (10) =1*2 2 +1*2 0 +1* *2 -3 =5+1/2+1/8=5.625

Кратные системы счисления Если основания двух систем счисления b 1 и b 2 связаны соотношением b 2 = b 1 m для некоторого натурального т, то такие системы счисления называются кратными. Перевод числа из одной с. с. в другую для таких систем можно выполнить проще. Сгруппируем цифры в b 1 -записи числа по m от точки влево и вправо (добавив при нехватке цифр нужное количество незначащих нулей):

затем также сгруппируем слагаемые в формуле (5) (они содержат множитель b 1 в степени, равной индексу цифры), вынесем за скобки из каждой группы i общий множитель (b 1 im = (b 1 m ) i = b 2 i ) и обозначим для каждой группы Тогда значение исходного числа может быть представлено в виде: N(S) = A k * b 2 k + … + A i * b 2 i А 0 *b А -1 *b … А -j b 2 -j, что по определению совпадает со значением записи того же числа в b 2 -с.c. c цифрами А i, если заметить, что А i, действительно могут принимать все значения от 0 до b 1 m 1 = b 2 1.

Таблицы соответствия последовательностей цифр кратных с. с. 8-с.с.2-с.с с.с.2-с.с A1010 B1011 C1100 D1101 E1110 F c.c.3-c.c

Алгоритм А8: перевод из меньшей кратной с.с. в большую Вход: b 1 > 1, b 2 = b 1 m, b 1 - представление числа; разбить число на группы по т цифр, начиная от точки, в обе стороны (если в крайних группах цифр меньше т, добавить незначащие нули: в целой части спереди, в дробной сзади); заменить каждую группу b 2 -цифрой по формуле (8) или таблице. Выход: b 2 -представление исходного числа.

Алгоритм А9: перевод из большей кратной с.с. в меньшую Вход: b 1 > 1, b 2 = b 1 m ; b 2 -представление числа; заменить каждую b 2 -цифру цепочкой из т b 1 -цифр по формуле (8) или таблице; отбросить незначащие нули слева и справа. Выход: b 1 -представление исходного числа.

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

Алгоритм А10: сложение двух чисел Вход: две строки цифр, представляющие слагаемые ; выравнивание: расположить слагаемые одно под другим в произвольном порядке так, чтобы разряды с одинаковым весом находились друг под другом; если какое-то число короче других слева или справа, дополнить его нулями; начальные установки: обнулить цифру переноса в следующий разряд; установить результат равным пустой строке; цикл по текущему разряду от младшего до старшего: определить сумму переноса и цифр в столбце текущего разряда чисел; младшую цифру суммы записать в текущий разряд результата, старшую в перенос; конец цикла ; окончание: если перенос не равен 0, то дописать перенос в начало результата Выход: строка, представляющая результат.

Единственное место в этом алгоритме, где присутствует обращение к значениям цифровых символов, это поразрядное сложение в цикле. Действительно, из одного лишь вида знаков «2» и «3» нельзя извлечь информацию, что результатом их сложения будет знак «5». Эти сведения можно задать, например, двумя таблицами сложения: в одной для каждой пары цифр записать младшую цифру результата, в другой цифру переноса («0» или «1»); исчерпав таким образом все немногочисленные случаи, можно заменить операцию сложения значений операцией выборки знака из таблицы. Чтобы учесть сложение с переносом, можно завести две пары таблиц или записать в каждую клетку по две цифры.

Алгоритм А10 замечателен тем, что применим к произвольной позиционной с. с. при соответствующей замене таблиц сложения. Нетрудно обобщить алгоритм А10 для одновременного сложения нескольких чисел, а также аналогичными рассуждениями показать, что алгоритмы вычисления «столбиком» для вычитания, умножения и деления универсально применимы к произвольной с. с. при замене соответствующих таблиц *

Особенности умножения и деления на основание системы счисления В b - с. с. число b всегда имеет представление «10 (b) ». Умножение на b сводится просто к дописыванию 0 справа к целому числу или ( что то же ), сдвигом b - ичной точки на один разряд вправо. Деление на b равносильно сдвигу точки на один разряд влево или отбрасыванию младшей цифры целого числа при делении нацело. Аналогично число b всегда представляется единицей с k нулями, а умножение ( деление ) на b сводится к сдвигу точки на k позиций вправо ( влево ). Остатком от деления целого числа нацело на b является число, составленное из k младших цифр. Добавление k нулей справа и отбрасывание k младших цифр можно рассматривать как две новые операции арифметического сдвига на k позиций.

Арифметические сдвиги Добавление k нулей справа и отбрасывание k младших цифр можно рассматривать как операции арифметического сдвига на k позиций. В Си определены операции арифметического сдвига на k позиций, которые равносильны умножению или целочисленному делению на 2 k. > сдвиг вправо Примеры: a = 5 > 4; /* b будет равно 7 */

Особенности двоичной арифметики * Если сопоставить нулю логическую «ложь», а единице «истину», то таблица сложения совпадет с таблицей значений для логической операции «исключающее или», а таблицы умножения и переноса при сложении с операцией «и». На этом совпадении основана схемная реализация в компьютерах поразрядной двоичной арифметики с помощью примитивных логических элементов (вентилей). Другая аналогия «минимаксная»: нетрудно видеть, что ab = min(a,b), a+b = min(a,b)+ max(a,b). Наконец, умножение «столбиком» многозначных чисел в двоичной с. с. реализуется только с помощью операций сложения и сдвига.

Сложность арифметических алгоритмов Затраты памяти на хранение чисел и времени на выполнение операций с ними зависят от длины записи числа в цифрах рабочей системы счисления. Для заданной b-с. с. следующие величины: k n длина записи (натурального) числа N, N k максимальное натуральное число, записываемое k цифрами, связаны соотношениями: k n = [logbN] + 1, где [x] наибольшее целое, не превышающее x; N k = b k 1. Верхние оценки для размера результата арифметической операции над парой целых чисел N1 и N2 (пусть N1 > N2): для сложения и вычитания k N1 +1, для умножения k N1 + k N2, для деления k N1 +1, (так как N2 > 1).

Время исполнения Алгоритмы сложения содержат один проход по всем разрядам числа, причем каждый разряд обрабатывается не более одного раза. Поэтому время работы алгоритма сложения линейно по k : Т слож ( k )~ k. Алгоритмы умножения и деления выполняют сложение и вычитание несколько раз ( не более, чем k ), со сдвигом на одну позицию. Так как время сложения линейно, время умножения и деления квадратично по k : T yмн ~ k 2,, T дел ( k ) ~ k 2. В системах команд компьютеров есть команды типа сложения и умножения, которые работают не с отдельными битами, а с байтами ; они обычно рассматриваются как элементарные. Проведенные выше оценки сохраняют свою силу, если заменить базовую с. с. кратной ей ( со степенью кратности равной длине слова ).

Упражнения 1. Выразить целую часть 17.5 * X через сложение и операции поразрядных сдвигов числа X вправо и влево (10) = = –1 = (2) 17.5 *X = X* ( –1 ) = = X*2 4 + X*2 0 + X*2 –1 = = (X > 1) 2. Если 120 (x) делится на 11 (10), то как выглядит (чему равно?) 3 10 в системе счисления с основанием x? Подбором можно определить, что x = 9, т.к. 120 (9) = 99 (10) – делится на 11 без остатка = 3 2*5 = (3 2 ) 5 = 9 5 = (9)