Число — основное понятие математики; абстрактная сущность, используемая для описания количества.
Как всегда, тема данного поста возникла во время беседы с ММК (моим молодым коллегой) об одной несложной задачке. Речь шла о том, чтобы определить нахождение текущего значения счетчика тактов внутри интервала относительно некоего заданного значения. Затруднения вызывал момент перехода счетчика через максимальное значение в нулевое («реролл» или переполнение). Немного переформулировав задачу, приходим к классической задаче о задании интервала времени при помощи аппаратного счетчика, решение которой давно известно (смотри исходники Linux). Однако внезапно выяснилось, что данное решение не представляется ММК очевидным и потребовались определенные разъяснения. Чтобы обратить внимание других (не моих) МК на данный аспект работы с числами и был создан настоящий пост. А посвящен он описанию различных способов представления множества целых чисел на конкретной битовой основе, их преимуществам и недостаткам.
Если Вам интересна эта тема, то можете нажать кнопочку ниже.
Часть 1, в общем то, необязательная.
Для начала определимся с понятием «число». Примечание на полях (Пнп): где-то я читал, что в аксиоматике, основанной на теории множеств, определение единицы появляется на 17 (а может и на 72, уже не помню, но точно не на первой) странице. Из примечания понятно, что маловероятно предъявление автором поста точного определения данного понятия, но будем считать, что оно интуитивно доступно любому образованному человеку, а тем более технически образованному (классно я выкрутился).
Следующий шаг заключается в определении «представления числа», и вот тут получше – мы имеем в виду некую воспринимаемую органами чувств (зрением, слухом, осязанием или иными) информация, которая по некоторым заранее определенным правилам может рассматриваться, как отображение «числа», что бы последнее не означало. Формализовав указанные выше правила, мы определяем «систему счисления» (СС), в которой можем «представлять» произвольные «числа». Пнп: формализация не всегда доступна представителям прекрасной (и лучшей - это мое личное мнение) половины человечества, почему и возникают нечеткие определения числа вроде "день или хотя бы год нашей свадьбы", которые ставят в тупик оставшуюся (не прекрасную) часть человечества.
Надо отметить, что существуют и более однозначно трактуемые определения, например: "число наших детей", "число Рейнольдса", "число Авогадро" - это все определения ничуть не хуже других. Здесь также имеется область совершенно восхитительных парадоксов вроде "Число, на единицу большее, чем наибольшее число, которое можно записать 84 символами", но все это предмет другого поста.
СС могут быть классифицированы различными способами: по количеству символов, по способу интерпретации символов и так далее, рассмотрим некоторые из них.
Исторически первой СС является «одноричная», в которой единица представлена неким физическим (счетная палочка, раковина, камешек) либо логическим (черточка на песке, крестик на бумаге, зарубка на палочке) объектом. Представления для любого числа – набор объектов, количество которых совпадает с представляемым числом, для нуля представление отсутствует (хотя последнее неточно). Кроме своей исторической ценности, других ценностей не имеет (в математическом плане), но, наверняка, имеет эстетическую либо идеологическую составляющую, чему свидетельство звездочки (крестики) на фюзеляжах истребителей.
Следует отметить, что уже на самых ранних этапах люди понимали основной недостаток данной СС - очень длинная запись и пытались использовать элементы позиционности - зарубки на другой грани палочки, крестики в строках по 10 штук, зачеркивание полных наборов (в 5, 7, 10) и так далее. Пнп: вот запись номера текущего года в такой "псевдопозиционной" одноричной системе (нет, это не 2 с лишним тысячи палочек):
||
@ (приходится вводить для обозначения 0)
||
|||
Естественным расширением этой системы является «не позиционные» СС с количеством элементов, более одного. Самая известная из них - так называемая "римская" СС, где вводятся дополнительные значки, заменяющие конкретную группу единичных элементов (V, X, L, C, M). Пнп: сразу обратим внимание, что уже в этой (достаточно примитивной и простой) СС значение знака может меняться в зависимости от контекста его расположение, вот почему называть ее «не позиционной» несколько неверно. Несомненным достоинством является простота, малое количество символов (для чисел, используемых в обычной жизни), небольшие размеры таблицы сложения и умножения. Но все это более чем компенсируется недостатками – по прежнему значительная длина записи, неоднозначность представления числа,проблемы с масштабированием и, самое главное - исключительно неудобные арифметические операции.
Пнп: а вот и очередной пример - MMXXIII.
Тем не менее, аналогичная данной СС до сих пор активно применяется, и в устной речи мы используем не позиционную систему, ведь мы, наряду с «три сотни» используем (гораздо чаще) форму «триста», а это и есть дополнительное обозначение для группы одинаковых символов. Да и «сто» - это условное обозначение для последовательности "десять десятков" или «один ноль ноль» - так что наверняка у такой СС есть не сразу видные преимущества, раз она столь устойчива, ну это уже область психологии, в которой автор откровенно плавает.
Обратим еще внимание на сложности, связанные со схожими по произношению числительными и поймем, почему в ответственных ситуациях представители некоторых языковых групп произносят курс по числам "one four zero" (а те, кому команда предназначена, подтверждают получение в той же форме).
Пнп: как всегда - две тысячи двадцать три.
Но закончим исторический экскурс и вернемся к привычным нам позиционным системам счисления, в которых значение числа, обозначенного некоторым символов, зависит не только от символа, но и от его позиции в записи представления. Эти СС (более конкретно - однородные и регулярные, а бывают и другие) объединяются в группу «-чные», среди которых особый интерес представляют СС с основанием 2, 3, 10, (6)12, 16(8).
1. Двоичная. Первая из них интересна тем, что она имеет минимально возможное основание для позиционной СС. Более того, реализация физического элемента с 2 возможными состояниями (включен и выключен) наиболее проста, почему эта СС и получила широкое распространение в вычислительной технике. Заметим также, что большая часть набора возможных логических функций, реализуемых на двоичной базе (а их 2**(2*2) = 16 штук), имеет вполне понятные аналоги в алгебре логики, а для оставшихся нетрудно подобрать чуть менее понятные, но вполне вменяемые аналоги. Пнп: нам придется трактовать символы "0" и "1", как "ложь" и "истина", но это несложно ("что есть истина - не ноль"). Далее мы будем рассматривать именно двоичную СС, но предварительно немного пробежимся по оставшимся.
Пнп: 11111100111.
2.Троичная. СС с основанием 3 является оптимальной (в некотором смысле этого слова) но с реализацией ей не повезло. Элемент с 3 устойчивыми (и гарантированно достижимыми и различимыми, что важно) состояниями выполнить «в железе» намного сложнее, чем с двумя, а попытки сделать троичный элемент на основе двух двоичных вызывают только чувство тягостного недоумения. Пнп: аппаратная избыточность в 33% ради выигрыша в примерно 5% (или 12%, при другой оценочной функции) - так себе идея. Отображение трех состояний в алгебру логики весьма сомнительно ("ложь", "истина", "не знаю" - не работает), большая часть (если не все) реализуемых функций (а их стало 3**(3*3)=19683, между прочим, поскольку экспонента х**(х*х) не менее беспощадная, чем гравитация) интерпретации не поддается, так что потенциальная сила данной СС не была раскрыта. В то же время она активно использовалась при передаче информации и кодировка 4B3T была предтечей нынешних систем с «большими созвездиями».
Так что в смысле вычислений данная СС представляет исключительно академический интерес. Интересное замечание - как первая позиционная СС с нечетным основанием, она позволяет нам спроектировать "сбалансированную" систему с символами, представляющими -1, 0 и 1, которая имеет уникальные свойства и вполне могла бы стать распространенной, но "не взлетела" из за уникальнейших же недостатков.
Пнп: 2202221, +0-+00-+.
3. Десятичная. Система с основанием 10 прежде всего интересна тем, что мы ее активно используем в повседневной жизни, например, все числа написаны в данном посту именно с ее использованием. Утверждается, что она является логическим расширением единичной системы с учетом наличия 10 пальцев (как правило) на руках человека. Лично мне кажется, что в данном случае была бы более логичной 11-ричная система, поскольку мы можем представить на пальцах двух рук числа от 0 до 10, а не до 9. Тем не менее существуют убедительные доводы в пользу естественного создания именно 10-ричной системы, так что гипотезу о получении этой СС от пришельцев из космоса с 9 щупальцами следует считать маловероятной, несмотря на ее несомненную сенсационность и привлекательность. Пнп: если вдруг я в ближайшее время перестану писать свои посты и исчезну, это будет убедительнейшим доказательством верности только что озвученной гипотезы, поскольку меня похитят рептилоиды из мирового правительства за разглашение сакральных знаний. Надеюсь, что опасность столь явного разоблачения их остановит и мы еще увидим другие посты данного автора.
Пнп: 2023.
4. Двоично-десятичная. Возможна также реализация 10СС на основе 2СС и называется она двоично-десятичной (BCD) – выделяем 4 бита под символ и используем только 10 состояний для отображения числа от 0 до 9. Избыточность данной системы очевидна и составляет 37%, но это плата за возможность читать результаты прямо с лампочек и, в свое время, ее платили. Так, например, «первая в мире полиненасыщенная ЭВМ» вполне могла быть как двоичной, так и двоично-десятичной и Кнутту это обстоятельство нисколько не мешало.
Пнп: 0010 0000 0010 0011.
5. Двенадцатеричная. А вот это совершенно естественная СС, основанная на числе 6 (умноженном на 2), все числа которой от 0 до 5 вполне себе представляются пальцами на одной руке и ничего лишнего нет. В ней есть масса преимуществ, например, значительное количество делителей. Эта система была одной из первых, исторически сложившихся и до сих пор существует в виде 60-ричной (6*2*5) СС, которой мы до сих пор пользуемся при отображении времени. Пнп: СС для отображения времени является великолепным примером неоднородной позиционной, поскольку в сутках 24 часа, а не 60. Именно благодаря данному обстоятельству удалось реализовать воистину восхитительное соотношение "Пи секунд равны одному нановеку".
Однако, в силу непонятных мне причин, термины «дюжина» и «гросс» практически вышли из употребления, будучи вытеснены терминами «десяток» и «сотня», возможно, таблица умножения на 1212=144 элемента оказалась слишком сложна для заучивания. Пнп: на мой взгляд, слабое обоснование, но другого у меня нет.
6. Шестнадцатеричная (и восьмеричная). Самостоятельного значения не имеют, являются всего лишь попыткой сделать двоичную чуть компактнее, с этой задачей вполне справляются (особенно удачно это было сделано в архитектуре фирмы DEC, 105737 ... это было чудесно), но все остальное … я никогда не пробовал умножать ни в одной, ни во второй СС и не думаю, чтобы мне (или кому бы то ни было из инженеров, мнением нормальных людей пренебрегаем) это занятие понравилось.
Пнп: 7E7, 3747.
На этом экскурсию по окрестностям задачи, призванную продемонстрировать эрудицию автора и сообщить некоторые интересные факты, можно считать завершенной и сосредоточится исключительно на двоичной системе счисления.
Часть 2.
Представление чисел в этой системе (в виде записи на бумаге, никто ведь не ожидает увидеть рисунки реле или лампочек) осуществляется записью последовательность двух символов (мы привыкли к символам «0» и «1», но это не единственный вариант). Каждый символ представляет собой число 2**n (для «1») либо 0 (для «0»), где n – номер символа в последовательности, при этом нумерация начинается с 0 и возрастает при движении влево. Для получения представления эти числа суммируются, получая итоговый результат.
В привычной нам реализации получаем N=S{i=0,i<=k) (B[i]*2**i), где B - элементы записи и k - длина записи.
Будем дальше обозначать эту сумму, как S(B,k). Обратим внимание на разрядность k и связанную с ней проблему существования максимально представимого числа M=2**(k+1)-1. Минимальное представимое число, как легко видеть из формулы, равно 0. Для наглядности построим график, где по оси Х отложим S, а по оси У - N и убедимся, что они совпадают и вот получилась синяя линия на рисунке (спасибо, капитан, ведь это одно и то же, но "стрижка только начата"). Как нетрудно убедиться, мы с Вами получили представление для «натуральных» чисел, не больших M, с включенным в это множество нулем.
Немного о разрядности – понятно, что в реальной системе мы можем выделить только конечное количество двоичных символов (бит). Обычно определенное количество бит группируется в некий агрегат (слово), которое и является далее минимальной единицей хранения информации и с которым производятся различные манипуляции. Слова тоже могут объединяться в агрегаты большей длины (двойное слово и т.д.). Минимально возможный размер слова – 1 бит (теоретически возможны и слова длины 0, но изучение подобных систем может представлять исключительно теоретический интерес), и такие системы тоже встречались на заре развития (знаменитая машина Тьюринга именно такова), но по мере развития технических средств появились слова в 4 бита (первые МК), 8 бит (байтовые МК), 12 бит (ранние PDP), 16 бит (вот тут отметились практически все), 32 бита (и тут тоже), 64 бита (современный мэйнстрим), 128 и более (как правило, для векторной арифметики). Пнп: в далекой молодости (в 1985 году) автор разрабатывал кросс-систему в 16-битовой машине для 1-битового промышленного контроллера. Была и экзотика в 18, 24, 33, 43 и так далее бита в слове, но она сгинула, не оставив следа.
Чтобы не загромождать текст, дальнейшее описание будет вестись с упором на 4- битное слово («квад» или «ниббл») – достаточно длинный, что показать основные концепции и достаточно короткий, чтобы его представление было легко прочитать.
Итак, у нас две проблемы (эсминец и пуговица) -существование минимального и максимального представимого числа и если со второй справиться, в принципе, несложно, то с первой проблемой нам этот трюк не поможет. Чтобы победить вторую проблему, просто берем две записи с количеством двоичных символов разрядов (бит) k, располагаем одну перед второй и рассматриваем полученную последовательность, как одну запись с числом разрядов k*2, что расширяет диапазон представления до M=2**(2*k+1)-1, то есть очень сильно, при необходимости повторяем до готовности.
Как же нам решить первую проблему – представить числа, меньшие нуля, то есть отрицательные числа. Для начала надо определиться, что мы вообще хотим от такого представления:
1. Предсказуемость и однозначность трансляции – каждая запись представляет только одно число и это число определяется данной записью однозначно. С этим требованием у всех далее рассматриваемых представлений все хорошо, просто помним о нем.
2. Отсутствие пропусков – любое целое число из диапазона допустимых чисел имеет представление. С этим требованием также все хорошо. А вот со следующими требованиями по-разному у разных представлений.
3. Взаимная однозначность – сильное требование, никак не вытекает из двух предыдущих и устанавливает единственное представление для любого целого числа из диапазона допустимых значений.
4. Число ноль представляется последовательностью символов «0».
5. Простые арифметические операции над представлениями чисел, в идеале совпадающие с таковыми для натуральных чисел (синяя линия на рисунке 1).
Начинаем строить некое представление для отрицательных чисел. И первое, что приходит на ум, это представление «со смещением», или «с избытком». Берем число в обычном двоичном представлении и вычитаем из него некоторое заранее выбранное число, получая число в данном представлении. Тогда N=S(B,k)-D, где за D обычно принимают (M+1)/2, смотри красную линию на рисунке. Для принятых нибблов, то есть k=4 и D=8, число 0 будет представлено строкой «1000», 1 – «1001», -1 –«0111», 7 и -7 «1111» и «0001» соответственно, а строка "0000" олицетворяет число -8. Строим график (серая линия) и радуемся - у такого представления есть масса достоинств: оно простое и понятное, удовлетворяет требованиям 1-3 «сходу», не отвечает 4, да и фиг то с ним, ведь главная проблема не в этом. К сожалению, арифметические операции с таким представлением никак не могут совпасть с таковыми для натуральных чисел, что очевидно из следующей записи N1+N2=S(B1,k)-D+S(B2,k)-D=(S(B1,k)+S(B2,k))-D-D, что совершенно очевидно не совпадает с возможной записью суммы в общем случае. Этот фатальный недостаток – необходимость коррекции результата любой операций – не позволило данному представлению стать повсеместно применяемым. Тем не менее оно не забыто и до сих пор используется, например, именно так представлен порядок при записи чисел с плавающей точкой IEEE – в виде байта с избытком 128.
Попробуем сконструировать представление лучше. Для начала посмотрим, как это делается в обычной жизни с десятичной записью – вводится два дополнительных символа – "+" и "-" и один из этих символов ставится перед символами, представляющими собственно число, причем "+", как правило, подразумевают. Решение «простое, всем понятное и совершенно неверное», то есть нам не подходящее, поскольку мы не можем позволить себе дополнительные символы, у на есть только "0" и "1".
Но попытаемся использовать данную идею – добавим еще один бит и закодируем в нем знак при помощи нашего набора 0/1. Небольшое затруднение состоит в том, где разместить этот дополнительный бит и тогда мы решаем выделить один из битов слова и использовать для кодирования знака именно его. При этом надо понимать, что для представления собственно числа осталось на 1 бит меньше и диапазон представления уменьшился - ДарЗаНеБы.
Какой именно бит выбрать – целиком на наше усмотрение, но, если мы выберем один из битов внутри слова, всегда останется вопрос – почему именно его, а не другой, поэтому естественно рассматривать крайние биты – младший (с номером 0) или старший (с номером k). В свое время было принято решение использовать старший бит, им и будем руководствоваться. Как именно закодировать минус (для плюса тогда останется только один вариант) – вообще то, без разницы, примем, что минус обозначается символом 1. Мы только что изобрели «прямое» представление для целых чисел. Тогда число 0 будет представлено набором символов «0000» (или «1000»), число 1 –«0001», число -1 – «1001», 7 и -7 – «0111» и «1111» соответственно, зеленая линия на рисунке. Можно написать формулу для числа, представимого данной схемой N=(-1)**B[k]*S(B,k-1), но лучше преобразовать ее к виду N=(1-B[k])*S(B,k-1)-B[k]*S(B,k-1)=(1-2B[k])*S(B,k-1). Нарисуем соответствующий график (зеленая линия) и посмотрим на него повнимательнее, чтобы увидеть, как обстоят дела с требованиями в «прямом» представлении: 1 и 2) все хорошо. 3) так себе, есть 2 представления для числа 0 (обведено кружком), 4) нормально, одно из представлений 0 подходит. 5) очень плохо, немонотонность графика все губит на корню.
Общий вывод – представление неудачное, и использовать его в наше время контр-продуктивно. Хотя и оно не умерло до конца – в представлении чисел с плавающей точкой (в нормализованной форме) мантисса представлена именно в «прямом» формате, да еще и с подразумеваемым старшим битом. Попытаемся создать более удачное представление, сделав график монотонным (пусть с одиночным разрывом).
Если для отображения отрицательного числа просто инвертировать все его разряды, включая знаковый, получим монотонное «обратное» представление. Соответствующая формула, написанная «в лоб», выглядит страшновато N=(1-B[k])*S(B,k-1)-B[k]*S(~B,k-1), но ее можно упростить, использовав (не)очевидное тождество S(~B,k-1)= M(k-1)-S(B,k-1). Получим гораздо более удобное N=S-B*S-B(M-S)=S-BS-BM+BS=S(B,k-1)-B[k]*M. Нарисуем соответствующий график (фиолетовая линия) и рассмотрим его. Мы видим 0, как последовательность «0000» (и как «1111»), 1 как «0001», -1 как «1110», 7 и -7 как «0111» и «1000» соответственно. У нас по-прежнему все хорошо с правилами 1 и 2, так себе с 3 (помечен кружком), нормально с 4, и, самое главное, стало намного лучше с 5. Мы уже можем применять обычные арифметические операции к данному представлению, но, к сожалению, есть один аспект, отличающий их результат – возникновение «кольцевого» переноса. Типичный пример -2+-1= «0010» + «1110» = (1)«0000» совершенно очевидным образом не равно 1 «0001» и нужно прибавить перенос, чтобы получить правильный результат. Причем самое ужасное в том, что не выполнив первую часть операции, нальзя узнать, потребуется ли дополнительный перенос. В общем то, с недостатками «обратного» представления можно было бы смириться, если бы не было следующего "поистине восхитительного" варианта.
Как говорил Ньютон «я стоял на плечах гигантов», кому-то из великих (Вики утверждает, что это был Джон фон Нейман) пришла в голову совершенно гениальная идея – взять «обратное» представления для отрицательных чисел и прибавить единицу. Тогда последовательность символов представляет собой число N=S(B,k-1)-B[k]*(M-1) и мы видим 0, как последовательность «0000», 1 как «0001», -1 как «1111», 7 и -8 как «0111» и «1000» соответственно. Смотрим на соответствующий график (голубая линия) и обнаруживаем, что при данной коррекции мы достигаем синтетического эффекта (чем и отличаются гениальные решения от просто хороших):
1 и 2 не нарушаются, с 3 все отлично, поскольку «отрицательный ноль» исчезает («0000» ~-> «1111» +1-> (1)«0000»), с 4 все хорошо и, самое главное, все отлично с 5,так что теперь мы можем производить операции сложения и вычитания с последовательностью битов по законам натуральных чисел и результат будет абсолютно верным без всяких коррекций. Пнп: мы не говорим о переполнении, оно в любом представлении является проблемой. Внимательный читатель мне скажет - но ведь функция немонотонна и имеет разрыв после точки 0111, но я применю хитрый трюк с продлением графика влево от 0 (тонкая голубая линия) и станет очевидно, что в этом представлении все хорошо.
Честно говоря, лично мне непонятно, почему не было сразу использовано столь замечательное представление. Единственное возможное объяснение – на первых машинах, где результаты вычислений выводились на индикаторы (ламповые, между прочим), прочитать битовое представление «прямого» кода очень легко, а «обратный» несложно превратить в «прямой» через элементы «исключающее ИЛИ» в то время, как «дополнительный» код потребует, кроме управляемого инвертора, еще и настоящего сумматора между регистром и лампочками. Ну и процесс смены знака сложнее, чем в "обратном" - надо не только проинвертировать, но еще и увеличить на 1.
Обратим внимание на важную особенность – при применении «дополнительного» кода мы больше вообще не задумываемся о представлениях и рассматриваем запись числа как цепочку символов, с которыми проводим операции, как с представлением натурального числа. И лишь потом мы можем по-разному интерпретировать результат операции – как без-знаковое число или как знаковое в «дополнительном» коде. Для этого у нас есть два набора команд сравнения – знаковые (BGT, BLE) и беззнаковые (BHI, BLOS). Пнп: так они назывались в системе команд PDP, у Вас они могут называться по другому.
А теперь мы можем, наконец то, поговорить о совершенно замечательном свойстве «дополнительного» представления, совпадающего с таким же для без-знаковых чисел. Если сложение без-знаковых чисел может привести к переполнению, то есть результат превзойдет наибольшее представимое число M (и неясно, что в этом случае делать, хотя язык C нам гарантирует нам результат - UB, что бы это не значило), то при вычитании переполнения не может возникнуть в принципе и мы всегда получаем верный результат – число, которое надо добавить к вычитаемому, чтобы получить уменьшаемое (возможно, с переполнением). При этом совершенно неважно расположение обоих операндов относительно начала отсчета: и 15-0=15, и 14-15=15, в обоих случаях нужно пройти от одного числа до другого по кругу 15 шагов. В то же время 15-14=1 и 0-15=1, в обоих случаях достаточно 1 шага. С учетом этого свойства исходная задача имеет очень простое решение – мы должны вычесть ТекущееЗначениеСчетчика из НачальноеЗначение+ВерхняяГраница и сравнить результат с ВерхняяГраница-НижняяГраница. Причем и разницу мы вычисляем с помощью вычитания и сравнение производится с его помощью, что и дает нам совершенно верный результат без всяких коррекций ы случае переполнения.
Разумеется, что это «поистине удивительное свойство» вычитания известно с момента создания дополнительного кода и активно используется в программировании, например, в системе времени Linux, где результат вычитания двух без-знаковых чисел интерпретируется как знаковое число с целью определения расстояния между ними, что позволяет экономить слово памяти для хранения границы и 2 операции при сравнении текущего значения с границей, для чего применяется еще 1 трюк, но об этом в другой раз.
