Глава 7 На пороге цифрового века

Теперь в своей анкете в графе «Владение иностранными языками» вы можете гордо написать: «Бегло считаю по-японски до десяти…»

aikido-russia.ru

Все началось, конечно, с Аристотеля, который жил в IV веке до нашей эры. Когда читаешь вступление к любой популярной книге, посвященной чему угодно — от изящных искусств до биологии, химии, физики и математики, — возникает впечатление, что Аристотель был каким-то сверхчеловеком. Тем не менее, авторы не врут, просто знаний было тогда накоплено еще не очень много, и обозреть их все — задача вполне посильная для человека острого ума и выдающихся способностей, каким Аристотель, несомненно, был.

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

Заметки на полях

Аристотель, между прочим, четко разделял науку и ремесла («техно», по-гречески) — позиция, которая была странным образом утрачена уже почти на наших глазах, во второй половине XX века, когда в 1956 году Нобелевскую (научную) премию впервые дали за технологическое достижение — изобретение транзистора. И пошло-поехало — в некоторых источниках я встречал утверждения, что существование микропроцессоров есть выдающееся научное достижение. И, раз уж мы заговорили на философские темы, уместно сделать еще одно замечание. Дело в том, что почти все «обычные» достижения технологического века (паровой двигатель, телеграф, телефон, самолет, телевизор, автомобиль и т. п.) в некотором смысле изобретать было не надо — идеи передачи речи или изображения на расстояние (волшебное зеркальце), или передвижения с большой скоростью по воздуху (ковер-самолет) были выдвинуты давно, вероятно, задолго даже до Аристотеля. Нужно было придумать только способы технического воплощения этих идей. Если завтра изобретут антигравитацию, вы, с детства читавшие фантастические романы, сильно ли удивитесь? А вот никаких таких «компьютеров» не существовало и в помине — в некотором смысле это единственное настоящее изобретение, основанное на чисто идеальных предпосылках, в материальном мире никаких аналогов не имевшее — кроме, конечно, самого человеческого разума. И люди — самые уважаемые, крупные математики — всерьез верили, что именно искусственный разум они и изобрели, не будучи в силах поверить, что это действительно абсолютно новая, ранее не существовавшая вещь, которой не надо искать аналогий в повседневности. Компьютеры к разуму имеют такое же отношение, как интернет-путешествие к реальной охотничьей экспедиции в Африку — это всего лишь имитационное моделирование отдельных немногочисленных сторон деятельности разума. Что совершенно не умаляет значимости самого изобретения, кстати, скорее наоборот.

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

Булева алгебра

Законы аристотелевой логики, которые с его лихой подачи стали идентифицироваться с законами мышления вообще, неоднократно пытались привести в математическую форму. Некто Луллий в ХIII веке попытался даже механизировать процесс логических рассуждений, построив «Всеобщий решатель Задач» (несомненно, это была первая попытка построения «думающей машины»). Затем формализацией логики занимался Лейбниц и многие другие, пока, в конце концов, все не сошлось в двух работах английского математика Джорджа Буля, который жил и работал уже в середине XIX века.

Заметки на полях

Любопытно название второй из этих работ — «Исследование законов мышления», первая же работа называлась поскромнее, но без «мышления» и тут не обошлось — в названии фигурировало слово «рассуждения». Значит, и сам Буль, и все его предшественники в течение более чем двух тысяч лет, и еще сто с лишним лет после него — никто так и не усомнился, что в основе мышления лежит именно та логика, которая называется «аристотелевой». Это была такая, как сейчас модно говорить, парадигма. И лишь в XX веке, после работ Геделя и Тьюринга, и особенно в связи с благополучно провалившимися (как и у Луллия за 700 лет до того) попытками создания «искусственного интеллекта», до ученых наконец начало доходить, что мышление вовсе не имеет логической природы, а логика есть лишь удобный способ сделать свои рассуждения доступными окружающим, т. е. перевести их в вербальную форму.

Рис. 7.1. Клод Элвуд Шеннон (Claude Elwood Shannon, 1916–2001).

_{Фото Lucent Technologies Inc./Bell Labs}

Главное для нашего повествования свойство логики обнаружил в своей магистерской диссертации от 1940 года великий Клод Шеннон (которому, как автору теории информации, мы вообще обязаны самим существованием цифрового века). Оказалось, что абстрактные булевы законы, не интересные, в общем, никому, кроме математиков (да и те сначала сомневались, стоит ли причислять логику к математическим дисциплинам), в точности совпадают с принципами функционирования реально существующих объектов — релейных электрических схем.

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

Но довольно рассуждений, перейдем к практике.

Основные операции алгебры Буля

Булева алгебра имеет дело с абстрактными логическими переменными (операндами), для которых определены некоторые операции, подчиняющиеся определенным правилам:

• логическое сложение двух операндов (операция объединения, операция «ИЛИ» или «OR», обозначается обычным знаком сложения);

• логическое умножение двух операндов (операция пересечения, операция «И» или «AND», мы будем обозначать ее крестиком, чтобы отличить от обычного умножения)[5];

• отрицание для одного операнда (операция «НЕ» или «NOT», обозначается черточкой над символом операнда).

Остальные операции могут быть выведены из сочетания этих трех основных. Любая конкретная интерпретация булевых операндов — математическая или техническая — должна отвечать этим установленным правилам. Например, оказалось, что логическим операндам отвечают множества (отсюда названия операций «пересечение» и «объединение»). Но нас больше интересуют технические приложения, которые, однако, ничего не меняют в принципе: операция пересечения множеств совершенно адекватна операции «И» с логическими переменными, как и соответствующей манипуляции с выключателями в электрической сети, о чем далее.

В булевой алгебре многое совпадает с обычной (например, правила типа А + В = В + А; или А + (В + С) = (А + В) + С), но для нас важны как раз отличия. Вот они: А + А = А (а не 2А, как было бы в обычной алгебре), а также А х А = А (а не А2). Последнее уравнение в обычной алгебре, впрочем, имело бы решение, причем сразу два: 0 и 1. Таким путем обычно и переходят к интерпретации булевых операндов, как логических переменных, которые могут иметь только два состояния: 1 и 0 или «правда» (True) и «ложь» (False). Тогда мы действительно можем с помощью определенных выше действий записывать некоторые словесные высказывания в виде уравнений и вычислять их значения, что дает иллюзию формального воспроизведения процесса мышления. Но сначала надо определить, как и в обычной алгебре, правила, которым подчиняются операции, т. е. таблицы логического сложения и умножения. Они таковы:

0 + 0 = 0    0 x 0 = 0

0 + 1 = 1    0 x 1 = 0

1 + 0 = 1    1 x 0 = 0

1 + 1 = 1    1 x 1 = 1

Операция отрицания «НЕ», понятно, меняет 1 на 0 и наоборот.

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

Пусть высказывание состоит в следующем: <а меньше нуля или х больше единицы и у меньше двух». Как записать это высказывание? Введем следующие логические переменные: А = (х < 0); В = (х > 1); С = (у < 2). Как мы видим, все они могут принимать только два значения — «правда» (если условие выполняется) и «ложь» (если не выполняется). Обозначим значение всего выражения через D. Тогда высказывание запишется в виде логического уравнения:

D = (А + В) х С. (7.1)

Возможны другие варианты записи этого выражения:

• D = (A ИЛИ В) И С (по-русски);

• D = (A OR В) AND С (по-английски);

• D = ((x <0) or (x > 1)) and (у < 2) (язык программирования Pascal);

• D = ((x < 0) | (x > 1)) & (у < 2) (язык программирования С).

Рассмотрим подробнее возможные варианты решения уравнения 7.1. Пусть х = 0,5, у = 1. Чему будет равно D в этом случае? Очевидно, что выражение (А + В) примет значение «ложь» (или 0), т. к. x не удовлетворяет ни одному из условий А и В. А переменная С примет значение «правда» (или 1), но результату это уже не поможет, т. к. произведение 0 на 1, согласно таблице логического умножения, равно 0. Таким образом, D в данном случае есть «ложь».

Если же принять значение х = — 0,5, то D примет значение «правда». Интересный оборот примут события, если вместо «OR» между А и В подставить «AND» — легко догадаться, что выражение в скобках тогда не выполнится ни при каком значении х, т. к. условия «х меньше 0» и «х больше 1» взаимоисключающие. Потому результирующее условие D всегда будет принимать значение 0, т. е. «ложь». Но вот если мы изменим выражение следующим образом:

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

D = (A¯ + B¯) x C. (7.3)

Это свойство выражается в т. н. правилах де Моргана (учителя Буля):

Отметим, что из таблиц логического умножения и сложения вытекает одно Любопытное следствие. Дело в том, что ассоциация значения «ложь» с нулем, & «правды» — с единицей есть действие вполне произвольное, ничто не мешает нам поступить наоборот. В первом случае логика носит название «положительной», во втором — «отрицательной». Так вот, замена положительной логики на отрицательную приводит к тому, что все операции «ИЛИ» заменяются на «И» и наоборот (рассмотрите таблицы внимательно). А вот операция «НЕ» к такой замене индифферентна, т. к. 0 меняется на 1 в любой логике. В дальнейшем, если это специально не оговорено, мы всегда будем Иметь в виду положительную логику.

Далее приведены несколько соотношений, которые вместе с правилами де Моргана помогают создавать и оптимизировать логические схемы. Некоторые из них очевидны, некоторые же — совсем нет.

А х В х С = (А х В) х С = А х (В х С) (ассоциативный закон умножения);

А + В + С = (А + В) + С = А + (В + С) (ассоциативный закон сложения);

А х А = А; А + А = А;

А + А¯ = 1; А х А¯ = 0;

А x 1 = А; А + 1 = 1;

А x 0 = 0; А + 0 = А;

А + А х В = А;

А х (В + С) = А х В + А х С;

А + В х С = (А + В) х (А + В);

1¯ = 0; 0 = 1¯.

Булева алгебра на выключателях и реле

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

Рис. 7.2. Схемы реализации логических функций на кнопочных выключателях

Здесь операции «И» и «ИЛИ» выполняются обычными кнопками без фиксации. Каждая из них соответствует одной логической переменной, которая принимает значение «1», если контакты замкнуты, и «О» — если разомкнуты. На выходе значению «О» соответствует погасший светодиод, «I» — горящий. Легко понять, что работать эти схемы будут именно так, как указано в правилах для соответствующих логических операций. Для технических устройств, которые, как мы увидим далее, могут выполнять функции, отличающиеся от базового набора булевых операций, правила соответствия входов и выхода называются «таблицами истинности» (или «таблицами состояния») и оформляются в следующем виде:

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

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

Рис. 7.3. Схемы реализации логических функций на реле

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

Легко видеть, что она не адекватна таблице для «ИЛИ», как могло бы показаться на первый взгляд. Аналогично составляется элемент «ИЛИ-HE» — из схемы «ИЛИ», показанной на рис. 7.3 посередине, и инвертора. Таблица истинности для него будет такой:

В большинстве современных серий логических микросхем используются именно элементы «И-НЕ» и «ИЛИ-HE», а не чистые «И» и «ИЛИ» (которые часто даже вовсе отсутствуют в составе некоторых серий, см. главу 8). Для того чтобы было проще разбираться в логических схемах, не заучивая таблицы истинности, работу элементов можно запомнить следующим образом: элемент «И» дает единицу на выходе только если на входах одновременно есть единица («оба одновременно»), элемент «ИЛИ» — если на любом из входов единица («хотя бы один»). Возможно, вам еще проще будет запомнить так: элемент «ИЛИ» дает единицу на выходе, если на входах «хотя бы одна единица», а элемент «И» дает ноль на выходе, если на входах «хотя бы один ноль». Рассмотренные же элементы с инверсией по выходу будут давать в тех же случаях обратные значения.

Заметки на полях

Интересно рассмотреть вопрос — а нельзя ли упростить схемы этих комбинированных элементов, исключив из них третье реле, выполняющее инверсию? В самом деле, большинство реле имеют перекидные контакты, так за чем же дело стало — меняем нормальноразомкнутые контакты на нормальнозамкнутые, и все! Легко заметить, что такая замена не будет адекватной, поскольку мы инвертируем здесь не общий выход элемента, а выходы каждого реле в отдельности, что равносильно инвертированию входов. Если обратиться к правилам де Моргана, то мы увидим, что такое изменение схемы приведет к тому, что элемент «И» превратится в «ИЛИ-НЕ», а «ИЛИ» — соответственно, в «И-НЕ». Иначе можно сказать так: мы получили желанный результат, но в отрицательной логике. Я советую читателю посидеть над этими соображениями и вывести таблицы истинности самостоятельно, чтобы убедиться, что все сказанное — правда. Второе полезное упражнение состоит в том, чтобы попытаться самому построить трехвходовые элементы, соответствующие уравнениям А + В + С и А х В х С (они будет состоять из трех реле).

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

Как мы считаем

О том, что мы считаем в десятичной системе потому, что у нас десять пальцев на двух руках, осведомлены, вероятно, все. Персонажи из мультфильмов студии «Пилот ТВ» — Хрюн Моржов и Степан Капуста — считают, наверное, в восьмеричной системе, так как у них пальцев по четыре. У древних ацтеков и майя в ходу была двадцатеричная система (вероятно потому, что закрытая обувь в их климате была не в моде). Вместе с тем, история показывает, что привязка к анатомическим особенностям строения человеческого тела совершенно необязательна. Со времен древних вавилонян у нас в быту сохранились остатки двенадцатеричной и шестидесятеричной систем, что выражается в количестве часов в сутках и минут в часах, или, скажем, в том, что столовые приборы традиционно считают дюжинами или полудюжинами (а не десятками и пятерками). Так что само по себе основание системы счисления не имеет значения, точнее, это дело привычки и удобства.

Число — одна из самых удивительных абстрактных сущностей. Нет никаких сомнений, что число, количество предметов — есть вполне объективно существующая характеристика, и в отличие от, к примеру, зрительных образов, она совершенно независима от самого факта наличия разума у считающего субъекта и даже от наличия самого субъекта — если бы (и когда) цивилизации вообще не существовало, количество планет в Солнечной системе осталось бы тем же. И тем не менее материального воплощения числа не имеют — количество, представленное в виде комбинации пальцев рук и ног, зарубок на палочке (вспомните, как Робинзон Крузо вел свой календарь), разложенных на земле веточек, костяшек на счетах или — что для нас самое главное! — черточек или значков на бумаге, есть всего лишь физическая модель некоего идеального абстрактного понятия «числа». Умение считать в уме, которое отличает цивилизованного человека от дикаря, и состоит в том, что мы можем оторваться от такой материальной модели и оперировать непосредственно с абстракцией.

Заметки на полях

Раз уж мы опять ударились в философию, то не могу удержаться, чтобы не продолжить в том же духе: раз числа существуют объективно, то где они существуют? Этот вопрос совсем не так прост, потому что число есть лишь один из подобных объектов, несомненно присутствующих в природе, и тем не менее не имеющих материального воплощения — это и геометрические фигуры, и другие математические объекты, в том числе и булева алгебра вместе с ее операндами. Причем, если физические идеализации («абсолютно твердое» или «абсолютно упругое» тело) есть сущности, действительно выдуманные человеком с целью упрощения изучения свойств реальных тел, и вне человеческого знания не существуют, то с математическими абстракциями вовсе не так: естественный спутник Земли всегда был один, даже когда самого человечества еще не существовало. Это послужило основанием для того, чтобы великий греческий философ Платон, из учений которого в той или иной степени проистекает вся современная западная философия, предположил существование некоего идеального мира («платоновского мира идей»), где все эти абстракции и «живут». Любопытно, что на этом основании Платона справедливо зачисляют в идеалисты, однако вышесказанное — хороший пример тому, что часто отождествляемые понятия «идеалистического» и «божественного» вовсе не одно и то же.

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

Из понятия числа, как объективно существующей абстракции, вытекает, что его материальное представление может быть произвольным, лишь бы оно подчинялось тем же правилам, что и сами числа. Проще всего считать палочками (и в детском саду нас учат именно такому счету), в качестве которых могут выступать и пластмассовые стерженьки, и пальцы, и черточки на бумаге. Один — одна палочка, два — две палочки, десять — десять палочек. А сто палочек? Уже посчитать затруднительно, поэтому придумали сокращение записи: доходим до пяти палочек, ставим галочку, доходим до десяти — ставим крестик:

1 2 5 7 10 11

I II V VII X XI

Узнаете? Конечно, это всем знакомая римская система, сохранившаяся до настоящих времен на циферблатах часов или в нумерации столетий. Она представляет собой пример непозиционной системы счисления, потому что значение определенного символа, обозначающего то или иное число, в ней не зависит от позиции относительно других символов — все значения в записи просто суммируются. Следовательно, записи «XVIII» и «IIIХV» в принципе Должны означать одно и то же. На самом деле это не совсем так: в современной традиции принято в целях сокращения записи учитывать и позицию символа: скажем, в записи «IV» факт, что палочка стоит перед галочкой, а не после нее, означает придание ей отрицательного значения, т. е. в данном случае единица не прибавляется, а вычитается из пяти (то же самое относится и к записи девятки «IX»). Если вы человек наблюдательный, то могли заметить, что на часах четверку пишут почти всегда, как «IIII, а не как «IV», что, несомненно, более отвечает духу непозиционной системы. Однако, при всех возможных отклонениях главным здесь остается факт, что в основе системы лежит операция суммирования.

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

Рис. 7.4. Вавилонские глиняные таблички с записью чисел. Вверху перевод некоторых из них в десятичную систему

Заметки на полях

В Европе позиционную систему переоткрыл (видимо) Архимед, затем от греков она была воспринята индусами и арабами, и на рубеже I и II тысячелетий н. э. опять попала в Европу[6] — с тех пор мы называем цифры арабскими, хотя по справедливости их следовало бы назвать индийскими. Это была уже современная десятичная система в том виде, в котором мы ее используем по сей день, у арабов отличается только написание цифр. С тем фактом, что заимствована она именно у арабов, связано не всеми осознаваемое несоответствие порядка записи цифр в числе и привычным нам порядком следования текста: арабы, как известно, пишут справа налево. Поэтому значение цифры в зависимости от позиции ее в записи числа возрастает именно справа налево, что в европейском языке нелогично — приходится заранее обозревать число целиком и готовить ему место в тексте.

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

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

а_nрⁿ + а_n-1р^n-1 + … + a₁р¹ + a₀p⁰. (7.4)

В самой записи числа степени основания подразумеваются, а не пишутся (и для записи основания даже нет специального значка), т. е. запись будет представлять собой просто последовательность а_n … а₀ (обратим внимание на то, что запись производится справа налево по старшинству — обычная математическая запись выглядела бы наоборот). Отдельные позиции в записи числа называются разрядами.

Заметки на полях

Еще один нюанс, дошедший до нас из древнегреческих времен, связан с тем, что греки и римляне не знали нуля. Именно поэтому первым годом нового века и тысячелетия считается 2001, а не 2000 год — год с двумя нулями относится к предыдущему столетию или тысячелетию — после последнего года до нашей эры (минус первого) идет сразу первый год нашей эры, а не нулевой. Однако именно нулевой логично считать первым, вдумайтесь: ведь когда мы говорим «первые годы XX века», мы имеем в виду именно 1903 или 1905, а не 1913 или 1915. Но древние греки были совсем не такие дураки и ноль игнорировали не по скудоумию. Дело в том, что в последовательности объектов, нумерованных от нуля до, например, девяти, содержится не девять предметов, а десять! Чтобы избежать этой путаницы, в быту обычно нумеруют, начиная с единицы, тогда последний номер будет одновременно означать и количество. В электронике же и в программировании обычно принято нумеровать объекты, начиная с нуля, и всегда следует помнить, что номер и количество различаются на единицу (так, в байте 256 возможных символов, но номер последнего равен 255). На всякий случай всегда следует уточнять, откуда ведется нумерация, иначе можно попасть в неприятную ситуацию (скажем, элементы строки в языке Pascal нумеруются с единицы, а в языке С — с нуля).

Десятичная и другие системы счисления

В десятичной системе (т. е. в системе с основанием р = 10) полное представление четырехразрядного числа, например, 1024 таково: 1∙10³ + 0∙10² + 2∙10¹ + 4∙10⁰.

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

Ну, а как можно представить число в системе счисления с другим основанием? Для любой системы с основанием р нужно не меньше (и не больше) чем р различных цифр — то есть значков для изображения чисел. Для десятичной системы их десять — это и есть известные всем символы от 0 до 9. Выбор начертания этих значков совершенно произволен — так, у арабов и по сей день 1 обозначается, как и у нас, палочкой. А вот цифра 2 обозначается знаком, похожим на латинскую строчную «г», причем тройка тоже имеет похожее начертание, и я плохо себе представляю, как Усама бен Ладен их там отличает. Впрочем, это дело привычки, у нас тоже значки «5» и «6» в некоторых случаях различить непросто, не говоря уж о сходстве между нулем «0» и буквой «О». В ручном написании текстов программ, а также в матричных компьютерных шрифтах, которые были в ходу до появления графического интерфейса, для этого ноль даже изображали перечеркнутым, наподобие знака диаметра: «

Чтобы древним вавилонянам, несчастным, не приходилось выучивать аж 60 разных начертаний знаков, они придумали логичную систему наподобие римской (еще раз обратите внимание на рис. 7.4) — действующую, впрочем, только в пределах первых шестидесяти чисел, а далее у них система становилась аналогичной современным.

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

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

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

Что очень важно на практике, двоичная система прекрасно стыкуется как с представленными в предыдущем разделе логическими переменными «правда» и «ложь», так и с тем фактом, что величина, могущая принимать два и только два состояния, и получившая названия бит, есть естественная единица количества информации — меньше, чем один бит, информации не бывает. Это было установлено в 1948 году одновременно упоминавшимся Клодом Шенноном и Нобертом Винером, «отцом» кибернетики. Разряды двоичных чисел (то есть чисел, представленных в двоичной системе) также стали называть битами. (Bit, bite — по-английски «кусочек, частица чего либо». На самом деле это случайное совпадение: слово «бит» возникло от сокращения Binary digiT — «двоичная цифра».)

Заметки на полях

С троичным компьютером, который был на практике построен Н. Брусенцовым в МГУ на рубеже 60-х годов прошлого века (под названием «Сетунь»), связана отдельная история. При разработке первых компьютеров перед конструкторами встал вопрос об экономичности систем счисления с различными основаниями. Под экономичностью системы понимается тот запас чисел, который можно записать с помощью данного количества знаков. Чтобы записать 1000 чисел (от 0 до 999) в десятичной системе, нужно 30 знаков (по десять в каждом разряде), а в двоичной системе с помощью 30 знаков можно записать 2¹⁵=32768 чисел, что гораздо больше 1000. Поэтому двоичная система явно экономичнее десятичной. В общем случае, если взять n знаков в системе с основанием р, то количество чисел, которые при этом можно записать, будет равно р^n/p. Легко найти максимум такой функции, который будет равен иррациональному числу е = 2,718282…. Но поскольку система с основанием е может существовать только в воображении математиков, то самой экономичной считается система счисления с основанием 3, ближайшим к числу е. В компьютере, работающем по такой системе, число элементов, необходимых для представления числа определенной разрядности, минимально. Реализацию троичной системы в электронике можно представить себе, как схему с такими, например, состояниями: напряжение отсутствует (0), напряжение положительно (1), напряжение отрицательно (-1). Д. Кнут в своем труде [10] показывает, что троичная арифметика проще двоичной.

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

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

Итак, запись числа в двоичной системе требует всего две цифры, начертание которых заимствовано из десятичной системы, и выглядит, как 0 и 1. Число, например, 1101 тогда будет выглядеть так:

1∙2³ + 1∙2² + 0∙2¹ + 1∙2⁰ = 13.

Чтобы отличить запись числа в различных системах, часто внизу пишут основание системы:

1101₂= 1310.

Если система не указана, то имеется в виду обычно десятичная, но не всегда. Часто, когда из контекста понятно, что идет речь об электронных устройствах, не указывают не только основание «два», но и под словом «разрядность» имеют в виду количество именно двоичных, а не десятичных разрядов (таков, скажем, смысл термина «24-разрядный цвет»).

Шестнадцатеричная система

Шестнадцатеричная система имеет, как ясно из ее названия, основание шестнадцать. Для того чтобы получить шестнадцать различных значков, изобретать ничего нового не стали, а просто использовали те же цифры от 0 до 9 для первых десяти знаков, и заглавные латинские буквы от А до F — для знаков с одиннадцатого по шестнадцатый. Таким образом, известное нам число 13₁₀ выразится в шестнадцатеричной системе, как просто D₁₆. Соответствие шестнадцатеричных знаков десятичным числам следует выучить наизусть: А — 10, В — 11, С — 12, D — 13, Е — 14, F — 15. Значения больших чисел вычисляются по обычной формуле, например:

A2FC₁₆= 10∙16³ + 2∙16² + 15∙16¹ + 12∙16⁰ = 40960+ 512 + 240 + 12 = 41724₁₀.

Перевод из одной системы счисления в другую

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

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

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

2¹ = 2₁₀ =10₂;

2² = 4₁₀ = 100₂;

2³ = 8₁₀ = 1000₂ и т. д.

Способ состоит в следующем: пусть мы имеем, например, десятичное число 59. Подбираем наибольшую степень двойки из таблицы ранее, не превышающую этого числа: 32, что есть 5-я степень. Ставим 1 в шестом разряде: 100000. Вычитаем подобранную степень из исходного числа (59–32 = 27) и подбираем для остатка также степень, его не превышающую: 16 (2⁴). Ставим единицу в 5-м разряде: 110000. Повторяем процедуру вычитания-подбора: 27–16 = 11, степень равна 8 (2³), ставим единицу в 4-м разряде: 111000. Еще раз: 11 — 8 = 3, степень равна 2 (2¹), ставим единицу во 2-м разряде: 111010. Последнее вычитание дает 1, которую и ставим в младший разряд, окончательно получив 59₁₀ = 111011₂. Если бы исходное число было четным, к примеру 58, то в последнем вычитании мы бы получили 0, и число в двоичной системе также оканчивалось бы на ноль: 58₁₀ = 111010₂.

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

2¹ — 1 = 1₁₀ = 1₂;

2² — 1 = 3₁₀ = 11₂;

2³ — 1 = 7₁₀ = 111₂;

Подобно тому, как наибольшее трехразрядное число в десятичной системе равно 999, и чисел таких всего 10³ = 1000 (от 000 до 999), в двоичной системе тех же трехразрядных чисел будет 2³ = 8 штук, в диапазоне от 000 до 111, т. е. от 0 до 7. Таким образом, наибольшее двоичное число с данным количеством разрядов будет всегда содержать все единицы во всех разрядах.

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

Например, число 59₁₀, т. е. 0011 1011₂, будет равно 3Bh.

Точно так же осуществляется и обратный перевод — каждое шестнадцатеричное число просто записывается в виде совокупности тетрад. Так, число A2FC₁₆ выразится, как 1010 0010 1111 1100₂. Заметьте, что пробелы между тетрадами введены просто для удобства восприятия, подобно пробелам между тройками разрядов (классами) в записи больших десятичных чисел, и никакой иной нагрузки не несут. При записи двоичных чисел в тексте программ, как ассемблерных, так и программ на языках высокого уровня, естественно, эти пробелы ставить запрещается.

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

Байты

Слово байт (byte) создано искусственно и представляет собой сокращение от BinarY digiT Eight, что буквально переводится, как «двоичная цифра восемь». На самом деле байт — это просто восьмиразрядное двоичное число. Соответственно, он имеет ровно два шестнадцатеричных разряда, или две двоичных тетрады. Такой байт был введен фирмой IBM в конце 50-х годов прошлого века, до этого (а в СССР — вплоть до 1969 года) применялись байты с другим количеством разрядов (5, 6 и 7).

Почему именно 8 разрядов? Да просто потому, что так удобно: число кратно степени двойки, т. е. легко масштабируется, скажем, шестнадцатиразрядное число — просто два байта, записанные подряд, подобно тетрадам в самом байте. В то же время оно относительно невелико и одновременно достаточно емко: имеет 256 значений, которых с лихвой хватает, к примеру, для представления всех печатных знаков европейских алфавитов (во всяком случае, до нашествия фирмы Microsoft с ее системой Windows хватало — что, конечно же, следует рассматривать, как шутку).

Поэтому в настоящее время байт — общепринятая единица измерения информации, т. к. основную единицу — бит — на практике применять неудобно из-за ее «мелковатости», числа получаются слишком большими. Применяют и меньшие единицы (кроме бита, это полубайт, или просто одно шестнадцатеричное число), и большие — двухбайтовые (65 536 значений), четырехбайтовые (32 двоичных разряда или 4 294 967 296 значений) и даже восьмибайтовые числа. Все они часто называются словами — «word».

Однако на практике распространение получила запись больших количеств информации по системе, «слизанной» с десятичной: это килобайт (1024 или 2¹⁰ байта), мегабайт (1024 или 2¹⁰ килобайта) и гигабайт (1024 или 2¹⁰ мегабайта). Близостью значения 1024 к десятичной тысяче широко пользуются производители жестких дисков — так, емкость диска в 10 Гбайт может быть вовсе не 1024x1024 килобайта, как положено, а 1000x1000, что почти на пять процентов меньше. Пустячок — а ведь приятно обмануть покупателя, который потом будет с недоумением раздумывать, почему ему в настройках компьютера показывается вовсе не 10, а 9,54 Гбайта, и куда исчезли «родные» 460 Мбайт? Однако имейте в виду, что подобные фокусы все же выкидываются только в отношении наивных покупателей, а в серьезной технической документации кило- и мегабайты обычно означают то, что положено.

Подробности

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

На практике можно встретить обозначение единиц информации из одной буквы (напр. «256 К памяти»), но злоупотреблять таким способом не следует, т. к. часто приходится гадать, идет ли тут речь о битах, байтах, словах или вообще бодах (см. далее). Мы вслед за фирменным описанием Atmel будем пользоваться такой нотацией (К или М без указания единиц), но исключительно для обозначения абсолютных чисел (например, «диапазон 4 М», что значит 4 х 1024 х 1024 = 4194304), обозначающих обычно адреса в памяти программ, разбитые по двухбайтовым словам.

Впрочем, есть одна область, где традиционно употребляются именно биты (а также мегабиты и гигабиты), а не байты — это характеристики последовательных цифровых линий передач, к примеру, всем знакомая характеристика модемов в 56 К означает именно 56 кбит в секунду. Биты в секунду иногда называют бодами (по имени изобретателя телетайпного аппарата Эмиля Бодэ), но это не совсем точно. Употребление именно битов в сетях передачи данных связано с тем, что передача восьмиразрядными пакетами там применяется редко — скажем, стандарт RS-232, который мы будем еще разбирать, содержит восемь значащих разрядов (т. е. один байт), но помимо этого передается как минимум еще два бита (столовый и стартовый) — итого 10. В Интернете пакеты и вовсе могут иметь переменную длину, а модемы за одну посылку (как говорят связисты, за одну модуляцию) могут посылать от одного до 16 битов (вот число таких посылок в секунду и измеряется в бодах). Поэтому байтами в сетях информацию считают только, когда речь идет об отправленной или принятой информации, но не о той, которая реально передается.

Запись чисел в различных форматах

Шестнадцатеричный формат записи часто еще обозначают как HEX (hexadecimal), двоичный — как BIN (binary), а десятичный — как DEC (decimal). Кроме этого, в ходу еще т. н. двоично-десятичный формат BCD (binary-coded decimal), о котором далее. Так как с помощью матричных шрифтов на компьютерах с текстовыми дисплеями воспроизводить индексы было невозможно, то вместо того, чтобы обозначать основания системы цифрой справа внизу, их стали обозначать буквами: «В» (или «Ь») означает двоичную систему, «Н» (или «h») — шестнадцатеричную, «D» (или «d») — десятичную. Отсутствие буквы также означает десятичную систему:

13 = 13d = 00001101b = 0Dh.

Такая запись принята, например, в языке ассемблера для процессоров Intel. Популярность языка С внесла в это дело некоторый разнобой: там десятичная система обозначается буквой «d» (или никак), двоичная буквой «Ь», а вот шестнадцатеричная буквой «х», причем запись во всех случаях предваряется нулем (чтобы не путать запись числа с идентификаторами переменных, которые всегда начинаются с буквы):

13 = 0d13 = 0Ь00001101 = 0x0D.

Такая же запись также принята в ассемблере для микроконтроллеров AVR, которыми мы будем пользоваться. Запись типа 0Dh ассемблер AVR не поддерживает, зато «понимает» представление НЕХ-формата, принятое в языке Pascal: $0D. В фирменном описании системы команд AVR можно даже встретить запись сразу с двумя обозначениями, по типу $0Dh (очевидно, специально для особо бестолковых).

Обратите внимание, что запись в НЕХ-формате обычно ведется в двухразрядном виде, даже если число имеет всего один значащий разряд, как в нашем случае, то в старшем пишется 0, то же самое относится и к двоичной записи, которая дополняется нулями до восьми разрядов. А вот для десятичного представления такой записи следует остерегаться.

Замечание

Чтобы еще больше «запутать» пользователя, разработчики AVR-ассемблера приняли для представления редко употребляемых восьмеричных чисел запись просто с ведущим нулем, без букв: например, 77 означает просто десятичное 77, а вот 077 будет означать 7∙8 + 7 = 63₁₀. Нет, чтобы уж сделать и здесь, как в языке С, где восьмеричные числа записываются по аналогии со всеми остальными, как 0оХХ.

Добавление незначащих нулей связано с тем обстоятельством, что запись и чтение чисел обычно ведется побайтно, а в байте именно два шестнадцатеричных разряда или восемь двоичных. Если число имеет разрядность больше байта, т. е. представляет собой слово, то для обозначения этого факта слева дописываются еще нули, так, шестнадцатиразрядное двоичное число 13 правильно записать, как 0000 0000 0000 1101b, а в НЕХ-формате оно будет иметь 4 разряда, т. е. запишется, как 000Dh. Поглядев на эти две записи, вы можете понять, для чего пользуются шестнадцатеричной системой — запись получается намного компактней.

Формат BCD

Электронные устройства «заточены» под двоичную и родственные им системы счисления, потому что основой являются два состояния — двоичная цифра. Так что соединив несколько устройств вместе с целью оперирования с многоразрядными числами, мы всегда будем получать именно двоичное число. При этом четыре двоичных разряда могут представлять шестнадцать различных состояний, и задействовать их для представления десятичных чисел было бы попросту неэкономично: часть возможного диапазона осталась бы неиспользованной. Подсчитайте сами: для представления числа с шестью десятичными разрядами в десятичном виде нужно 6 х 4 = 24 двоичных разряда, а для представления того же числа в двоичном виде с избытком хватит 20 разрядов (2²⁰ = 1 048 576). А меньше, чем четыре двоичных разряда, для представления одного десятичного числа не хватит (2³ = 8). К тому же с чисто двоичными числами, как мы увидим в дальнейшем, оперировать значительно проще.

И все же применять двоично-десятичный формат приходится всегда, когда речь идет о выводе чисел, например, на цифровой дисплей — двоичные или шестнадцатеричные числа человеку воспринимать, естественно, тяжело: представьте, что мы показываем температуру в виде 1E,D градуса по Цельсию! Многие ли сразу подсчитают, что это означает (примерно) 30,81 градуса?

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

Неупакованный формат попросту означает, что мы тратим на каждую десятичную цифру не тетраду, как необходимо, а целый байт. Зато при этом не возникает разночтений: 05h = 05₁₀ и никаких проблем.

Однако ясно, что это крайне неэкономично — байтов требуется в два раза больше, а старший полубайт при этом все равно всегда ноль. Потому BCD-числа при хранении в регистрах всегда упаковывают, занимая и старший разряд второй десятичной цифрой: скажем, число 59 при этом и запишется, как просто 59. Однако это не 59h! 59 в шестнадцатеричной форме есть 3Bh, как мы установили ранее, а наше 59 процессор прочтет, как 5∙16 + 9 = 89, что вообще ни в какие ворота не лезет! Поэтому перед проведением операций с упакованными BCD-числами их распаковывают, перемещая старший разряд в отдельный байт и заменяя в обоих байтах старшие полубайты нулями. Иногда для проведения операций с BCD в микропроцессоре или микроконтроллере предусмотрены специальные команды, так что самостоятельно заниматься упаковкой-распаковкой не требуется (такие инструкции есть, например, в системе команд знаменитого 8086, на котором был построен IBM PC). В качестве примера хранения чисел в BCD-формате можно привести значения часов, минут и секунд в энергонезависимых часах компьютера.

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

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

0 + 0 = 0    0∙0 = 0

0 + 1 = 1    0∙1 = 0

1 + 0 = 1    1∙0 = 0

1 + 1 = 10   1∙1 = 1

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

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

Отрицательные числа

Самый простой метод представления отрицательных чисел — отвести один бит (логичнее всего старший) для хранения знака. По причинам, которые вы поймете далее, значение «1» в этом бите означает знак «минус», а «0» — знак «плюс». Как будут выглядеть двоичные числа в таком представлении?

В области положительных чисел ничего не изменится, кроме того, что их диапазон сократится вдвое: например, для числа в байтовом представлении вместо диапазона 0—255 мы получим всего лишь 0—127 (0000 0000–0111 1111). А отрицательные числа будут иметь тот же диапазон, только старший бит у них будет равен единице. Все просто, не правда ли?

Нет, неправда. Такое представление отрицательных чисел совершенно не соответствует обычной числовой оси, на которой влево от нуля идет минус единица, а затем числа по абсолютной величине увеличиваются. Здесь же мы получаем, во-первых, два разных нуля («обычный» 0000 0000, и «отрицательный» 1000 0000), во-вторых, оси отрицательных и положительных чисел никак не стыкуются, и выполнение арифметических операций превратится в головоломку. Поэтому поступим так: договоримся, что -1 соответствует число 255 (1111 1111), — 2 — число 254 (1111 1110) и т. д., вниз до 128 (1000 0000), которое будет соответствовать -128 (и общий диапазон всех чисел получится от -128 до 127). Очевидно, что если вы в таком представлении хотите получить отрицательное число в обычном виде, то надо из значения числа (например, 240) вычесть максимальное значение диапазона (255) плюс 1 (256). Если отбросить знак, то результат такого вычитания (16 в данном случае) называется еще дополнением до 2 (или просто дополнительным кодом) для исходного числа (а само исходное число 240 тогда будет дополнением до 2 для 16). Название «дополнение до 2» используется независимо от разрядности числа, потому что верхней границей всегда служит степень двойки (в десятичной системе аналогичная операция называется «дополнение до 10»).

Вычитание

Что произойдет в такой системе, если вычесть, например 2 из 1? Запишем это действие в двоичной системе обычным столбиком:

00000001

— 00000010

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

(1) 00000001

— 00000010

-

11111111

На самом деле девятиразрядное число 1 0000 0000 есть не что иное, как 256, т. е. то же самое максимальное значение +1, и мы здесь выполнили две операции: прибавили к вычитаемому эти самые 256, а затем выполнили вычитание, но уже в положительной области для всех участвующих чисел. А что результат? Он будет равен 255, т. е. тому самому числу, которое, как мы договорились, представляет собой -1. Таким образом, вычитание в такой системе происходит автоматически правильно, независимо от знака участвующих чисел.

Немного смущает только эта самая операция нахождения дополнения до 2, точнее, в данном случае до 256 — как ее осуществить на практике, если схема всего имеет 8 разрядов? В дальнейшем мы увидим, что на практике это не нужно: при вычитании и в микроконтроллерах, и в обычных электронных счетчиках все осуществляется автоматически.

Впрочем, в микропроцессорах есть обычно и отдельная команда, которая возвращает дополнение до 2. В большинстве ассемблеров она называется neg, от слова «негативный», потому что просто-напросто меняет знак исходного числа, если мы договариваемся считать числа «со знаком». Разберем из любопытства, как ее можно было бы осуществить «вручную», не обращаясь в действительности к 9-му разряду. Для этого выпишем столбиком какое-нибудь число (далее для примера — 2 и 240), результаты операции нахождения его дополнения до 2, и результат еще одной манипуляции, которая представляет собой вычитание единицы из дополнения до 2, или, что то же самое, просто вычитания исходного числа из наивысшего числа диапазона (255):

Если мы сравним двоичные представления в верхней и нижней строках в каждом случае, то увидим, что они могут быть получены друг из друга путем инверсии каждого из битов. Эта операция называется нахождением обратного кода или дополнения до единицы (потому что число, из которого вычитается, содержит все 1 во всех разрядах; для десятичной системы аналогичная операция называется «дополнение до 9»). Для нахождения дополнения до 1 девятый разряд не требуется, да и схему можно построить так, чтобы никаких вычитаний не производить, а просто «переворачивать» биты. Так и делается, конечно, но не ищите в микроконтроллерах специальной операции инверсии битов — для этого вызывается именно команда нахождения дополнения до 1 (в AVR-ассемблере она обозначается, как сом, и определяется, как операция вычитания из FFh, а что уж там происходит на самом деле — тайна, покрытая мраком). Итак, для полного сведения вычитания к сложению надо проделать три операции:

1. Найти дополнение до 1 для вычитаемого (инвертировать его биты).

2. Прибавить к результату 1, чтобы найти дополнение до 2.

3. Сложить уменьшаемое и дополнение до 2 для вычитаемого.

Заметки на полях

Заметим, что все сложности с этими многочисленными дополнениями связаны с наличием нуля в ряду натуральных чисел — если бы его не было, дополнение было бы всего одно, и операция вычитания упростилась. Так может греки все же были в чем-то правы?

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