Игрушечная имлементация чисел с фиксированной точкой в C++

В C++ нет базового типа чисел с фиксированной точкой, в стандартной библиотеке также нет классов для них. В тоже время работа с числами с плавающей точкой (double, float) часто может быть неочевидна (например, ответьте на вопрос: ассоциативна ли операция сложения над ними?), вдобавок язык предоставляет (часто критикуемую) возможность перегрузки арифмитических операторов, подталкивая нас к созданию собственного типа данных.

Прежде чем писать код, давайте повторим мат. часть, а именно о представление чисел в типах uint8_t, int8_t и особенностях арифмитических операциях над ними. Итак, сложенение двух uint8_t происходит по модулю 256, то есть 1+2 = 3, но 1 + 255 = 0, для int8_t отрицательные значения можно ввести следущим образом: отрицательные числа соответсвуют тем безнаковым числам из uint8_t которые складываясь по модулю 256 дадут ноль, то есть -1 будем в памяти выглядить как 255 (FF). Границы типа int8_t -128…+127, для отрицательных чисел старший бит всегда равен 1. При умножении двух int8_t получаем результат типа int16_t, частное от деления int16_t на uint8_t будет иметь тип uint8_t. Все эти сведения носят аболютно тривиальный характер, но, они необходимы для дальнейшего понимания статьи.

Итак, перейдём к основной идее: что если мы мысленно возьмем значение типа int8_t и скажем, что теперь это не число единиц, а скажем, число 1/4 (проговорим словами: это число показывает сколько четвертых частей в исходном числе)? После чего инкапсулируем эту перменную в поле класса и перегрузим для него основные арифмитичекие операторы и напишем свой operator string() для правильного вывода таких чисел. Ниже, можно посмотреть, что получается из этой идеи.

#include <stdexcept> #include <cmath> #include <climits> #include <iostream> #include <sstream> #include <iomanip>  template <typename T> constexpr T ipow(T num, unsigned int pow) {     return (pow >= sizeof(unsigned int)*8) ? 0 :                pow == 0 ? 1 : num * ipow(num, pow-1); }  // fills and return given number of ones in the least significant bits of a byte constexpr uint8_t mask(uint8_t num) {     return num == 0 ? 0 : (mask(num - 1) << 1) | 1; }  // FractionLength - how many bits are after a period template <uint8_t FractionLength> class FixedPoint { public:      explicit FixedPoint(int decimal, unsigned int fraction = 0): val(0)     {         if (decimal > max_dec || decimal < min_dec || (decimal == min_dec && fraction) || (fraction >= full_fraction))         {             throw std::invalid_argument("It won't fit our so few bits");         }          int8_t sign = decimal > 0 ? +1 : -1;          val |= fraction;         val |= (decimal << FractionLength);         val *= sign;     }      explicit FixedPoint(double v): val(0)     {         double decimal_double = 0.0;         double fraction = std::modf(v, &decimal_double);          if (decimal_double > max_dec || decimal_double < min_dec)         {             throw std::invalid_argument("It won't fit our so few bits");         }          int8_t decimal_part = static_cast<int8_t>(decimal_double);         int8_t sign = v > 0 ? +1 : -1;         decimal_part = std::abs(decimal_part);          uint32_t fraction_decimal = std::abs(fraction)* ipow(10, FractionLength + 1);         uint8_t count = fraction_decimal / fraction_unit_halv;         count += count & 0x01;         count >>= 1;          if (count && sign == -1 && decimal_part == min_dec_abs)         {             throw std::invalid_argument("It won't fit our so few bits");         }          if (count == full_fraction)         {             decimal_part += 1;              auto decimal_part_signed = sign * decimal_part;              if (decimal_part_signed > max_dec || decimal_part_signed < min_dec)             {                 throw std::invalid_argument("It won't fit our so few bits");             }         }         else         {             val |= count;         }          val |= (decimal_part << FractionLength);          val *= sign;      }       FixedPoint operator + (const FixedPoint& r) const     {         return makeFx(val + r.val);     }      FixedPoint operator - (const FixedPoint& r) const     {         return makeFx(val - r.val);     }      FixedPoint operator - () const     {         return makeFx(-val);     }      FixedPoint operator * (const FixedPoint& r) const     {         uint16_t temp = val * r.val;         temp >>= (FractionLength - 1);         uint8_t unit = temp & 0x01;          return makeFx((temp >> 1) + unit);     }      FixedPoint operator / (const FixedPoint& r) const     {         uint16_t left = val;         left <<= (FractionLength + 1);         uint8_t temp = left / r.val;         uint8_t unit = temp & 0x01;          return makeFx((temp >> 1) + unit );     }      operator std::string() const     {         std::stringstream res;         uint8_t temp = val;         auto fraction = temp & fraction_mask;          if (sign_mask & temp)         {             res << '-';              temp = ~temp + 1;             fraction = temp & fraction_mask;         }          res << (temp >> FractionLength);           if (fraction)         {             res << '.' << std::setw(FractionLength) << fraction * fraction_unit;         }          return res.str();     }  private:      int8_t val;     static constexpr uint8_t decimal_lenght = CHAR_BIT - FractionLength;     static constexpr uint8_t max_dec = (1 << (decimal_lenght - 1)) - 1;     static constexpr int8_t  min_dec_abs = (1 << (decimal_lenght - 1));     static constexpr int8_t  min_dec = -min_dec_abs;     static constexpr uint32_t fraction_unit = ipow(10, FractionLength) / (1 << FractionLength);     static constexpr uint32_t fraction_unit_halv = ipow(10, FractionLength + 1) / (1 << (FractionLength + 1));     static constexpr uint8_t full_fraction = ipow(2, FractionLength);     static constexpr uint8_t sign_mask = 0x80;     static constexpr uint8_t fraction_mask = mask(FractionLength);     static constexpr uint8_t decimal_mask = 0xFF & ~FractionLength;       explicit FixedPoint(): val(0)     {     }          static FixedPoint makeFx(int8_t v)     {         FixedPoint fp;         fp.val = v;         return fp;     } };  template <uint8_t FractionLength> std::ostream& operator << (std::ostream& out, const FixedPoint<FractionLength>& number) {     out << std::string(number);      return out; }  template <uint8_t FractionLength> const FixedPoint<FractionLength> operator + (const FixedPoint<FractionLength>& l, int r) {     return l + FixedPoint<FractionLength>(r); }  template <uint8_t FractionLength> const FixedPoint<FractionLength> operator + (int l, const FixedPoint<FractionLength>& r) {     return r + FixedPoint<FractionLength>(l); }  template <uint8_t FractionLength> const FixedPoint<FractionLength> operator - (const FixedPoint<FractionLength>& l, int r) {     return l - FixedPoint<FractionLength>(r); }  template <uint8_t FractionLength> const FixedPoint<FractionLength> operator - (int l, const FixedPoint<FractionLength>& r) {     return r - FixedPoint<FractionLength>(l); }  template <uint8_t FractionLength> const FixedPoint<FractionLength> operator * (const FixedPoint<FractionLength>& l, int r) {     return l * FixedPoint<FractionLength>(r); }  template <uint8_t FractionLength> const FixedPoint<FractionLength> operator * (int l, const FixedPoint<FractionLength>& r) {     return r * FixedPoint<FractionLength>(l); }  template <uint8_t FractionLength> const FixedPoint<FractionLength> operator / (const FixedPoint<FractionLength>& l, int r) {     return l / FixedPoint<FractionLength>(r); }  template <uint8_t FractionLength> const FixedPoint<FractionLength> operator *= (FixedPoint<FractionLength>& l, const FixedPoint<FractionLength>& r) {     l = l * r;     return l; }  template <uint8_t FractionLength> const FixedPoint<FractionLength> operator += (FixedPoint<FractionLength>& l, const FixedPoint<FractionLength>& r) {     l = l + r;     return l; }  using FixedPoint_2 = FixedPoint<2>; using FixedPoint_4 = FixedPoint<4>; 

Пояснения:

• Самая длинная и сложная функция здесь – конструктор FixedPoint(double v), он нужен только для удобства тестирования – пропустите при первом чтении

• Конструктор FixedPoint(int decimal, unsigned int fraction = 0) – гораздо проще, но, в основном, он нужен для перегруженных арифметических операторов, где один из аргументов типа int

• Конструкторы контролируют переполнения поля val, но арифметические операторы – нет. Это осознанное решение: неудобно изначально работать с невалидными числами, которые обрезались и гадать почему вся программа работает неверно, в тоже время контролировать это всюду нет нужды, также как компилятор не контролирует это для встроенных типов

• Арифметические операторы вне класса – тривиально опираются на операторы опредленные в классе

• Сложение и вычитание – тривиально, нет разницы, что складывать, сотые части (четвертые) или целые

• Приватный конструктор и функция makeFx – a workaround, что б «заливать» в поле val, в некоторых операторах

Что такое творится в operator * и operator / ? Поясняю: если вы умножите 2 числа представляющих собой количество 1/4 вы получите число представляющее из себя количество 1/16 – поэтому сдвинем их вправо на 2 разряда, но, сдвига так, мы делаем грубое округление – учтём последний сдвинутый разряд,то есть получив число 0.10₂ до сдвига, без этого мы бы теряли его полность, а так делаем по стандартным правилам округления. С оператором деления немного другая история: при делении количесво 1/4 друг на друга результат уезжает вправо 2 разряда, но в коде я зарнее уношу делимое влево на 3 разряда – 3ий разряд опять же нужен для лучшего округления.

string operator() делает 3 вещи, выделяет целую часть и выводит её как целое, выделяет дробную часть и пересчитывает её в десятичнное число (число сотых) и выводит его как целое, последняя – опредление знака, делаем это через старший бит, строка ~temp + 1 тоже самое, что унарный минс, просто унарный минус странно использовать над безнаковым типом.

Приведу небольшой примерчик, где посмотрим как наш тип работает

template <typename T> T poly(T x) {     return (2*x +1)*x - 3; }  double x = 0.261799; FixedPoint_4 fx{x};  std::cout << poly(x) << ' ' << poly(fx) << std::endl;

Результат работы:

-2.60112 -2.6250

По-моему, неплохо, для типа созданного «на коленке!»

Итак, что можно сделать, что б убрать слово «игрушечный» из аттрибутов класса:

• использовать базовый тип побольше, лучше всего int32_t – промеуточные результаты будут в int64_t не придётся придумывать какое-то «длинное» умножение

• перегрузить больше операторов

• покрыть тестами