2Дискретка / Метода / 1. Системы счисления

I. СИСТЕМЫ СЧИСЛЕНИЯ

Впервые числовые термины появились как качественные, а не как количест- венные. Они показывали лишь различие между одним и многими. Качественное разделение на единственное и множественное число и по сей день присутствует почти во всех разговорных языках.

Система счисления – это совокупность приемов обозначения (записи) чисел. Системы счисления подразделяют на позиционные и непозиционные. В позици-

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

1.1. Непозиционные системы счисления. Римская система счисления

Большинство непозиционных систем являлись аддитивными, т.е. числа в них образовывались путем сложения: 3=2+1, 4=2+2.

Примеры древних аддитивных непозиционных систем счисления:

1)Камиларои считали: 1=мал, 2=булан, 3=гулиба, 4=булан-булан и так далее.

2)Унарная система счисления. Простейшая система счисления – зарубки или палочки. В этой системе счисления удобно складывать, но она очень громоздка. Сейчас используется для обучения счету.

3)Древнеегипетская иероглифическая система счисления (2,5 в. до н.э.):

| – единица, ∩ – десять, С – сотня.

4)Древнегреческая система счисления – числа, 1, 2, …, 9, 10, 20, …, 90, 100, 200… обозначались буквами с чертой сверху. Позже эта традиция через Византию пришла в древнеславянскую письменность.

5)Древнеримская аддитивная система счисления: Ключевые числа 1, 5, 10, 50 100, 500, 1000 обозначались I, V, X, L, C, D и M. (V-“одна пятерня”, X-“две пятер- ни”, C-centum, D-demille и M-mille).

Современная Римская система счисления, отличается от древнеримской только тем, что не является чисто аддитивной.

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

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

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

Древнейшая позиционная система счисления была в Вавилоне. Ее возраст 2-3 тысячи лет.

Цифры: – 1, – 10. Основание: 60 Первоначально употреблялась для записи денежных единиц (1 мина серебра =

60 шекелям, 1 талант = 60 минам). В этой системе счисления первоначально не было 0, поэтому числа 1, 60, 3600 выглядели одинаково. Кроме того, в этой системе не было знака, отделяющего дробную и целую части. Тем не менее, эта система счис- ления дошла до наших дней – с ее помощью определяется время.

Система счисления индейцев племени майя:

Цифры: – 1, –5. Ключевые числа: 1, 20, 18·20, 18·202,…

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

Принцип поместного значения цифр и их начертание зародились в Индии в VI веке. В Европе они стали известны лишь в IX веке благодаря книге хорезмского ма- тематика Мухаммеда ибн Муса. Книга была написана на арабском языке, и поэтому цифры называются арабскими. Иногда эти цифры называются индийскими. В Рос- сии с индийской нумерацией познакомились только в XIII веке.

Лишь в XVII веке вошла в употреблении современная алгебраическая символи-

ка (знаки «=», «+», «-» и др.).

В дальнейшем будем рассматривать d-ичные позиционные системы счисления основание которых – d, а цифры – натуральные числа от 0 до d–1.

Записать число в d-ичной системе счисления означает представить это число либо в цифровой Ad = (anan−1an−2 …a1a0 ,a−1a−2 …a−k )d , либо в многочленной

Ad = andn + an−1dn−1 + an−2dn−2 + …a1d1 + a0 + a−1d−1 + a−2d−2 + …a−kd−k

формах.

1.3. Взаимосвязь систем счисления

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

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

Для облегчения запоминания договоримся под d-ичной системой понимать де- сятичную, а под q-ичной любую другую систему счисления (алгоритмы работоспо- собны и без этого ограничения).

I Алгоритм перевода целого числа Aq из q-ичной системы счисления в чис- ло Bd d-ичной системы.

1)Присвоить результату цифру старшего разряда.

2)Если цифры закончились – stop.

3)Умножить текущее значение результата на «старое» основание q по прави- лам d-арифметики.

4)Прибавить цифру следующего разряда и перейти на шаг 2.

Пример 1. Число 212314 заменить равным ему десятичным числом.

4212314 = (((210 * 410 +110 )* 410 + 210 )* 410 + 310 )* 410 +110 = 62110 3

II Алгоритм перевода целого числа Ad из d-ичной системы счисления в число Bq q-ичной системы.

1)Разделить «с остатком» по правилам d-ичной арифметики число Ad на число q, записанное в d-ичной системе.

2)Если результат ≥ q, то повторить пункт 1.

3)Цифрами искомого числа Bq являются остатки от деления, выписанные так, чтобы последний остаток являлся цифрой старшего разряда.

Пример 2. Число 153 заменить равным ему числом в системе счисления с основани-

ем q=4.

4 153=38*4+1, 38=9*4+2, 9=2*4+1.

15315310 = 21214 = 2 * 43 + 1* 42 + 2 * 4 + 1 = 4 * (4 * (4 * 2 + 1) + 2) + 1.3

IIIАлгоритм перевода правильных дробей из q-ичной системы счисления

вd -ичную.

1)Цифру младшего разряда числа 0,Aq разделить на «старое» основание q по правилам d-арифметики.

2)Если цифры закончились – stop.

3)Прибавить следующую цифру исходной дроби.

4)Текущее значение результата разделить на «старое» основание q по прави- лам d-арифметики и перейти на шаг 2).

IV Алгоритм перевода правильных дробей из d-ичной системы счисления

вq-ичную.

1)Умножить по правилам d-арифметики исходную дробь 0,Ad на «новое» ос- нование q, записанное в d-ичной системе.

2)Целую часть полученного произведения считать цифрой старшего разряда искомой дроби.

3)Если дробная часть равна 0 или достигнута требуемая точность, то stop. Иначе, дробную часть полученного произведения умножить по правилам d- арифметики на «новое» основание q, записанное в d-ичной системе и перей- ти на шаг 2).

Пример 3. Дробь 0,37510 заменить равной ей двоичной.

40,37510 * 210 = 0,75010 ,

0,7510 * 210 = 1,510 ,

0,510 * 210 = 1,010 .

Так как дробная часть оказалась равной нулю, то окончательный результат: 0,37510 = 0,0112 .3

Пример 4. Дробь 0,110 заменить равной ей двоичной.

40,110 * 210 = 0, 210 , 0,210 * 210 = 0, 410 , 0,410 * 210 = 0,810 ,

0,810 * 210 = 1,610 , 0,610 * 210 = 1, 210 , 0,210 * 210 = 0, 410

…

Таким образом, десятичная конечная дробь 0,110 в двоичной системе счисления представляется в виде периодической дроби 0,37510 = 0,0112 . 0,00011(0011)3

V Алгоритм перевода целых чисел из d-ичной системы счисления в dn-ичную систему счисления.

1)Разбить число справа налево на группы по n цифр.

2)Каждое получившееся n-значное число заменить цифрой dn-ичной системы

счисления.

VI Алгоритм перевода правильных дробей из d-ичной системы в dn-ичную систему счисления.

1)Разбить число слева направо на группы по n цифр.

2)Каждое получившееся n-значное число заменить цифрой dn-ичной системы счисления.

Пример 5.

101101011,10000111012 = 1 0110 10 11, 10 00 0111 012 = 11223, 201314 ,

101101011,10000111012 = 1 0110 1011, 1000 0111 01002 = 16B,87416

VII Алгоритм перевода чисел из dn-ичной системы счисления в d-ичную систему счисления.

Каждую цифру искомого числа заменить n-разрядным числом в новой системе счисления.

Пример 6.

35A,1716 = 3 5 A,1 716 = 0311 22, 01134 = 31122,01134 ,

35A,1716 = 3 5 A,1 716 = 0011 01011010, 0001 01112 = 1101011010,000101112 .

Последние три алгоритма имеют большое практическое значение. Обмен ин- формацией между узлами и устройствами большинства ЭВМ осуществляется путем передачи командных слов, которые, как правило, являются словами в двоичном ал- фавите. Использование двухбуквенного (0 и 1) алфавита диктуется инженерными требованиями. Однако пользоваться словами, записанными в таком алфавите, из-за большой длины слов и своеобразной «зрительной однородности» текста человеку неудобно. Поэтому программисты и инженеры все «машинные слова» при обсужде- нии обычно заменяют на эквивалентные им числа, записанные в шестнадцатирич- ной системе.

1.4. Двоичная система счисления

Официальное рождение двоичной арифметики связывают с именем Г.В. Лейб- ница. Он в 1703 году опубликовал статью, в которой были рассмотрены правила

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

До начала тридцатых годов XX века двоичная система счисления оставалась вне поля зрения прикладной математики. Потребность в создании надежных и про- стых по конструкции счетных механических устройств и удивительная простота выполнения действий над двоичными числами привели к более глубокому и актив- ному изучению особенностей двоичной системы как системы, пригодной для аппа- ратурной реализации. Первые двоичные вычислительные механические машины были построены во Франции и Германии. Пионером в проектировании вычисли- тельных устройств двоичного действия на электронно-ламповой основе является инженер Дж.В.Атанасов, болгарин по национальности, проживавший в США. Од- новременно с ним (1937г.) двоичную машину, но на релейной основе, спроектиро- вал Дж.Р.Штибиц. В 1941 году немецкий инженер Конрад Цуре построил сначала механическую, а затем и релейную двоичную вычислительную машину.

Утверждение двоичной арифметики в качестве общепринятой основы при кон- струировании ЭВМ с программным управлением состоялось под влиянием работы А.У. Беркса, Х.Х.Гольдсайна и Дж. фон Неймана о проекте первой ЭВМ с хранимой в памяти программой, написанной в 1946 году. В этой работе наиболее аргументи- ровано обоснованы причины отказа от десятичной арифметики и переход к двоич- ной системе счисления как основе машинной арифметики.

1.4.1. Двоичная арифметика

Арифметика двоичной системы счисления основана на использовании таблиц сложения и умножения цифр:

+	0	1
0	0	1
1	1	10

*	0	1
0	0	0
1	0	1

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

				11,12
				×
		101,11012		10,12
	+		+		111
		11,10112
			111

1001,10002	1000,112

Прежде всего, отметим, что и вычитание, и деление в двоичной арифметике можно осуществить по общепринятым правилам, аналогично тому, как это делается в десятичной системе счисления.

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

1.4.2. Вычитание с использованием двоичного дополнения. Умножение

Вся теория будет строиться сначала для десятичных чисел.

Десятичным дополнением n-разрядного числа A10 называется разность 10n−A10 . Например, десятичное дополнение числа 7 – 3, числа 342 – 658, числа 007 – 993.

Идея использования десятичного дополнения при вычитании основана на сле- дующих рассуждениях. Пусть необходимо найти разность A10 − B10 . Возможны слу- чаи:

а) A10 > B10 .

В этом случае рассмотрим тождество

A10 − B10 = A10 + (10n − B10 ) −10n ,

откуда следует правило нахождения разности:

–найти десятичное дополнение к вычитаемому;

–сложить найденное дополнение и уменьшаемое;

–зачеркнуть единицу старшего разряда и вместо нее поставить знак «+»

б) A10 < B10 .

Вэтом случае используем тождество (10n − A10 − (10n − B10 )),A10 − B10 = −

или, если через C10 обозначить сумму A10 + (10n − B10 ), то получим

A10 − B10 = −(10n − C10 ).

Отсюда следует, что искомая разность есть десятичное дополнение к числу C10 взя- тое со знаком «–».

Пример 7. Найти разность A10 − B10 .

41. A10 = 74 ; B10 = 39 .

Находим дополнение числа 39, имеем 102 − 39 = 61. Складываем уменьшаемое и найденное дополнение: A10 + 61 = 74 + 61 =135 . Отбрасываем единицу старшего разряда и получаем 35 (или 74-39=35).

2. A10 = 23 ; B10 = 47 .

Находим дополнение числа 47: 102 − 47 = 53 . Складываем уменьшаемое и най- денное дополнение: A10 + 53 = 23 + 53 = 76 . Так как единица в старшем разряде не

появилась, то находим десятичное дополнение числа 76: 102 − 76 = 24 , берем его со знаком минус и считаем искомой разностью: A10 − B10 = 23 − 47 = −24 .3

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

Алгоритм вычитания целых десятичных чисел

Шаг 1. Уравнять число разрядов в числах A10 и B10 , приписав впереди требуемое число нулей.

Шаг 2. Найти десятичное дополнение вычитаемого C10 = (10n − B10 ). Шаг 3. Найти сумму A10 + C10 = D10 .

Шаг 4. Если появилась единица в дополнительном старшем разряде числа D10 , то заменить ее знаком «+».В противном случае найти десятичное дополнение числа D10 и поставить перед ним знак «–».

Шаг 5. Полученное число считать искомой разностью A10 − B10 .

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

Приведенные рассуждения и основанный на них алгоритм могут быть построе- ны и в позиционной системе счисления с натуральным основанием, отличным от десяти. Однако наиболее эффективен такой подход к вычитанию в двоичной ариф- метике. Объясняется это тем, что в этой системе счисления очень просто находится «двоичное дополнение» (двоичным дополнением n-значного числа B2 является раз-

ность 2n − B2 ).

Алгоритм отыскания двоичного дополнения числа B2

Шаг 1. Все единицы числа B2 заменить на нули, а все нули – на единицы. Шаг 2. К полученному числу по правилам двоичной арифметики прибавить 1.

Чтобы получить алгоритм вычитания двоичных чисел, достаточно в приведен- ном выше алгоритме заменить слово «десятичный» словом «двоичный», а индекс «10» заменить индексом «2».

Пример 8.

Найти разность A2 − B2 .

A2 =1100112 , B2 =111012						A2 =10112 ; B2 =10011012
Находим двоичное дополнение C2 вычитаемого B2
+	1000102				+			0100102
			12							12
		1000112							0100112
C2 =1000112							C2 = 0100112
				Находим сумму D2 = A2 + C2
1100112					0010112
+ 100011					+ 010011
	2							2
10101102					0111102
D2 =10101102							D2 = 0111102
					Так как число D2 содержит столько же
					разрядов, что и числа A2 и B2 , то в соответ-
В соответствии с алгоритмом					ствии с алгоритмом находим дополнение
отбрасываем единицу в дополни-					числа D2 = 0111102 :
тельном старшем разряде					+1000012
					12
						1000102
					Найденное дополнение со знаком минус
A2 − B2 =1100112 −111012 =101102					A2 − B2 =10112 −1011012 = −1000102 .