Теперь мы знаем, рассматривали в предыдущей статье, почему в ЭВМ применяется именно двоичная система счисления и какое отношение к этому имеет средневековый математик Фибоначчи. Мы даже кратко рассмотрели представление целых чисел в двоичной и троичной симметричной системах счисления. Казалось бы, пора переходить к более сложным форматам чисел, как это делается во всех учебниках...
Однако, статья не является учебником, а моя цель это именно описание "почему именно так", что по большей части пропускается в учениках. А значит, мы сегодня продолжим небольшой экскурс в системы счисления и внимательнее присмотримся к целым числам. Более того, хоть это изначально и не планировалось, мы снова поговорим о троичной системе счисления, но уже без затрагивания специфики машины Сетунь.
Двоичная VS троичная симметричная
Обсуждения предыдущей статьи
свидетельствуют, что нужно рассмотреть этот вопрос подробнее.
На самом деле, хоть мы будем говорить только о двоичной и троичной несимметричной системах счисления, все будет верным в отношении любых симметричных и несимметричных систем счисления. И главу можно было назвать "Симметричные VS несимметричные".
Я кратко напомню, что такое симметричные и несимметричные системы счисления. В несимметричных системах счисления, наиболее нам привычных, используются цифры (весовые коэффициенты) не имеющие знака. Часто их называют положительными, хоть это не совсем верно. Для несимметричной N-ричной системы счисления используются цифры от 0 до N-1. При этом общее количество цифр равно N.
Так для десятичной системы счисления, которой мы пользуемся в обычной жизни, используются цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. В шестнадцатиричной системе используются цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A (10), B (11), C (12), D (13), E (14), F (15).
Симметричная система счисления тоже использует N цифр, но сами цифры (весовые коэффициенты!) уже имеют знак. И они располагаются симметрично относительно нуля. Подавляющему большинству обычных людей симметричные системы счисления вряд ли встретятся.
Для троичной симметричной системы счисления, которая использовалась в ЭВМ Сетунь, используются цифры -1, 0, +1. Вы это помните из предыдущей статьи. Пятиричная симметричная система счисления будет использовать цифры -2, -1, 0, +1, +2.
Несимметричные системы счисления приводят к появлению своеобразного артефакта, который принимается как данность, но является именно артефактом. Все числа делятся на две большие группы. Первая - числа не имеющие знака (беззнаковые). Вторая - числа имеющие знак. Зачастую считается, что беззнаковые числа являются положительными, но это не совсем так. Все зависит от нашей интерпретации таких чисел. Отсутствие знака у числа вовсе не означает, что отсутствующий знак именно +.
Что бы иметь возможность записывать и положительные, и отрицательные, числа в несимметричной система счисления мы добавляем к числу знак как дополнительный элемент. Знак числа является дополнительным признаком, атрибутом. Несмотря на то, что знак + чаще всего опускается, он все равно незримо присутствует.
Поскольку знак для чисел со знаком есть у любого числа, включая ноль, мы и получаем два нуля - положительный и отрицательный. Для двоичной системы счисления нашли выход их положения использовав для представления отрицательных чисел дополнительный код. Но об этом чуть позже
Я показал отрезки числовых прямых и числа на них в разных системах счисления. В десятичной системе счисления знак просто занимает дополнительное место в строке. В двоичной системе счисления все точно так же, просто знак, в процессоре ЭВМ, представлен содержимым старшего бита числа. Если этот бит равен 0, то число положительное. Если равен 1, то число отрицательное. Мы это уже видели в предыдущей статье.
Место в строке и дополнительный бит это дополнительные затраты на знак числа. Для представления показанных на иллюстрации чисел достаточно три бита, но знак числа требует использования целой тетрады.
Числа в симметричной системе счисления имеют знак как неотъемлемый атрибут числа. В таких системах счисления чисел без знака просто не существует
Не обращайте внимания, что теперь нам требуется всего два трита на число. Основание системы счисления выше, поэтому и разрядов нужно меньше. Но обратите внимание, что нам теперь не требуется выделять знак числа как дополнительный разряд (атрибут). И у нас остается всего один ноль.
Поэтому можно сказать, что симметричные системы счисления позволяют представлять математическое понятие "число" более естественным образом. Правда эта естественность больше для машины, а не для человека.
Может показаться, что для троичной симметричной системы счисления затраты будут больше. Многие читатели в доказательство могут сослаться на машину Сетунь, где использовалось два ферритовых сердечника для каждого трита. Но современная схемотехника легко позволяет обойти это усложнение. Достаточно представлять +1 и -1 разной полярностью напряжения.
Суета вокруг ноля
Но почему столько внимания уделяется простому нолю? Чем вообще мешает наличие двух нулей, положительного и отрицательного? В конечном итоге, человек вполне успешно пользуется десятичной системой счисления и не чувствует никаких проблем с отдельно стоящим знаком числа.
Все верно, но дело в том, что человек просто автоматически учитывает все нюансы, все таки он человек разумный. А машина выполняет операции, которые очень желательно иметь одинаковыми для всех чисел. Иначе схемотехника процессоров получается излишне сложной. И простым добавлением знака, пусть и в виде дополнительного бита, проблема не решается.
Давайте посмотрим на простой пример операции сложения двух чисел имеющих разные знаки. Да, это аналогично операции вычитания, но ведь никто не запрещает использовать именно сложение. Машинная операция работает с переменными, с ячейками памяти. А в ячейке может храниться любое значение
Результат совсем не такой, как мы ожидали! В чем проблема? В том, что знаковые биты, показанные на иллюстрации цветом, тоже участвуют в операции сложения. Значит, при представлении чисел со знаком в прямом коде (для двоичных чисел в ЭВМ), должны быть отдельные арифметические команды для чисел со знаком и чисел без знака. Причем команды для чисел знаком должны дополнительно анализировать сами числа, что бы при необходимости откорректировать знак результата или даже изменить выполняемую операцию.
Нельзя просто обрабатывать знак отдельно. Если для примера на иллюстрации отбросить знаковый бит, результат все равно будет неверным. Потому что процессор должен, предварительно проанализировав содержимое ячеек, заменить операцию сложения на операцию вычитания. А это существенно усложняет реализацию процессора и, косвенно, снижает быстродействие.
Мы можем снизить степень усложнения процессора перейдя к разным способам представления положительных и отрицательных чисел. Давайте попробуем для отрицательных чисел использовать инверсию. При этом знаковый бит сохраняется. Тогда мы получим такое
Обратите внимание, что мы получили почти верный результат. Причем мы использовали обычную операцию сложения для чисел без знака и никак не учитывали наличие знакового бита. Что это за перенос такой мы подробнее рассмотрим чуть позже, в нем нет ничего сложного.
Итак, мы использовали простую инверсию, причем включая и знаковый бит. Смена знака числа свелась в простой инверсии всех бит. Это позволило нам использовать обычную операцию сложения не учитывающую знак чисел. Но результат все таки требует небольшой коррекции. А значит, арифметические команды для работы с числами со знаком и без знака все таки должны быть разными.
И проблема нуля никуда не делась, он по прежнему является артефактом. Мы не можем сменить знак числа с помощью инверсии, если это число 0. Решением проблемы является усложнение представления отрицательных чисел. Помните, в предыдущей статье я говорил о том, что отрицательные числа хранятся в дополнительном коде? Теперь мы понимаем, почему это потребовалось. И проблема оказалась не только в представлении 0.
Вспомним, что в дополнительном коде отрицательные числа хранятся как числа, которые нужно прибавить к исходному для получения 0. Дополнительный код получается очень просто, инверсией всех бит с последующим инкрементом (прибавлением 1). То есть, смена знака числа это инверсия плюс инкремент. И смотрите, что у нас получается
Мы получили верный результат с помощью универсальной операции сложения! То есть, мы усложнили представление отрицательных чисел, но это не потребовало увеличения места под их хранение. Изменилась только наша интерпретация битового содержимого ячейки памяти. Мы усложнили операцию смены знака числа. Но мы получили существенное упрощение всего процессора в целом. При этом упростилась и работа программиста (или компилятора), так как теперь арифметические команды стали универсальными.
Но все это потребовалось лишь по той причине, что была использована несимметричная система счисления. Поэтому я и назвал эту главу "суета вокруг ноля". Для симметричной системы счисления такое усложнение не требуется. И это было одной из причин попытки использования троичной системы счисления в ЭВМ Сетунь. Для число вычислительных задач симметричная система счисления действительно удобнее.
Переносы и переполнения
Теперь мы можем перейти к рассмотрению не только интерпретации отдельных бит числа, что мы делали ранее, но и посмотреть на взаимозависимость отдельных бит внутри числа. Для этого мы снова начнем с десятичной системы счисления и операции сложения
Как вы помните, для позиционных систем счисления мы можем выполнять арифметические операции отдельно над каждым разрядом (каждой цифрой) числа. Именно так мы выполняем сложение в столбик. Но возникает проблема, когда сумма двух цифр числа не помещается в одной цифре результата. Именно так у нас произошло при сложении 1 и 9.
Непомещающаяся часть результата, при сложении на бумаге или в уме, нами отмечается, например, как "на ум пошло". То есть 1+9 равно 0 и "1 на ум пошло". Вот это "на ум пошло" и называется возникновением переноса.
Переносы автоматически возникают при выполнении операции сложения для каждой цифры числа. Просто перенос может быть равен нулю, как при сложении цифр 3 и 2. Внутри числа этот перенос называется межразрядным. Межразрядный перенос является исходящим для результата сложения. Но он же является входящим для операции сложения последующих цифр (разрядов) числа. И обязательно учитывается при операции с очередными цифрами, что и показано на иллюстрации. Просто при сложении чисел в десятичной системе счисления мы обычно не учитываем (не обрабатываем дополнительно) нулевые переносы.
Поскольку операция сложения выполняется справа налево, можно сказать, что второй разряд результата (равный 9 на иллюстрации) зависит от результата сложения предыдущего разряда (0, точнее 10, на иллюстрации). То есть, каждый последующий разряд результата зависит и от результата операции для предыдущего разряда. Или, что результат операции каждого разряда влияет на результат операции последующего разряда.
Вот это и есть та самая взаимозависимость между отдельными разрядами. Только проявляется она не при хранении числа, а при выполнении операций с числами.
Иллюстрация для десятичной системы счисления несколько неудачно показывает "исходящий перенос". Дело в том, что мы в обычной жизни это не выделяем как перенос. Но видно, что мы складывали два четырехразрядных числа, а результат занимает 5 разрядов. Вот это последний исходящий перенос, из старшего разряда результата, и считается исходящим для операции сложения в целом.
Что бы все стало более понятным, давайте перейдем в двоичной системе счисления и рассмотрим сложение двух тетрад
Да, я знаю, что более привычным было показать операцию с байтами и многобайтным представлением чисел. Но на самом деле нет никакой разницы и в случае тетрад, слов, двойных слов. Перенос связывает разряды внутри числа. Даже в том случае, если число хранится в нескольких ячейках памяти из-за недостатка разрядности.
Просто исходящий/входящий переносы зачастую вынесены в специальный бит в слове состояния процессора (машины). И этому есть простое объяснение. Межразрядные переносы не выходят за рамки самой операции, их не нужно где то запоминать и хранить отдельно. Исходящий и входящий переносы существуют между выполнением отдельных операций. А значит, такой перенос нужно где то сохранять. И слово состояния процессора идеально для этого подходит.
Для операции вычитания значение переноса сохраняется. Но теперь он используется не для переноса части результата в последующий разряд, а для заема из последующего разряда. Поэтому иногда говорят о бите заема/переноса в слове состояния процессора.
Является ли перенос, как результат выполнения операции, ошибкой? Ведь он означает, что результат не поместился в отведенное ему место. Ответ на этот вопрос не так прост. Поэтому давайте попробуем разобраться.
Во первых, очевидно, что межразрядные переносы ошибкой не являются. Они являются непосредственными участниками операции, как мы только видели. А значит, не являются ошибками и промежуточные переносы (между тетрадами, байтами, словами, и т.д.), которые тоже являются межразрядными пр своей сути. Однако, здесь есть исключения, которые мы скоро рассмотрим.
Во вторых, исходящий перенос операции в целом является (или может являться, по усмотрению программиста) ошибкой для чисел без знака, так как результат выходит за границы разрядности участвующих в операции чисел. При этом можно говорить о переполнении разрядной сетки. Но тогда почему "может"? Просто иногда такое переполнение можно, и нужно, игнорировать, например, в адресной арифметике, когда адресное пространство просто "заворачивается" к началу. Поэтому окончательное решение принимает программист.
Для чисел со знаком мы как раз и сталкиваемся с тем самым исключением, о котором я говорил ранее. Дело в том, что при представлении отрицательных чисел в дополнительном коде мы может использовать универсальные операции, но в них, на равных с информационными, участвует и знаковый бит. Поскольку команда не учитывает знаковость, возможна ситуация, когда знак результата оказывается неверным. Например, для байта
Это явная ошибка, хотя исходящий перенос отсутствует. При этом мы ранее видели, что исходящий перенос есть, но результат верен. А раз так, сам по себе перенос не является ни критерием ошибки, ни критерием ее отсутствия. Нужны дополнительные условия.
Это условие выглядят так: "ошибка отсутствует, если количество переносов с знаковый бит равно количеству переносов из знакового бита", для чисел со знаком. Это кажется сложным, но все достаточно просто. В последнем примере у нас был перенос в знаковый бит, но не было ни одного переноса из знакового бита (нет исходящего переноса). А значит, результат ошибочный.
В примере со сложением 5371 и -2418 у нас был перенос в знаковый бит, но был и перенос из знакового бита (исходящий перенос). Поэтому результат верный. Даже не смотря на наличие исходящего переноса в последнем случае.
Вы можете самостоятельно проверить это, и даже доказать математически. Теперь вы знаете достаточно для этого.
Переполнение точно так же, как и перенос, часто представлено специальным бит в слове состояния процессора.
Существуют и аналогичные правила для операции вычитания, только там речь идет о заемах. Для операций умножения и деления тоже существуют правила установки/сброса битов переноса и переполнения, но это уже менее стандартно и обычно описывается на процессор.
Переносы и переполнения применимы и для троичной симметричной системы счисления. Правила сброса/установки этих признаков (бит), будут отличаться, но их суть остается точно такой же. Мы не будем отдельно рассматривать выполнение операций в троичной системе счисления.
Заключение
Мы немного больше узнали о представлении чисел в ЭВМ, правда пока только целых. Таких простых целых чисел. А простых ли? Правда мы рассматривали вопрос с точек зрения "почему так" и "как это устроено". Иначе хватило бы пары строчек и определений.
На этом мы не заканчиваем изучать глубинные аспекты представления чисел в ЭВМ. Причем в следующей статье мы продолжим разбираться именно с целыми числами. Там еще много интересного. Ну а после этого сможем заняться и более сложными вопросами.
Будет интересно, но не факт, что просто.