Реализация собственного типа decimal на C (аналог s21_decimal)
Структура данных для десятичных чисел
Decimal с фиксированной точностью можно реализовать как структуру, содержащую:
Мантиссу – большое целое число, хранящее все значащие цифры;
Показатель степени (scale) – целое для хранения позиции десятичной запятой (сколько цифр после запятой);
Знак – флаг положительного/отрицательного числа.
Такой подход позволяет поддерживать до 28–30 десятичных знаков, что достаточно для финансовых расчетов и точных вычислений. В языке C удобно представить мантиссу как массив из нескольких 32-битных слов. Например, в проекте s21_decimal мантисса реализована 96-битным числом, хранящимся в массиве uint32_t bits[4]�
github.com
�
github.com
.
bits[0], bits[1], bits[2] – младшие, средние и старшие 32 бита мантиссы (в сумме 96 бит)�
github.com
. Это позволяет представить целое до
2
96
−
1
≈
7.9
×
10
28
2
96
−1≈7.9×10
28
, то есть ~28–29 десятичных цифр.
bits[3] – поле флагов, хранящее знак и показатель степени (scale). В этом 32-битном слове:
Бит 31 отвечает за знак (0 – число положительное, 1 – отрицательное);
Биты 16–23 хранят показатель степени (количество цифр после запятой) от 0 до 28�
github.com
. Он указывает, на какое число
10
𝑛
10
n
нужно поделить мантиссу.
Остальные биты bits[3] не используются и должны быть равны 0�
github.com
.
Такое разбиение соответствует схеме .NET Decimal и обеспечивает диапазон значений ~
±
(
2
96
−
1
)
/
10
28
±(2
96
−1)/10
28
. Тrailing zeros (замыкающие нули) могут сохраняться в scale – например, число 1.2300 и 1.23 имеют одинаковое значение, но могут храниться с разным scale (4 и 2) для сохранения лишних нулей; эти нули не влияют на результаты арифметики или сравнения�
github.com
. Выбор типов: для мантиссы целесообразно использовать беззнаковые типы (uint32_t), поскольку знак отдельно. Массив из 3 элементов по 32 бита (96 бит) дает ~28 десятичных цифр точности. Если нужно до 30 цифр, можно зарезервировать 4-е слово под мантиссу (128 бит), но тогда часть бит уйдет под флаги. В s21_decimal фактически задействовано 96 бит под значение и 32 бита под флаги. Такой статический размер упрощает операции – все числа имеют одинаковую максимальную точность.
Битовое представление десятичного числа
Внутри наше число хранится как целое и scale. Десятичная запятая не хранится явно, её положение задается scale. Числовое значение вычисляется как:
value
=
mantissa
×
10
−
scale
,
value=mantissa×10
−scale
, с учетом знака. Например, рассмотрим число 123.45 (знак +, scale = 2):
Мантисса должна хранить значение 12345 (целое без запятой).
Показатель степени = 2 (означает, что последние 2 цифры – дробная часть).
Знак = 0 (положительное).
В памяти (массив int bits[4]):
bits[0] = 0x00003039 (двухбайтовое представление 12345 в hex; младшие 32 бита мантиссы)
bits[1] = 0x00000000 (средние 32 бита мантиссы = 0)
bits[2] = 0x00000000 (старшие 32 бита мантиссы = 0)
bits[3] = 0x00020000 (флаги: знак 0, scale = 2).
Разберём содержимое bits[3] в двоичном виде для примера 123.45:
markdown
Копировать
Редактировать
bits[3] = 0 0000000 00000010 0000000000000000 (2 в двоичном представлении с нужным сдвигом)
|_______|________|________________
| | \__ 16 бит не используются (0)
| \___________ 8 бит показателя степени = 2
\___________________ 7 бит не используются (0) + 1 бит знака = 0 (плюс)
В старшем слове bits[3] биты 16–23 содержат 00000010₂, что соответствует десятичному 2 (scale). Бит 31 равен 0, указывая на положительный знак, а все прочие биты bits[3] равны 0�
github.com
. Таким образом, bits[3] = 0x00020000 (в шестнадцатеричном формате) кодирует “scale = 2, знак = +”. Если число отрицательное, например -123.45, то мантисса остается той же (12345), scale = 2, но бит 31 в bits[3] устанавливается в 1. Для -123.45 bits[3] стал бы 0x80020000 – те же exponent bits + установленный знак. На этой схеме видно, что дробная часть не хранится отдельно – мы оперируем целой мантиссой, а позиция запятой задается степенью 10. Это реализует фиксированную десятичную точку: при одном и том же scale все числа имеют одинаковое количество десятичных разрядов после точки.
Арифметические операции и побитовые сдвиги
Реализация арифметики с таким типом требует аккуратной работы с 96-битными числами и учетом scale у каждого операнда:
Сложение и вычитание
Для сложения или вычитания двух decimal нужно сперва привести их к общему scale. Это означает: если у одного числа scale=2 (например 1.23, мантисса 123) а у другого scale=5 (например 0.00045, мантисса 45), нужно выровнять их дробные части. Обычно повышают меньший scale до большего – умножают мантиссу с меньшим scale на 10^(разность scale). В примере 1.23 (scale 2) превратится в 1.23000 (scale 5, мантисса 12300), после чего можно складывать/вычитать мантиссы напрямую. Далее выполняется длинная арифметика на 96-битных мантиссах:
Если знаки операндов одинаковы, мантиссы складываются; знак результата тот же.
Если знаки разные, вычитается меньшая мантисса из большей (для реализации вычитания), знак результата – знак числа с большей абсолютной величиной.
После целочисленного сложения/вычитания может получиться результат с ведущими нулями или, наоборот, требующий увеличения разрядности. Если после сложения мантисса оказалась больше 96 бит (переполнение), можно попробовать уменьшить scale (насколько позволяют значащие цифры) и выполнить округление, либо зафиксировать ошибку переполнения.
Перенос битов при сложении: поскольку мантисса занимает несколько 32-битных ячеек, реализация сложения похожа на сложение “в столбик” с переносом. Мы складываем младшие 32 бита (bits[0]) и проверяем перенос в старший разряд: если сумма превысила 0xFFFFFFFF, перенос = 1, и он добавляется к следующему 32-битному слову (bits[1]). Процесс повторяется для bits[1] + переноса -> bits[2]. Например, сложим мантиссы 0xFFFFFFFF и 0x1 (96-битные, остальные слова 0):
yaml
Копировать
Редактировать
0x00000000`FFFFFFFF (мантисса 1: bits[1]=0, bits[0]=0xFFFFFFFF)
+ 0x00000000`00000001 (мантисса 2: bits[1]=0, bits[0]=0x1)
= 0x00000001`00000000 (результат: bits[1] стало 0x1 из-за переноса, bits[0]=0x00000000)
Младшее слово переполнилось и дало перенос -> bits[1] увеличилось на 1. Таким образом, 0xFFFFFFFF + 1 = 0x1_00000000 (33 бита), и старший лишний бит ушел в следующий элемент массива. Аналогично происходит перенос и в bits[2], если переполнится bits[1]. Для вычитания мантисс алгоритм аналогичен, но используется заем при недостатке разрядов: если надо вычесть 1 из 0 в данном 32-битном слове, берем заем (занимаем единицу) у следующего слова, вычитая и там на 1 и добавляя 0x100000000 к текущему слову перед вычитанием. После сложения/вычитания может оказаться, что у результата больше дробных знаков, чем нужно (например, вы сложили 1.230 (scale=3) и 2.450 (scale=3) и получили 3.680 с тем же scale). Обычно scale результата берется максимум из операндов. Если получилось лишних значащих нулей справа, можно нормализовать результат – убрать лишние нули, уменьшая scale (но в рамках ограничения 0–28).
Умножение
При умножении двух decimal результирующее значение мантиссы = произведение двух 96-битных мантисс, а новый scale = сумма scale множителей (поскольку
10
−
𝑠
𝑐
𝑎
𝑙
𝑒
1
×
10
−
𝑠
𝑐
𝑎
𝑙
𝑒
2
=
10
−
(
𝑠
𝑐
𝑎
𝑙
𝑒
1
+
𝑠
𝑐
𝑎
𝑙
𝑒
2
)
10
−scale
1
�

×10
−scale
2
�

=10
−(scale
1
�
+scale
2
�
)
). Алгоритм: перемножить 96-битные числа можно "вручную" длинной арифметикой или используя 64-битные типы для частичного умножения. Максимальная длина произведения двух 96-битных чис – 192 бита (понадобится массив из 6 *32-бит слов). Далее:
Если полученное 192-битное число умещается в 96 бит после учета scale, то просто берем младшие 96 бит как мантиссу результата.
Если мантисса длиннее 96 бит, нужно сократить точность до 96 бит. Для этого уменьшают scale результата (чтобы отбросить лишние разряды) или выполняют округление. Например, если получилось 29 значащих цифр, можно уменьшить scale на 1 (отбросив последний десятичный разряд) и округлить результат по правилам (см. ниже про банковское округление). В s21_decimal указано применять банковское округление, если результат не вмещается в мантиссу�
github.com
.
Сумма показателей степени не должна превысить 28; если больше – тоже потребуется снижение scale с округлением.
Побитовые сдвиги часто используются при умножении и делении больших чисел. Например, умножение на 10 можно реализовать как комбинацию сдвигов и сложений:
𝑥
×
10
=
(
𝑥
≪
1
)
+
(
𝑥
≪
3
)
x×10=(x≪1)+(x≪3) (т.к. 10 = 2 + 8). Сдвиг влево << на 1 бит эквивалентен умножению числа на 2, а на 3 бита – умножению на 8. Комбинируя, получаем умножение на 10 без большой 96*96-битной операции. Аналогично, деление на 2 реализуется сдвигом вправо >>. Однако для деления на 10 такой трюк не подходит, тут применяют длинное деление. Тем не менее, побитовые сдвиги полезны при смещении частей мантиссы между bits[0..2]: сдвиг всего 96-битного значения влево требует сдвигов каждого элемента и переноса бит между ними. Например, сдвиг влево на 1 бит:
bits[0] получит все биты исходного bits[0] сдвинутые на 1 влево, а его самый значимый бит (бит 31) пойдет в младший бит bits[1].
bits[1] сдвигается и принимает перенос от bits[0], его старший бит переходит в bits[2].
bits[2] сдвигается влево, его выпадающий бит (бывший 31-й) теряется (или вызывает переполнение, если был 1).
Таким образом можно реализовать умножение на 2^n (сдвиг влево на n бит) и деление на 2^n (сдвиг вправо) для больших чисел. В контексте десятичной арифметики это нужно, например, для масштабирования при выравнивании scale: умножение мантиссы на 10^k можно делать k раз сдвигом/сложением, но чаще проще применять готовую big integer арифметику или умножение в несколько этапов. Главное – следить за переполнениями при сдвигах.
Деление
Деление двух decimal более сложное. Требуется вычислить:
mantissa
res
=
mantissa
1
mantissa
2
,
mantissa
res
�
=
mantissa
2
�

mantissa
1
�

�
, а scale результата =
scale
1
−
scale
2
scale
1
�
−scale
2
�
(поскольку
10
−
𝑠
1
/
10
−
𝑠
2
=
10
−
(
𝑠
1
−
𝑠
2
)
10
−s1
/10
−s2
=10
−(s1−s2)
). Но мантиссу результата, как правило, нужно расширить для точного деления. В десятичной арифметике при делении может получиться бесконечная десятичная дробь (например, 1 делить на 3). Поэтому нужно ограничивать точность 28 разрядами и округлять результат. Подход к делению:
Выравнивание: если
scale
1
<
scale
2
scale
1
�
2
�
, можно увеличить scale первого числа (умножив мантиссу на 10) несколько раз, чтобы вычитание показателей не дало отрицательного результата. Например, деление 5.00 (scale=2) на 2 (scale=0) можно переписать как 5.00 / 2.00 (приведя оба к scale=2) без изменения значения второго числа.
Выполнить целочисленное деление 96-битной мантиссы1 на 96-битную мантиссу2, получив результат и остаток. Это делается «в столбик» или алгоритмом, похожим на деление длинных чис вручную. При этом, чтобы получить достаточную точность, возможно, придется дополнительно масштабировать делимое: например, чтобы получить 28 знаков после запятой в результате, можно умножить мантиссу1 на
10
𝑛
10
n
перед делением (с последующим увеличением scale), пока не достигнем нужной точности или пока остаток не станет 0.
Полученное целое частное будет мантиссой результата. Разница scale скорректирована на этапе 1 и за счет возможного домножения мантиссы.
Если был остаток от деления – результат не точный. Необходимо решить, как округлить. Согласно условию, следует использовать банковское округление (round half to even).
Пример:
1
/
3
1/3. Мантиссы: 1 и 3, оба scale=0. Чтобы получить результат с scale= ~28, можно мантиссу 1 умножить на
10
28
10
28
и разделить на 3. Получим приблизительно 0.3333333... с остатком. Округляем до 28 знаков после запятой. Если мантисса не помещается в 96 бит, снижаем её, уменьшая scale и округляя.
Округление к ближайшему чётному (банковское округление)
Банковское округление – это способ округления .5 случаев “к ближайшему чётному” числу, чтобы устранить систематическую погрешность. Правило: если отбрасываемая часть больше половины – округляем вверх, если меньше – вниз; если ровно половина (например, 2.5, 3.5000... точно) – тогда к ближайшему чётному значению�
ru.wikipedia.org
. Это значит, что 2.5 → 2, а 3.5 → 4�
ru.wikipedia.org
(оба одинаково удалены от целых 2 и 3 или 4, но выбирается чётное). В контексте 96-битного decimal это применяется, когда результат имеет больше 28 значащих десятичных цифр, и нужно отбросить лишние. Алгоритм:
Посмотреть первую отбрасываемую цифру (d) и остальные за ней.
Если d < 5 – просто отбросить (округление вниз, “floor” к ближайшему).
Если d > 5 – округлить вверх (прибавить 1 к последней сохраняемой цифре).
Если d == 5 и все следующие цифры после неё нули (то есть число ровно посередине) – округлить к ближайшему чётному: посмотреть последнюю сохраняемую цифру. Если она нечётная – увеличить на 1 (станет чётной), если уже чётная – оставить как есть.
Если d == 5 и дальше есть ненулевые цифры (например 2.5001) – это больше чем ровно половина, поэтому округляем вверх.
Пример: число 7.25 округляем до 1 знака после запятой. Здесь отбрасываемая часть “5”. 7.2(5) – последняя сохраняемая = 2 (чётная), поэтому 7.2 остаётся 7.2 (а не 7.3). А 7.35 -> 7.4, потому что сохраняемая 3 (нечётная) округлится до 4. Такое правило обеспечивает статистически нейтральное округление в финансовых расчётах. В реализации проверка .5 упрощается, если оперировать целыми: “.5” означает, что остаток при делении на
10
𝑛
10
n
ровно половина этого
10
𝑛
10
n
. Можно сравнить 2*остаток с модулем деления и увидеть равенство, а затем проверить чётность последнего разряда мантиссы.
Использование побитовых масок
Битовая маска – это двоичное число, используемое для выделения или изменения отдельных битов в другом числе. Маска представляет набор бит, где 1 обозначает “этот бит затронуть”, а 0 – “не трогать”. Побитовые операции AND (&), OR (|), XOR (^) и NOT (~) в сочетании со сдвигами позволяют удобно работать с отдельными битами:
Установка бита в 1: используем операцию OR с маской, у которой нужный бит = 1. Например, чтобы выставить знак отрицательного числа, применяем маску 0x80000000 к bits[3]:
c
Копировать
Редактировать
bits[3] |= 0x80000000; // установить бит 31 в 1 (делаем число отрицательным)
Здесь маска 0x80000000 имеет двоичный вид 100...0 (1 в бит 31, остальные 0). OR устанавливает этот бит, не затрагивая другие (поскольку x | 1 = 1, а x | 0 = x для каждого бита).
Сброс бита в 0: используем AND с инвертированной маской, где нужный бит = 0, остальные 1. Например, чтобы обнулить знак (сделать число положительным):
c
Копировать
Редактировать
bits[3] &= ~0x80000000; // сбросить бит 31
Операция NOT даст маску ~0x80000000 = 0x7FFFFFFF (бит 31 = 0, остальные = 1). AND с этой маской обнулит бит 31, сохранив остальные (поскольку x & 0 = 0, x & 1 = x).
Проверка состояния бита: применяем AND с маской и смотрим на результат. Если результат ≠ 0, значит бит был 1. Например:
c
Копировать
Редактировать
if (bits[3] & 0x80000000) {
// знак отрицательный
}
Здесь маска оставит только бит 31, и если он был 1, условие сработает.
Инверсия бита: можно использовать XOR. XOR с 1 меняет бит на противоположный:
c
Копировать
Редактировать
bits[3] ^= 0x80000000; // поменять знак на противоположный
Если бит был 1, станет 0; если 0 – станет 1.
Помимо управления знаком, маски используются для работы с показателем степени. Например, чтобы извлечь значение scale из bits[3], можно взять побитовый AND с маской, которая оставляет биты 16–23, а затем сдвинуть результат вправо. Маска для бит 16–23: 0x00FF0000 (в двоичном: 8 единиц на позициях 16–23). Применяя:
c
Копировать
Редактировать
int raw_scale = (bits[3] & 0x00FF0000) >> 16;
мы получим число от 0 до 28 — значение показателя степени. Установка нового scale делается схожим образом: обнулить старые биты scale AND-ом с инвертированной маской ~0x00FF0000, затем OR с новым значением, сдвинутым в нужную позицию:
c
Копировать
Редактировать
bits[3] &= ~0x00FF0000; // очистить биты 16-23
bits[3] |= ((uint32_t)new_scale << 16); // записать новый scale
Таким образом, маски позволяют адресно работать с определенными битами внутри поля флагов или мантиссы. В decimal-типе мы часто оперируем сразу целыми 32-битными словами, но когда нужно проверить, например, знак или отдельный флаг, маски незаменимы.
Сравнение с IEEE 754 Decimal64
IEEE 754 Decimal64 – это стандартный формат десятичного числа с плавающей запятой, определенный в IEEE 754-2008. Он отличается от нашего самодельного типа следующим:
Размер и точность: Decimal64 занимает 64 бита (8 байт) и способен точно представить до 16 десятичных цифр�
en.wikipedia.org
. Наша реализация s21_decimal использует 128 бит (4 * 32) с 96-битной мантиссой (~28–29 значащих цифр). То есть custom decimal имеет существенно бóльшую точность, но и больший размер в памяти.
Диапазон значений: Decimal64 – формат с плавающей точкой, поэтому имеет отдельное поле для экспоненты (порядка числа). Он может представлять как очень большие, так и очень маленькие числа, хотя точность всегда ~16 цифр. Диапазон порядка порядка ±10^384 (порядок от -383 до +384)�
habr.com
�
en.wikipedia.org
. Для сравнения, наш тип фиксирует порядок строго от 0 до 28 (scale), но мантисса сама может быть порядка 10^28. В итоге custom decimal охватывает максимум ~
7.9
×
10
28
7.9×10
28
(если scale=0) или минимум ~
10
−
28
10
−28
(если хранится число 1 с scale=28).
Представление и особенности: Decimal64 кодирует число в научной нотации: в 64 битах поля отводятся под коэффициент (значащие цифры) и порядок (экспоненту) в десятичной системе. Существуют две схемы кодирования значащих цифр (Dense Packed Decimal и Binary Integer Decimal), позволяющие уместить 16 десятичных цифр в бинарный формат. Наш s21_decimal же – по сути фиксированная точка, где масштаб ограничен 28 и не эксплуатируется динамически. Также Decimal64 поддерживает специальные значения: NaN (не число), Infinity (бесконечность), -0 (отрицательный ноль) и денормализованные числа�
en.wikipedia.org
, как и бинарные float’ы. В самодельном decimal обычно таких понятий нет (мы можем условно иметь -0 и +0, но они считаются равными).
Когда использовать стандартный Decimal64: если нужна совместимость со стандартами IEEE 754, или если ваша платформа/язык имеет поддержку десятичной плавающей арифметики (например, тип _Decimal64 в C компилятора GCC, или decimal128 в некоторых СУБД), имеет смысл воспользоваться ими. Decimal64 обеспечивает широкий динамический диапазон и аппаратную поддержку на некоторых системах (например, IBM Power). Однако, он ограничен 16 цифрами – для финансовых расчетов этого может быть мало, и нужно следить за накоплением ошибок округления при последовательных операциях.
Когда предпочтителен свой decimal (s21_decimal): если требуется больше точных знаков (28–29), определенность фиксированного scale (например, всегда работать с копейками, 2 знака, или с четко 28 знаками), или отсутствие поддержки Decimal64 в среде. Custom decimal удобен, чтобы полностью контролировать арифметику: вы сами прописываете правила округления, контроля переполнений и пр. Кроме того, .NET Decimal (128-бит) де-факто стандарт в ряде задач (финансы, бухгалтерия), поэтому реализовать аналогичный может быть полезно для совместимости.
Итого: IEEE 754 Decimal64 – это стандартизированный тип с плавающей запятой в десятичной системе, компактный и универсальный, а s21_decimal – пользовательский тип с фиксированной запятой, дающий повышенную точность и предсказуемость. Выбор зависит от требований: для широкого диапазона и интеграции со стандартами лучше Decimal64�
habr.com
, а для максимальной точности в ограниченном диапазоне (например, финансовые суммы до триллионов с точностью до копейки) – собственный decimal на 128 бит.