2…Системы счисления, переводы чисел из одной позиционной системы счисления в другую.

Система счисления (СС) – это совокупность правил записи и наименования чисел.

Существуют позиционные и непозиционные С.С.

СС называется позиционной (непозиционной), если значение цифры числа зависит (не зависит) от местоположения цифры в числе.

Непозиционная СС , например, римская:

I – 1, V - 5, X - 10, L – 50, C - 100, D – 500, M – 1000

XXVII, XLIV

Общепризнанной ПСС является 10-ая СС . Она использует для записи чисел цифры 0, 1 ,2 ,3, 4. 5, 6, 7, 8, 9.

727,7 – это сокращенная запись 7 *102+2*101 +7*100 +7*10-1

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

Основанием позиционной СС называется количество единиц какого- либо разряда, объединяемых в единицу соседнего старшего разряда.

Основание СС в любой ПСС записывается как 10

Примеры ПСС: 60-ричная, 12-ричная, 5-ричная.

В ПСС с основанием Р>1 любое число может быть записано

в двух формах: 1) сокращенной и 2) в виде многочлена.

1. Х = an an-1 an-2 an-3…a1 a0 a-1 a-2 …a-m

Значением числа является сумма значений его цифр.

2) X = an *pn+an-1*pn-1 +an-2*pn-2+….+a1*p1+a0*p0+a-1*p-1+a-2*p-2+…+a-m*p-m

Здесь p – основание СС, 0 =< ai <=P-1 – называют базисными цифрами данной СС. Количество базисных цифр равно основанию СС. В информатике часто используются 2-я, 8-я и 16-я СС.

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

Сложение умножение

0 + 0 = 0 0 * 0 = 0

0 + 1 = 1 1 * 0 = 0

1 + 0 = 1 0 * 1 = 0

1 + 1 = 10 1 * 1 = 1

Эти два свойства 2-ой СС послужили причиной того, что все современные компьютеры используют ее для представления и обработки числовой информации

Таблица базисных цифр:

10	2	8	16
0	0	0	0
1	1	1	1
2	10	2	2
3	11	3	3
4	100	4	4
5	101	5	5
6	110	6	6
7	111	7	7
8	1000	10	8
9	1001	11	9
10	1010	12	A
11	1011	13	B
12	1100	14	C
13	1101	15	D
14	1110	16	E
15	1111	17	F

Переводы чисел из одной ПСС в другую.

Постановка задачи.

Известна запись числа Х в СС с основание P и базисными цифрами 0 <= pi <= P-1, требуется получить запись числа Х в СС с основанием Q и базисными цифрами 0 <= qi <= Q-1.

При рассмотрении правил перевода необходимо помнить правилами арифметики какой СС вы пользуетесь. Будем считать «своей» СС с основание P и при переводе будем пользоваться правилами P-ичной СС. Тогда СС с основанием Q называют «чужой», в ней умеют представлять базисные цифры и основание СС с помощью P-ичных чисел.

Перевод из Q -> P.

Чтобы перевести число из “чужой» СС в «свою», необходимо:

1) представить данное число в виде многочлена;

2) базисные цифры и основание Q-ичной СС записать с помощью P-ичных чисел;

3) выполнить арифметические действия.

Примеры.

1) (125,2)8->10 = 1*102 +2*101 +5*100 + 2*10-1 =

1*82 +2*81 +5*80 +2*8-1 = 64 + 16 + 5 +0,25 = 85,2510

Переводы чисел из одной ПСС в другую. Схема Горнера

2) (101,01)2->10 = 1*102 +0*101 +1*100 + 0*10-1 +1*10-2 =

= 1*22 +0*21 +1*20 +0*2-1 +1*2-2 = 4 + 1 + 0,25 = 5,2510 ;

3). (AB1)16->10 = A*102 +B*101 +1*100 = 10*162 + 11*161 + 1* 160 = 2560 + 176 + 1=

= 273710.

Для перевода целых чисел из любой системы в 10-ю удобно использовать схему Горнера, согласно которой:

an *pn+an-1*pn-1+an-2*pn-2+….+a1*p1+a0*p0 =

= ((…(an *P + an-1)*P + an-2)*P +….+a1)*P + a0

Например.

13218->10 = ((1*8 + 3)* 8 + 2)* 8 +1 = 72110

12348->10 = ((1*8 + 2)*8 + 3)*8 + 4 = 66810

Перевод из P в Q.

• Перевод целых чисел.

• Дано Х = (an an-1an-2….a1a0)p, требуется получить

  • Х = (qn qn-1qn-2….q1q0)Q

Переводы чисел из одной ПСС в другую.

Представим в виде многочлена данное число

Х = qn *Qn+qn-1*Qn-1 +qn-2*Qn-2+….+q1*Q1+q0

Разделив число на основание СС, в которую переводим – Q, получим: Х/Q = [X/Q] + {X/Q}, где

[X/Q] = qn*Qn-1+qn-1*Qn-2+qn-2*Qn-3+….+q1 -

это целая часть от деления, а

{X/Q} = q0/Q - дробная часть.

Так как qi < Q, то q0 = {X/Q} * Q - это остаток от деления Х/Q. ….Продолжая делить целую часть на Q, получим:

qi = {Xi/Q} * Q , Xi+1 = [Xi/Q], i = 0, 1, 2, 3, …. X0 = X……

Так как действия мы выполняли с помощью P-ичной арифметики, для

получения окончательной записи числа Х в новом представлении

необходимо полученные числа qi записать с помощью цифр

Q-ичной СС.

Примеры: (25)10->2 = (11001)2; (3060)10->16 = (BF4)16

3. Перевод произвольных чисел.

Для перевода произвольных чисел из P-ичной системы в Q-ичную достаточно отдельно перевести целую часть и дробную часть и результаты приписать. (3060,8)10->16 = (BF4,C)16

Смешанные СС.

Смешанная Q-P-ичная СС – это СС, в которой каждая цифра P-ичного числа записывается с помощью n Q-ичных цифр, где n – это количество Q-ичных цифр, достаточных для хранения старшей Р-ичной цифры.

Например, число 2410 в 2-10-й СС равно 0010 01002-10.

Переводы чисел для СС, связанных соотношением P = Qn.

1). Перевод из P в Q. Чтобы перевести число из СС с основанием P в СС с основанием Q, достаточно каждую цифру данного числа записать с помощью n Q-ичных разрядов, используя таблицу представления базисных цифр

Переводы чисел для СС, связанных соотношением P = Qn. Числа с фиксированной и плавающей точкой.

2). Перевод из Q в P. Чтобы перевести число из СС с основанием Q в СС с основанием P, достаточно данное число разбить влево и вправо от запятой на группы по n разрядов, неполные крайние группы можно дополнить нулями. Затем каждую такую группу записать с помощью одной P-ичной цифры.

Примеры.

(1BF9,51)16->2->8 = 0001 1011 1111 1001, 0101 00012 = 15771,2428

(7541,23)8-2-16 = 111 101 100 001,010 0112 = F61,4C16

Числа с фиксированной и плавающей точкой.

X = знак(anan-1an-2…a0.a-1a-2…..a-m)p - это запись числа с фиксированной точкой.

Записываем в виде многочлена:

Х = знак(an*Pn + an-1*Pn-1+an-2*Pn-2+…+a0*P0+a-1*P-1+a-2*P-2+…+a-mP-m)P

Вынесем за скобку в качестве множителя Pk и свернем, получим число в форме с плавающей точкой

Числа с фиксированной и плавающей точкой. Нормализованные числа.

Х = знак(an*Pn-k + an-1*Pn-1-k+an-2*Pn-2-k+.. …+a0*P-k+ak-1*P-1+ak-2*P-2+…

+a-mP-m-k)*Pk

1) X = знак(anan-1an-2…ak,ak-1ak-2…..a-m)*Pk или

2) X = знак |M| * Pзнак |n|

Число с плавающей точкой называется нормализованным числом, если

в записи 1) k = n+1 и an <> 0, или

в записи 2) мантисса M удовлетворяет условию 1/P <= |M| < 1.

Например: 3.1415926 0.0031415926*103 314.15926*10-2 0.31415926

Арифметические действия над числами с плавающей точкой.

1. M1*2p1 + M2 *2p2 = M*2p , если P1 > P2, то вычисляется P1 – P2 , M2 сдвигается на

(P1 – P2 ) разрядов вправо и мантиссы складываются, результат нормализуется,

так что порядок суммы чисел P = P1 + P/, где P/ учет нормализации мантиссы

результата суммирования.

2. Вычитание сводится к сложению

3. Умножение: M = M1 * M2 и P = P1 + P2 + P/

4. Деление: M = M1 / M2 и P = P1 - P2 + P/

Нетрадиционные позиционные системы счисления..

ПСС делят на традиционные, нетрадиционные и смешанные.

Все ПСС одинаковы в том смысле, что:

1. Арифметические операции выполняются по одним и тем же правилам;

2. Справедливы одни и те же законы арифметики ….

3. Правила выполнения арифметических действий опираются на таблицы сложения и умножения в P-ичной СС.

Для традиционных ПСС вводится понятие базис и основание СС так, что базис – это последовательность чисел, каждое из которых задает значение цифры по ее месту в записи, т.е. задает вес каждого разряда. Тогда, базис 10-ой СС – это

1, 101, 102, 103 , 104….10n ,а в общем виде:

….P-2, p-1, 1, p, p2 p3….pn

Знаменатель P геометрической прогрессии, члены которой образуют базис традиционной СС, является основанием СС.

Нетрадиционные позиционные системы счисления. Факториальная ПСС

В традиционных ПСС вес единиц разрядов числа растет справа налево равномерно в P раз, где P – основание СС. В нетрадиционных ПСС вес единиц разрядов в числе также растет, но не равномерно, а по какому-либо другому закону. Например, число, записанное в факториальной ПСС имеет значение в 10-ой СС, равное сумме факториалов n первых натуральных чисел, умноженных на цифры факториальной записи числа.

3221ф = 3 * 4! + 2 * 3! + 2 * 2! + 1* 1! = 8910

40301ф = 4*5! + 3*3! + 1*1! = 49910

Чтобы перевести число из 10-ой СС в факториальную, необходимо разделить данное число на 2, затем целую часть разделить на 3, затем на 4 и т. д. пока целая часть не окажется равной нулю.

Для нетрадиционных ПСС не используется понятие основание СС, а используется только понятие базисные цифры. А базисные цифры – это символы алфавита этой СС, этого формального языка.

Нетрадиционные позиционные системы счисления. Фибоначчиева ПСС. Уравновешенные СС.

• Фибоначчиева ПСС в качестве базиса использует числа ряда Фибоначчи (1,2,3,5,8,13,21,34,55,….), а символами алфавита являются 0 и 1. Тогда число в фибоначчиевой СС может быть записано так:

3710 = 34 + 3 = 10000100фиб = 1*34 + 0*21 + 0*13 +0*8 + 0*5 +0*2 +0*1;

2510 = 21 + 3 +1 = 1000101фиб

Нетрадиционные ПСС используются для кодирования чисел, их особенности и области применения – это предмет исследования в настоящее время.

Уравновешенная, например, троичная СС имеет алфавит -1, 0, 1.

Пример. -11-1013 = -1*34 + 1*33 -1*32 +0*3 +1*30 = 6210

Главная особенность уравновешенных СС – для представления в компьютере не нужно выделять разряд для знака и при выполнении арифметических операций не используется правило знаков.

Нетрадиционные позиционные системы счисления. Фибоначчиева ПСС. Уравновешенные СС.

• В 1958 году была построена ЭВМ Сетунь, работавшая на 3-ой уравновешенной арифметике. В 1962 – 1965 годах было 50 промышленных экземпляров, превосходивших по быстродействию ЭВМ такого же класса и более дешевые.

Создали Сетунь в МГУ Соболев, Брусенцов, Маслов.

В ЭВМ ENIAK использовалась двоично-пятиричная СС, в которой каждая цифра 10-ой СС заменялась двумя цифрами: одна – это 0 или 5, а вторая – это 0,1,2,3, или 4 так, чтобы в сумме получалась требуемая сумма.