Системы счисления

1. Происхождение и история развития систем счисления

1.1. Границы счета

На ранних ступенях развития общества люди почти не умели считать. Они отличали друг от друга совокупности двух и трех предметов; всякая совокупность, содержавшая большее число предметов, объединялась в понятии «много». Это был еще не счет, а лишь его зародыш.

Впоследствии способность различать друг от друга небольшие совокупности развивалась; возникли слова для обозначений понятий «четыре», «пять», «шесть», «семь». Последнее слово длительное время обозначало также неопределенно большое количество. Наши пословицы сохранили память об этой эпохе («семь раз отмерь - один раз отрежь», «у семи нянек дитя без глазу», «семь бед - один ответ» и т.д.).

С усложнением хозяйственной деятельности людей понадобилось вести счет в более обширных пределах. Для этого человек пользовался окружавшими его предметами, как инструментами счета: он делал зарубки на палках и на деревьях, завязывал узлы на веревках, складывал камешки в кучки и т.п. Такой вид счета носит название унарной системы счисления, т.е. система счисления, в которой для записи числа применяется только один вид знаков. Это удобно, так как сразу визуально определяется количество знаков и сопоставляется с количеством предметов, которые эти знаки обозначают. Все мы ходили в первый класс и считали там на счетных палочках - это отзвук той далекой эпохи. Кстати, от счета с помощью камешков ведут свое начало различные усовершенствованные инструменты, как, например, русские счеты, китайские счеты («сван-пан»), древнеегипетский «абак» (доска, разделенная на полосы, куда клались жетоны). Аналогичные инструменты существовали у многих народов. Более того, в латинском языке понятие «счет» выражается словом «calculatio» (отсюда наше слово «калькуляция»); а происходит оно от слова «calculus», означающего «камешек».

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

Поэтому, вполне естественно, что вновь возникавшие названия «больших» чисел часто строились на основе числа 10 - по количеству пальцев на руках; у некоторых народов возникали также названия чисел на основе числа 5 - по количеству пальцев на одной руке или на основе числа 20 - по количеству пальцев на руках и ногах.

На первых порах расширение запаса чисел происходило медленно. Сначала люди овладели счетом в пределах нескольких десятков и лишь позднее дошли до сотни. У многих народов число 40 долгое время было пределом счета и названием неопределенно большого количества. В русском языке слово «сороконожка» имеет смысл «многоножка»; выражение «сорок сороков» означало в старину число, превосходящее всякое воображение.

На следующей ступени счет достигает нового предела: десяти десятков, и создается название для числа 100. Вместе с тем слово «сто» приобретает смысл неопределенно большого числа. Такой же смысл приобретают потом последовательно числа тысяча, десять тысяч (в старину это число называлось «тьма»), миллион.

На современном этапе границы счета определены термином «бесконечность», который не обозначает какое либо конкретное число.

1.2. Десятичная система счисления

В современном русском языке, а также в языках других народов названия всех чисел до миллиона составляются из 37 слов, обозначающих числа 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 , 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000 (например, восемьсот пятнадцать тысяч триста девяносто четыре). В свою очередь названия этих 37 чисел, как правило, образованы из названий чисел первого десятка (1, 2, 3, 4, 5, 6, 7, 8, 9) и чисел 10, 100, 1000 (например, 18 = восемь на десять, 30 = тридесять и т.д.). В основе этого словообразования лежит число десять, и поэтому наша система наименований называется десятичной системой счисления.

Из упомянутого правила в разных языках имеются различные исключения, объясняющиеся историческими особенностями развития счета. В русском языке единственным исключением является наименование «сорок». Это исключение можно поставить в связь с тем, что число 40 играло некогда особую роль, означая неопределенно большое количество.

В тюркских языках (узбекском, казахском, татарском, башкирском, турецком и др.) исключение составляют наименования чисел 20, 30, 40, 50, тогда как названия чисел 60, 70, 80, 90 образованы из наименований для 6, 7, 8, 9. Во французском языке сохранились недесятичные названия чисел 20 и 80, причем 80 именуется quatrevingt, т.е. «четыре двадцать». Здесь мы имеем остаток древнего двадцатеричного счисления (по числу пальцев на руках и ногах). В латинском языке наименование числа 20 тоже недесятичное (viginti). Наименования чисел 18 и 19 образованы из названия 20 с помощью вычитания: 20-2 и 20-1 (duodeviginti, undeviginti, т.е. «два от двадцати», «один от двадцати»).

1.3. Развитие понятия числа

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

Так, в вавилонской системе мер веса (и денег) 1 талант составлял 60 мин, а одна мина - 60 шекелей. Соответственно с этим в вавилонской математике широко употреблялись шестидесятиричные дроби. В древнеримской весовой (и денежной) системе 1 асс делился на 12 унций; сообразно с этим римляне пользовались двенадцатиричными дробями.

Наши «обыкновенные дроби» широко употреблялись древними греками и индийцами. Правила действий с дробями, изложенные индийским ученым Брамагуптой (VIII век н.э.), лишь немногим отличаются от наших. Наша запись дробей тоже совпадает с индийской; только дробной черты индийцы не писали; греки записывали сверху знаменатель, а снизу числитель.

Индийской обозначение дробей и правила действий над ними были усвоены в IX веке в мусульманских странах благодаря узбекскому ученому Мухаммеду Хорземскому (аль-Хваризми). Они были перенесены в Западную Европу итальянским купцом и ученым Леонардо Фибоначчи из Пизы (XIII век).

Наряду с «обыкновенными» дробями до XVII века применялись (преимущественно в астрономии) шестидесятиричные дроби. Они были вытеснены десятичными дробями, введенными голландским купцом и выдающимся инженером-ученым Симоном Стевином (1548 - 1620).

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

Довольно поздно к семье чисел присоединился нуль. Первоначально слово «нуль» означало отсутствие числа (буквальный смысл латинского слова nullum - «ничто»). Для того чтобы это «ничто» считать числом, появились основания лишь в связи с рассмотрением отрицательных чисел.

1.4. Системы нумерации некоторых народов

1.4.1. Древнегреческая нумерация

В древнейшее время в Греции была распространена т.н. аттическая нумерация. Числа 1, 2, 3, 4 обозначались черточками , ,,. Число 5 записывалось знаком (древнее начертание буквы «пи», с которой начинается слово «пенте» - пять); числа 6, 7, 8, 9 обозначались , , , . Число 10 обозначалось (начальной буквой слова «дека» - десять). Числа 100, 1000 и 10000 обозначались , , . Числа 50, 500, 5000 обозначались комбинациями знаков 5 и 10, 5 и 100, 5 и 1000. Общую запись чисел в аттической нумерации иллюстрирует пример 1.1.

Пример 1.1 Запись чисел в аттической системе счисления

	,
	,
	,
	.

В третьем веке до н.э. аттическая нумерация была вытеснена так называемой ионийской системой. В ней числа 1 - 9 обозначались первыми девятью буквами алфавита; числа 10, 20, 30, 90 - следующими девятью буквами; числа 100, 200, 900 - последними девятью буквами.

Таблица 1.1 Обозначение чисел в ионийской системе нумерации

Обозна- чение	Название	Значе-ние	Обозна-чение	Название	Значе-ние	Обозна-чение	Назва-ние	Значе-ние
	Альфа	1		Йота	10		Ро	100
	Бета	2		Каппа	20		Сигма	200
	Гамма	3		Лямбда	30		Тау	300
	Дельта	4		Мю	40		Ипсилон	400
	Эпсилон	5		Ню	50		Фи	500
	Фауб	6		Кси	60		Хи	600
	Дзета	7		Омикрон	70		Пси	700
	Эта	8		Пи	80		Омега	800
	Тэта	9		Коппа	90		Сампи	900

Следует отметить, что буквы «фау», «коппа» и «сампи» отсутствуют в современном греческом алфавите. Для обозначения тысяч и десятков тысяч пользовались теми же цифрами с добавлением особого значка ` сбоку.

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

Пример 1.2 Запись чисел в ионийской системе счисления

	,
	,
	,
	,
	.

Такую же алфавитную нумерацию имели в древности евреи, арабы и многие другие народы Ближнего Востока.

1.4.2. Славянская нумерация

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

Таблица 1.2 Обозначение чисел в древнеславянской системе нумерации

Обозна-чение	Название	Значе-ние	Обозна-чение	Название	Значе-ние	Обозна-чение	Назва-ние	Значе-ние
	Аз	1		И	10		Рцы	100
	Веди	2		Како	20		Слово	200
	Глаголь	3		Люди	30		Твердо	300
	Добро	4		Мыслите	40		Ук	400
	Есть	5		Наш	50		Ферт	500
	Зело	6		Кси	60		Хер	600
	Земля	7		Он	70		Пси	700
	Иже	8		Покой	80		Омега	800
	Фита	9		Червь	90		Цы	900

В России славянская нумерация сохранилась до конца XVII века. При Петре I возобладала так называемая «арабская нумерация», которой мы пользуемся и сейчас. Славянская нумерация сохранялась только в богослужебных книгах. В таблице 1.2 приведены славянские цифры.

При записи чисел, больших 10, цифры писались слева направо в порядке убывания десятичных разрядов (однако иногда для чисел от 11 до 19 единицы записывались ранее десяти). Для обозначения тысяч перед числом их (слева внизу) ставился особый знак .

Пример 1.3 иллюстрирует написание чисел в славянской системе нумерации.

Пример 1.3 Запись чисел в древнеславянской системе счисления

	,
	,
	,
	.

1.4.3. Римская нумерация

Древние римляне пользовались нумерацией, которая сохраняется до настоящего времени под именем «римской нумерации». Мы пользуемся ей для обозначения веков, юбилейных дат, наименования съездов и конференций, для нумерации глав книги или строф стихотворения.

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

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

Все целые числа (до 5000) записываются с помощью повторения вышеприведенных цифр. При этом, если большая цифра стоит перед меньшей, то они складываются, если же меньшая стоит перед большей (в этом случае она не может повторяться), то меньшая вычитается из большей. Подряд одна и та же цифра ставится не более трех раз. Рассмотрим примеры.

	,
	,
	,
	.

Выполнение арифметических действий над многозначными числами в этой записи очень громоздко и трудно. Тем не менее римская нумерация преобладала в Италии до XIII века, а в других странах Западной Европы - до XVI века.

1.4.4. Вавилонская поместная нумерация

В древнем Вавилоне примерно за 40 веков до нашего времени создалась поместная (позиционная) нумерация, т.е. такой способ изображения чисел, при котором одна и та же цифра может обозначать разные числа, смотря по месту, занимаемому этой цифрой. Наша теперешняя нумерация - тоже поместная, однако в вавилонской поместной нумерации ту роль, которую играет у нас число 10, играло число 60, и потому эту нумерацию называют шестидесятиричной. Числа, меньшие 60, обозначались с помощью двух знаков: для единицы и для десятка . Они имели клинообразный вид, так как вавилоняне писали на глиняных дощечках палочками треугольной формы. Эти знаки повторялись нужное число раз. При отсутствии промежуточного разряда применялся знак. Запись чисел до 60 показана в примере 1.5. Способ обозначения чисел, больших 60 сведен в таблицу 1.3.

Пример 1.5 Запись вавилонской клинописью чисел до 60

	,
	,
	,
	.

Таблица 1.3 Запись вавилонской клинописью чисел, больших 60

Обозначение	Значение	Способ образования
	302
	1295
	3725
	7203

Шестидесятиричная запись целых чисел не получила распространения за пределами ассиро-вавилонского царства, но шестидесятиричные дроби проникли далеко за эти пределы: в страны Среднего Востока, Средней Азии, в Северную Африку и Западную Европу. Они широко применялись, особенно в астрономии, вплоть до изобретения десятичных дробей. Следы шестидесятиричных дробей сохраняются и поныне в делении углового и дугового градуса (а также часа) на 60 минут и минуты на 60 секунд.

1.4.5. Индийская поместная нумерация

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

Первоначально этими знаками представлялись числа 1, 2, 3, … , 9, 10, 20, 30, … , 90, 100, 1000; с их помощью записывались другие числа. Впоследствии был введен особый знак (жирная точка или кружок) для указания пустующего разряда; знаки для чисел, больших 9, вышли из употребления, и нумерация «деванагари» превратилась в десятичную поместную систему. К середине VIII века позиционная система нумерации получает в Индии широкое применение. Примерно в это время она проникает и в другие страны (Индокитай, Китай, Тибет, в Иран и др.). Решающую роль в распространении индийской нумерации в арабских странах сыграло руководство, составленное в начале IX века узбекским ученым Мухаммедом из Хорезма (аль-Хваризми). Оно было переведено в Западной Европе на латинский язык в XII веке. В XIII веке индийская нумерация получает преобладание в Италии. В других странах Западной Европы она утверждается в XVI веке. Европейцы, заимствовавшие индийскую нумерацию от арабов, называли ее «арабской». Это исторически неправильное название удерживается и поныне.

Из арабского языка заимствовано и слово «цифра» (по-арабски «сыфр»).

Форма индийских цифр претерпевала многообразные изменения. Та форма, в которой мы их пишем сейчас, установилась в XVI веке.

2. Основные понятия и определения

Выше мы говорили о системах счисления, не вдаваясь в подробности этого понятия. Каково же научное определение системы счисления?

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

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

В непозиционных системах любое число определяется как некоторая функция от численных значений совокупности цифр, представляющих это число. Цифры в непозиционных системах счисления соответствуют некоторым фиксированным числам. Пример непозиционной системы - рассмотренная ранее римская система счисления. Дpевние египтяне пpименяли систему счисления, состоящую из набоpа символов, изобpажавших pаспpостpаненные пpедметы быта. Совокупность этих символов обозначала число. Расположение их в числе не имело значения, отсюда и появилось название.

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

В вычислительной технике непозиционные системы не применяются.

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

Количества и количественные составляющие, существующие реально могут отображаться различными способами. В общем случае в позиционной системе счисления число N может быть представлено как:

, где: (2.1)

- основание системы счисления (целое положительное число, равное числу цифр в данной системе);

- любые цифры из интервала от нуля до .

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

Каждой позиции в числе соответствует позиционный (разрядный) коэффициент или вес. Покажем это на примере десятичного числа:

Пример 2.1 Способ образования десятичного числа

Для десятичной системы соответствия между позицией и весом следующее:

(2.2)

в общем случае:

(2.3)

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

Вычислительные машины в принципе могут быть построены в любой системе счисления. Но столь привычная для нас десятичная система окажется крайне неудобной. Если в механических вычислительных устройствах, использующих десятичную систему, достаточно просто применить элемент со множеством состояний (колесо с десятью зубьями), то в электронных машинах надо было бы иметь 10 различных потенциалов в цепях.

Наиболее удобной для построения ЭВМ оказалась двоичная система счисления, т.е. система счисления, в которой используются только две цифры: 0 и 1, т.к. с технической точки зрения создать устройство с двумя состояниями проще, также упрощается различение этих состояний.

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

3. Двоичная система счисления: основные сведения

3.1. История возникновения двоичной системы счисления

Двоичная система счисления, т.е. система с основанием , является «минимальной» системой, в которой полностью реализуется принцип позиционности в цифровой форме записи чисел. В двоичной системе счисления значение каждой цифры «по месту» при переходе от младшего разряда к старшему увеличивается вдвое.

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

3.2. Основные понятия машинной арифметики

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

Отверстие есть или отсутствует (перфолента или перфокарта);

Материал намагничен или размагничен (магнитные ленты, диски);

Уровень сигнала большой или маленький.

Существуют специальные термины, широко используемые в вычислительной технике: бит, байт и слово.

Битом называют один двоичный разряд. Крайний слева бит числа называют старшим разрядом (он имеет наибольший вес), крайний справа - младшим разрядом (он имеет наименьший вес).

Восьмибитовая единица носит название байта.

Многие типы ЭВМ и дискретных систем управления перерабатывают информацию порциями (словами) по 8, 16 или 32 бита (1, 2 и 4 байта). Двоичное слово, состоящее из двух байт4 Взаимный перевод двоичных и десятичных чисел и элементарные двоичные арифметические действия

3.3. Представление двоичных чисел и перевод их в десятичные

Совершенно очевидно, что двоичное число представляется последовательностью нулей и единиц - разрядов. Как и в любой позиционной системе, каждому разряду присвоен определенный вес - показатель степени основания системы. Веса первых 10 позиций представлены в таблице 4.1.

Таблица 4.1 Веса первых десяти позиций двоичной системы счисления

Позиция	9	8	7	6	5	4	3	2	1	0
Вес	512	256	128	64	32	16	8	4	2	1
Образование

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

Как и в десятичной системе, в двоичной системе счисления для отделения дробной части используется точка (двоичная точка). Каждая позиция слева от этой точки также имеет свой вес - вес разряда дробной части числа. Значение веса в этом случае равно основанию системы счисления (т.е. двойке), возведенному в отрицательную степень.

Получить десятичное число из двоичного чрезвычайно просто. Согласно формуле 2.3 для двоичной системы счисления получаем:

(4.1)

Пример 4.1 иллюстрирует процесс получения десятичного числа из двоичного.

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

3.4. Преобразование десятичных чисел в двоичные

Перевод из двоичной системы в десятичную несколько сложнее. Рассмотрим несколько алгоритмов.

3.4.1. Метод вычитания

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

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

3.4.2. Метод деления

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

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

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

	2
148	-74	2
1	74	-37	2
	0	36	-18	2
		1	18	-9	2
			0	8	-4	2
				1	4	-2	2
					0	2	-1	2
						0	0	0
							1		старший разряд
(10010101)2=(149)10	ответ

3.4.3. Метод умножения

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

Число умножается на 2, если результат 1, то в старший разряд записывается единица, если нет, то нуль. Умножаем на 2 дробную часть результата и повторяем процедуру. И так далее до получения нужной степени точности или до обнуления результата.

Пример 4.4 Перевод десятичного числа в двоичное методом умножения

3.5. Арифметические действия над двоичными числами

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

3.5.1. Двоичное сложение

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

Пример 4.5 Сложение двоичных чисел и

+	101101
	111110
	010011	- поразрядная сумма без учета переносов

+	1011000	- переносы
	0010011
	1001011	- поразрядная сумма без учета повторных переносов

+	0100000	- повторные переносы
	1001011
	1101011	- окончательный результат

Легко произвести проверку:

,

,

,

.

Пример 4.6 Сложение двоичных чисел и

+	110,	1011
	10111,	10101
	10001,	00011	- поразрядная сумма без учета переносов

+	11 1,	1	- переносы
	10001,	00011
	11100,	01011	- поразрядная сумма без учета повторных переносов

+	1 ,		- повторные переносы
	11100,	01011
	11110,	01011	- окончательный результат

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

3.5.2. Двоичное вычитание

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

Пример 4.7 Вычитание двоичных чисел и

-	11010,	1011
	1101,	01111
	1101,	00111

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

Рассмотрим четырехразрядный десятичный счетчик, какие в автомобиле отсчитывают пройденный путь. Пусть он показывает число 2, если вращать его в обратном направлении, то сначала появится 1, затем 0, после 0 появится число 9999. Сложим, к примеру, 6 с этим числом:

+	6
	9999
	10005

Если пренебречь единицей переноса и считать 9999 аналогом -1, то получим верный результат: .

Число 9999 называется десятичным дополнением числа 1. Таким образом, в десятичной системе счисления отрицательные числа могут быть представлены в форме десятичного дополнения, а знак минус можно опустить. Двоичное дополнение числа определяется как то число, которое будучи прибавлено к первоначальному числу, даст только единицу переноса в старшем разряде.

Пример 4.8 Двоичное дополнение числа

+	010101111	- число
	101010001	- двоичное дополнение
	1000000000	- сумма
- единица переноса

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

010101111	- число
101010000	- обратный код

прибавить к обратному коду единицу, образовав таким образом дополнительный код:

	101010000	- обратный код
	1
	101010001	- дополнительный код

Пример 4.9 Вычитание в дополнительном коде

- обратный код,

- дополнительный код.

100101₂=5₁₀ (верно).

3.5.3. Двоичное умножение

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

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

Умножение производится, начиная с младшего или старшего разряда множителя, что и определяет направление сдвига. Если сомножители имеют дробные части, то положение запятой в произведении определяется по тем же правилам, что и для десятичных чисел.

Пример 4.10 Умножение двоичных чисел и

3.5.4. Двоичное деление

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

Пример 4.11 Деление двоичных чисел

1) 18:2			2) 14:4
10010	10		1110	100
10	1001=(9)10		100	11,1=(3,5)10
00			110
00			100
001			100
000			100
10			0
10
00

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

4. Представление чисел в ЭВМ, кодирование

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

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

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

В ЭВМ применяются две основные формы представления чисел: полулогарифмическая - с плавающей запятой и естественная - с фиксированным положением запятой.

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

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

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

Рассмотрим подробнее эти два формата.

4.1.1. Числа с фиксированной запятой

Формат для чисел с запятой, фиксированной перед старшим разрядом. В этом формате могут быть с точностью до представлены числа (правильные дроби) в диапазоне

.

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

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

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

Достоинство представления чисел в форме с фиксированной запятой состоит в простоте выполнения арифметических операций.

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

4.1.2. Числа с плавающей запятой

При использовании плавающей запятой число состоит из двух частей: мантиссы m, содержащей значащие цифры числа, и порядка p, показывающего степень, в которую надо возвести основание числа q, чтобы полученное при этом число, умноженное на мантиссу, давало истинное значение представляемого числа:

(5.1)

Мантисса и порядок представляются в двоичном коде. Обычно число дается в нормализованном виде, когда его мантисса является правильной дробью, причем первая значащая цифра (единица) следует непосредственно после запятой: например, где m=0,1010; p=10; q=2

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

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

Нормализованные двоичные числа с плавающей запятой представляют значения модуля в диапазоне:

,

где - максимальное значение модуля порядка.

Так, при p=7 -1==63 и диапазон представления модулей нормализованных чисел:

,

Таким образом, диапазон чисел:

Для расширения диапазона представляемых чисел при фиксированной длине разрядной сетки (m+p) в качестве основания системы счисления выбирается . При этом число, представляемое в разрядной сетке, приобретает значения . Нормализованная мантисса 16-ричного числа с плавающей запятой имеет значения, лежащее в диапазоне . Признаком нормализации такого числа является наличие хотя бы одной единицы в четырех старших разрядах модуля мантиссы. Диапазон представления чисел в этом случае существенно расширяется, находясь при том же количестве разрядов в пределах от до .

4.2. Прямой, обратный и дополнительный коды. Модифицированный код

При рассмотрении элементарных арифметических операций над двоичными числами мы уже коснулись темы отрицательных двоичных чисел. Теперь рассмотрим ее подробнее.

Для кодирования знака двоичного числа используется старший ("знаковый") разряд (ноль соответствует плюсу, единица - минусу).

Такая форма представления числа называется прямым кодом.

В ЭВМ прямой код применяется только для представления положительных двоичных чисел. Для представления отрицательных чисел применяется либо дополнительный, либо обратный код, так как над отрицательными числами в прямом коде неудобно выполнять арифметические операции.

Правила для образования дополнительного и обратного кода состоят в следующем:

для образования дополнительного кода отрицательного числа необходимо в знаковом разряде поставить единицу, а все цифровые разряды инвертировать (заменить 1 на 0, а 0 - на 1), после чего прибавить 1 к младшему разряду;

для образования обратного кода отрицательного числа необходимо в знаковом разряде поставить единицу, а все цифровые разряды инвертировать;

при данных преобразованиях нужно учитывать размер разрядной сетки.

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

В таблице 5.1 приведены десятичные числа и их двоичные пpедставления в тpех различных формах. Интеpесно в ней вот что. Если начать счет с числа 1000 (-8) и двигаться вниз по столбцам, то в дополнительном коде каждое последующее число получается пpибавлением единицы к пpедыдущему без учета пеpеноса за пpеделы четвеpтого pазpяда Так пpосто эту опеpацию в пpямом и обpатном кодах не осуществить. Эта особенность дополнительного кода и явилось пpичиной пpедпочтителного пpименения его в совpеменных микpо и миниЭВМ.

Итак, числа, пpедставленные в дополнительном коде, складываются по пpавилам двоичного сложения, но без учета каких либо пеpеносов за пpеделы стаpшего pазpяда. Рассмотpим это на пpимеpах 5.1.

Таблица 5.1. Прямой, обратный и дополнительный коды

Десятичное число	Прямой код	Обратный код	Дополнительный код
-8	-	-	1000
-7	1111	1000	1001
-6	1110	1001	1010
-5	1101	1010	1011
-4	1100	1011	1110
-3	1011	1100	1101
-2	1010	1101	1110
-1	1001	1110	1111
0	1000 0000	1111 0000	0000
1	0001	0001	0001
2	0010	0010	0010
3	0011	0011	0011
4	0100	0100	0100
5	0101	0101	0101
6	0110	0110	0110
7	0111	0111	0111

Пример 5.1 Двоичное сложение в дополнительном коде

1)	+	+2	+	0010		2)	+	-2	+	1110		3)	+	+5	+	0101
		+5		0101				-6		1010				-4		1100
		+7		0111				-8		1000				+1		0001

Еще одним достоинством дополнительного кода является то, что нуль, в отличие от пpямого и обpатного кодов, пpедставляется одним кодом. Наличие 0 в знаковом бите пpи пpедставлении нуля опpеделяет его как величину положительную, что согласуется с математической теоpией чисел и соглашениями, пpинятыми во всех языках пpогpаммиpования.

Из приведенных примеров следует, что положительные числа в прямом, обратном и дополнительном кодах совпадают. В прямом и обратном коде нуль имеет два представления - «положительный» и «отрицательный» нуль.

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

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

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

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

Признаком переполнения служит появление в знаковом разряде суммы комбинации 01 при сложении положительных чисел (положительное переполнение) или 10 при сложении отрицательных чисел (отрицательное переполнение). Старший знаковый разряд в этих случаях содержит истинное значение знака суммы, а младший является старшей значащей цифрой числа. Для коррекции переполнения число нужно сдвинуть в разрядной сетке на один разряд вправо, а в освободившийся старший знаковый разряд поместить цифру, равную новому значению младшего знакового разряда. После корректировки переполнения мантиссы результата необходимо увеличить на единицу порядок результата.

4.3. Двоично-десятичное кодирование

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

При двоично-десятичной записи каждая цифра десятичного числа заменяется четырехзначным двоичным числом - тетрадой (таблица 5.2).

Таблица 5.2 Наиболее распространенные двоично-десятичные коды чисел от 0 до 9

Десятичное число	Двоично-десятичный код (8421)	Код Айкена (2421)	Код «с избытком 3»
0 1 2 3 4 5 6 7 8 9	0 0 0 0 0 0 0 0 1 1	0 0 0 0 1 1 1 1 0 0	0 0 1 1 0 0 1 1 0 0	0 1 0 1 0 1 0 1 0 1	0 0 0 0 0 1 1 1 1 1	0 0 0 0 1 0 1 1 1 1	0 0 1 1 0 1 0 0 1 1	0 1 0 1 0 1 0 1 0 1	0 0 0 0 0 1 1 1 1 1	0 1 1 1 1 0 0 0 0 1	1 0 0 1 1 0 0 1 1 0	1 0 1 0 1 0 1 0 1 0

Например, число в двоично-десятичном коде записывается в виде 0011 0110 0000. Для выполнения сложения и вычитания двоично-десятичных чисел наиболее удобно использовать самодополняющиеся коды, к числу которых относятся код Айкена, код “с избытком 3 ”. Код Айкена отличается от обычного двоично-десятичного, имеющего весовые коэффициенты разрядов в тетрадах 8421, другими значениями весовых коэффициентов разрядов: 2421. Код “с избытком 3”получается из обычного двоично-десятичного арифметическим прибавлением числа 3 (двоичное число 0011).

Как видно из таблицы 5.2 обратный код числа, представленного в каком-либо самодополняющемся двоично-десятичном коде ,является его двоичным дополнением до 9. Например, число 5 в коде «с избытком 3» =1000 имеет обратный код =0111, соответствующий числу 4 в коде «с избытком 3», которое «дополняет» число 5 до 9, так как 5+4=9.

При записи чисел в кодах ASCII цифрам от 0 до 9 поставлены в соответствие восьмиразрядные двоичные коды от 00110000 до 00111001.

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

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

5.1. Сложение чисел с фиксированной запятой

Алгебраическое сложение чисел с фиксированной запятой в цифровых машинах может производиться в одном из машинных кодов: прямом, дополнительном или обратном. Чаще всего используется либо дополнительный, либо обратный код. При этом знаковый разряд и цифровая часть числа рассматривается как единое целое, в результате чего с отрицательными числами машина оперирует как с положительными, независимо от того, представлены ли они в виде правильных дробей или в виде целых чисел. Главное достоинство дополнительного и обратного кодов заключается в том, что правильный знак суммы получается автоматически в процессе суммирования знаковых цифр операндов и цифры переноса из соседнего младшего разряда. В случае возникновения единицы переноса из знакового разряда суммы ее нужно отбросить при сложении в дополнительном коде и прибавить к младшему разряду суммы при сложении в обратном коде (т. е. произвести циклический перенос единицы переполнения).

Алгебраическое сложение многоразрядных чисел обычно организуется как регулярный процесс, состоящий из n одинаковых операций поразрядного сложения-вычитания, где n - количество разрядов в каждом из операндов).

При этом в зависимости от знаков слагаемых возможны четыре случая:

1) Х₁ > 0, Х₂ > 0, Х₃ = Х₁ + Х₂ > 0;

2) Х₁ > 0, Х₂ < 0, Х₃ = Х₁ + Х₂ > 0;

3) Х₁ > 0, Х₂ < 0, Х₃ = Х₁ + Х₂ < 0;

4) Х₁ < 0, Х₂ < 0, Х₃ = Х₁ + Х₂ < 0;

5.2. Сложение чисел с плавающей запятой

Если имеются два числа в нормальной форме: Х₁ = m₁ 10^P1 и Х₂ = m₂ 10^P2 , то для того чтобы их можно было сложить, нужно предварительно привести их к одному и тому же порядку Робщ, т. е. преобразовать одно из слагаемых, например, первое следующим образом:

Х₁ = m₁ 10^P1 = m₁^* 10^P1 = m₁^* 10^Pобщ

Далее можно вынести степень основания системы за скобки и произвести сложение мантисс: Х₁ + Х₂= m₁^* 10^Pобщ + m₂ 10^Pобщ. = (m₁^* + m₂ ) 10^Pобщ

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

Машинная операция сложения чисел в нормальной форме распадается таким образом, на 4 этапа:

Уравниваются порядки слагаемых: меньший порядок увеличивается до большего, мантисса преобразуемого числа сдвигается вправо (число денормализуется) на соответствующее количество разрядов. Практически в машинах производится вычитание порядков операндов. Знак и модуль разности Р1 - Р2 определяют соответственно, какое из слагаемых нужно преобразовывать и на сколько единиц следует сдвигать мантиссу преобразуемого числа.

Производится преобразование мантисс слагаемых в один из модифицированных кодов.

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

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

5.3. Умножение чисел с фиксированной запятой

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

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

0 0 = 0

0 1 = 1

1 0 = 1

1 1 = 0

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

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

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

5.4. Умножение чисел с плавающей запятой

Если имеем два сомножителя, заданные в нормальной форме Х₁ = m₁ 10^P1 и Х₂=m₂10^P2, то их произведение определяется следующим образом:

Х₁ Х₂ = m₁ m₂ 10^P1+P2.

Анализ этого соотношения показывает, что умножение чисел в машинах с плавающей запятой производится в четыре этапа:

Определение знака произведения путем сложения по модулю два знаковых цифр мантисс сомножителей.

Перемножение модулей мантисс сомножителей по правилам для дробных чисел с фиксированной запятой.

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

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

7. Другие системы счисления

Пpи наладке аппаpатных сpедств (пpогpамм BIOS и т.д.) и написании новых пpогpамм (особенно на языках низкого уpовня типа ассемблеpа или C) чисто возникает необходимость заглянуть в память машины, чтобы оценить ее текущее состояние. Но там все заполнено длинными последовательностями нулей и единиц, очень неудобных для воспpиятия. Кpоме того, естественные возможности человеческого мышления не позволяют оценить быстро и точно величину числа, пpедставленного, напpимеp , комбинацией из 16 нулей и единиц. Для облегчения воспpиятия двоичного числа решили разбить его на гpуппы pазpядов, напpимеp, по тpи или четыре pазpяда. Эта идея оказалась удачной, так как последовательность из 3 бит имеет 8 комбинаций, а последовательность из 4 бит -16 комбинаций. Числа 8 и 16 - степени двойки, поэтому легко находить соответствие между двоичными числами. Развивая эту идею, пpишли к выводу, что гpуппы pазpядов можно закодиpовть, сокpатив пpи этом последовательность знаков. Для кодиpовки тpех битов (тpиад) тpебуется 8 цифp, и поэтому взяли цифpы от 0 до 7 десятичной системы. Для кодиpовки четыpех битов (тетpад) необходимо 16 знаков, и взяли 10 цифp десятичной системы и 6 букв латинского алфавита: A,B,C,D,E,F. полученные системы, имеющие в основании 8 и 16 , назвали соответственно восьмеричной и шестнадцатеричной.