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

Представьте, что вы считаете яблоки. Вы говорите: «У меня 33 яблока». Все яблоки считаем десятками. Отсчитали первый десяток, сделали перенос, второй десяток - ещё перенос, третий десяток – третий перенос. И ещё три яблока. Итого 3 десятка и три яблока. А если было бы не 33, а 333 яблока, то точно так же десятками считали бы десятки, чтобы получить сотню. Затем сотни, тысячи и т.д. Это однородная система, в каждом разряде «максимум» счёта (основание) = 10.

А теперь представьте, что вы считаете время. «Прошло два дня, 5 часов, 10 минут и 35 секунд». У вас тут и дни, и часы, и минуты, и секунды. И у всех разный «максимум» разряда. Это и есть смешанная система счисления. Почему? Потому что в одном разряде у нас «вмещается» одно число, в другом — другое:

• В разряде секунд — максимум 60 (как только набирается 60, они превращаются в 1 минуту).
• В разряде минут — тоже максимум 60 (становятся 1 часом).
• А в разряде часов — максимум 24 (становятся 1 сутками).

Ещё примеры из жизни:

Длина (старая русская система):

• 1 сажень = 3 аршина
• 1 аршин = 4 пяди
• 1 пядь = 4 вершка
• 1 вершок = 4.4 см

Получается, что 1 сажень = 3 аршина = 12 пядей = 48 вершков = 211,2 см. Шаги различаются, получается смесь «максимумов».

Дюймы и футы (английская система):

• 1 ярд = 3 фута
• 1 фут = 12 дюймов

Опять в каждом разряде свой лимит.

В программировании и электронике часто используется смесь двоичной и шестнадцатеричной систем.

Например, в компьютере всё внутри в двоичном виде (0 и 1). Но человеку читать длиннющую строку 101011110011 неудобно. Поэтому берут и группируют двоичные цифры по 4 штуки (тетрады). А 4 двоичных цифры — это ровно одна шестнадцатеричная цифра (от 0 до F).

То есть мы считаем смешанно:

• Внутри одной шестнадцатеричной цифры — двоичная система (лимит 2).
• А сами цифры идут в 16-ричной системе (лимит 16).

Возьмем для примера число `2027_10`. Переведём его в двоичную систему `11111101011_2` (каким-нибудь способом, например, делением с остатками), а потом запишем как `0111` `1110` `1011_2`. Из такой записи мы сможем его легко «конвертировать» в шестнадцатеричную систему, используя только знания о соответствиях двоичной и шестнадцатеричной записи цифр 0-F. Таким образом у нас получится смешанная система 2-16.

• `2027_10` = `11111101011_2` = `0111` `1110` `1011_(2-16)` = `7EB_16`.

«Бонус» такой системы, что порядок ноликов и единичек не изменяется. То есть мы просто режем длинное двоичное число на тетрады (группы цифр по 4 штуки), начиная с хвоста и всё. Если получившиеся кусочки снова «склеить», то вновь получится прежнее число.

А теперь давайте рассмотрим смешанную систему 2-10, так называемый двоично-десятичный код. Чтобы записать максимальную в десятичной системе цифру `9_10` нам понадобится 4 двоичных разряда, как и для шестнадцатеричного числа `F_16`. Но лимит разряда у нас теперь будет не 16, а 10, поэтому двоичная запись тетрады сможет достигать не `F_16=1111_2`, а всего лишь `9_10=1001_2`. Если мы просто порежем наше двоичное число, как и раньше, на три тетрады, то получится невозможная запись. 1110 и 1011 не могут существовать в двоично-десятичной системе, т.к. 6 чисел, больших чем 1001, запрещены в такой записи.

Чтобы получить корректную запись числа `2027_10`, нам надо будет каждую его десятичную цифру записать двоичным кодом:

• `2027_10` = `0010` `0000` `0010` `0111_(2-10)` = `10000000100111_(2-10)`.

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

Попробуем посчитать, сколько будет «похожее» на него `10000000100111_(2-16)`:

• `10000000100111_(2-16)` = `0010` `0000` `0010` `0111_(2-16)` = `2027_16` = `8231_10`.

О как, в 4 раза больше получилось. Потому что `2027_10` совсем не то же самое, что `2027_16`.

Приходим к выводу, что запись одного и того же числа в двоичной системе совпадает с записью в 2-16, а с записью в 2-10 (BCD) не совпадает. Такие пироги. В связи с этим с такими числовыми смешанными системами нужно быть очень аккуратными, особенно если преобразования пытаетесь делать сами на бумажке или в голове. Но за компьютеры и калькуляторы можете не волноваться, они всё корректно посчитают, программисты уже давно всё продумали.

Существует несколько форматов представления BCD:

• Упакованный (Packed BCD) – В одном байте (8 бит) хранятся две десятичные цифры, каждая в своей тетраде. Например, число 1234 в упакованном BCD будет выглядеть как 0001 0010 0011 0100. Этот формат более эффективен по памяти, но требует дополнительной обработки для извлечения отдельных цифр.
• Неупакованный (Unpacked BCD) – Каждая десятичная цифра занимает отдельный байт, причём старшие 4 бита обычно не используются (часто устанавливаются в 0). Например, число 5 в неупакованном BCD — это 0000 0101. Этот формат проще в обработке, но менее эффективен по памяти. Часто используется при посимвольном вводе-выводе.
• Код с избытком 3 (Excess-3) – Перед кодированием к каждой цифре прибавляется 3 (0011 в двоичной системе). Это упрощает реализацию некоторых арифметических операций.
• BCD со знаком – Для представления отрицательных чисел используются разные методы: прямой код (старший бит или тетрада для знака), дополнительный код (дополнение до 10 в соответствующем разряде).

Плюсы BCD:

• Упрощённый ввод-вывод. Не нужно преобразовывать всё число целиком — достаточно вывести каждую тетраду отдельно.
• Точное представление десятичных дробей. Это критично для финансовых расчётов, где ошибки округления недопустимы.
• Упрощённые операции умножения и деления на 10, а также округления.

Минусы BCD:

• Неэффективное использование памяти. На каждую десятичную цифру требуется 4 бита, но теряется 6 из 16 возможных комбинаций.
• Усложнённые арифметические операции. При сложении, если сумма в тетраде превышает 9 (или возникает перенос), требуется коррекция (обычно просто прибавляется 0110=6₁₀).

Двоично-десятичный код широко используется в:

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

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

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

Фибоначчиева система счисления — это система представления целых неотрицательных чисел, основанная на числах Фибоначчи. Её ключевая особенность — использование теоремы Цекендорфа: любое натуральное число можно единственным образом представить в виде суммы различных чисел Фибоначчи, в которой нет двух соседних чисел из последовательности.

Веса разрядов образуют рекуррентную последовательность, а не геометрическую прогрессию, как в классических позиционных системах с постоянным основанием (вроде двоичной или десятичной). Весами разрядов являются числа последовательности Фибоначчи без первой единицы: 1,2,3,5,8,13,21,…

Правила записи:

• Используются только цифры 0 и 1, как в двоичной системе.
• Запись читается справа налево или слева направо по весам из последовательности Фибоначчи: например, разряд с весом 21, потом 13, потом 8, и так далее.
• В записи числа не должно быть двух единиц подряд.

Последнее правило отличает систему Фибоначчи от привычных систем счисления. Запрет на две единицы подряд — главное правило, которое делает представление уникальным. Из-за этого арифметические операции (сложение, вычитание) устроены сложнее, чем в обычных системах: нужно учитывать «переносы» и устранять пары соседних единиц (например, заменять 11 в каких-то позициях на эквивалентную комбинацию).

Пример: как записать число 10. Ищем наибольшее число Фибоначчи, не превосходящее 10, — это 8. Остаток: 10−8=2. Наибольшее число Фибоначчи ⇐2 — это 2. Остаток 0. Получили: 10=8+2=`F_5`+`F_2`. Теперь формируем запись по весам (в порядке убывания): 21,13,8,5,3,2,1: `0010010_(Fib)` или без ведущих нулей `10010_(Fib)`.

Ещё один пример: число 20. 20=13+5+2 (все числа Фибоначчи; соседние в последовательности не используются: `13=F_6`, `5=F_4`, `2=F_2`). По весам 21,13,8,5,3,2,1: 0,1,0,1,0,1,0 → `101010_(Fib)`

На основе фибоначчиевой системы счисления (ФСС) был придуман «код Фибоначчи» — это универсальный префиксный код для представления натуральных чисел, тесно связанный ФСС и теоремой Цекендорфа. Его активно используют в сжатии данных и передаче информации.

Как строится код Фибоначчи

• Берём представление числа по Цекендорфу. Это сумма различных чисел Фибоначчи, где не используются два соседних числа из последовательности. Например, для последовательности 1,2,3,5,8,13,… представление единственно.
• Записываем биты по позициям чисел Фибоначчи. Если число Фибоначчи участвует в сумме — ставим 1, если нет — 0. Обычно биты идут от меньших к большим (или наоборот — главное быть последовательным).
• Добавляем в конец ещё одну 1. Это ключевое отличие кода Фибоначчи от «чистого» представления Цекендорфа: финальная дополнительная единица служит маркером конца кодового слова.
• Из‑за этого в коде Фибоначчи единственное вхождение комбинации 11 всегда находится в самом конце, а внутри кодового слова двух единиц подряд быть не может.

Пример кодирования числа 10. Раскладываем по Цекендорфу: 10=8+2. Числа Фибоначчи: 1,2,3,5,8,…. Биты по позициям (от 1 до 8) 01001 (если идём от меньшего к большему). Добавляем в конец ещё одну 1: 010011. Это и есть код Фибоначчи для числа 10. То есть запись выглядит как число ФСС, записанное задом-наперёд и с дописанной в конце единичкой. Декодирование происходит в обратном порядке. Откидывается последняя единичка, далее складываем веса разрядов, в которых стоят единички.

Важные свойства:

• Самосинхронизация. Поскольку маркер конца — это 11, приёмник может надёжно определять границы кодовых слов даже при сбоях. Если в потоке данных появляется 11, это почти наверняка конец текущего числа.
• Префиксность. Ни одно кодовое слово не является началом другого — это позволяет декодировать поток без разделителей.
• Универсальность. Код подходит для кодирования произвольных натуральных чисел; чем больше число, тем длиннее код, но структура остаётся той же.

В общем смешанная система – это когда для каждого разряда числа свой «потолок» (основание).

Как будто считаешь яблоки разными «коробками»: в одну коробку влазит 12 яблок, в другую — 30, а в третью — 100. И ты говоришь: «У меня 2 коробки по 12, 3 коробки по 30 и 1 коробка по 100». Это и есть запись числа в смешанной системе.

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