6
\$\begingroup\$

I am working on an arbitrary math lib. Below is a class I use to handle the binary mathematics needed for the library.

The class is quite simple. All it does is wrap around a vector of any unsigned integral type designated. Which in turn support binary operations on individual bits, or whole register words. Basic binary mathematics is supported. That way other classes using this to implement general arithmetic can be checked against this if needed for testing or troubleshooting purposes.

One specific area of concern is comparison using a float, for a return type. I use it to support partial ordering later in the project. Should this be updated to the C++20 way of handling it, or be left as is for support in other project not using C++20?

Any feedback is welcomed! I am trying to identify any blind spots I have in my coding abilities.

#include <bitset>
#include <limits>
#include <vector>

#include "../support_files/Type_Defines.h"

namespace Olly {

    /********************************************************************************************/
    //
    //                                 'Binary_Register' class
    //
    //        The Binary_Register class implements a series of binary registers sized to
    //        the integral type passed during to the template at definition.
    //
    //        Support for all of the binary operation is provides, along with binary
    //        based mathematical operations.  The implementation is little endian.
    //
    /********************************************************************************************/

    template<typename N>
    class Binary_Register {

        static_assert(std::numeric_limits<N>::is_integer, 
            "The Binary_Register template argument T must be an unsigned integral.");
        static_assert(std::numeric_limits<N>::is_signed ? false : true, 
            "The Binary_Register template argument T must be an unsigned integral.");

    public:
        using Word     = N;
        using Register = std::vector<N>;

        static const N           MASK = ~N(0);
        static const std::size_t BITS = std::numeric_limits<N>::digits;

        Binary_Register();
        Binary_Register(const Text& value, Text base = "10");
        Binary_Register(const std::size_t& size, Word value);
        explicit
        Binary_Register(const std::size_t& size);
        virtual ~Binary_Register();

        bool              is() const;                             // bool conversion.
        bool             all() const;                             // bool test for all bits being set to 1.
        std::size_t    count() const;                             // The count of bits set to 1.
        std::size_t lead_bit() const;                             // Return the lead bit.
        std::size_t last_bit() const;                             // Return the last bit.
        Word        lead_reg() const;                             // Return the leading register.
        Word        last_reg() const;                             // Return the last register.

        bool at_bit(std::size_t index) const;                     // Return the value of a bit at the index.

        Word& at_reg(std::size_t index);                          // Return the word at the indexed register.
        Word  at_reg(std::size_t index) const;

        Text to_string()       const;                             // Return a string representation at radix 10.
        Text to_string(N base) const;                             // Return a string representation at radix 'base'.
        void to_string(Text_Stream& stream) const;                // Send a string representation to a stream_type.

        std::size_t size_bits() const;                            // Get the total size in bits of the register.
        std::size_t size_regs() const;                            // Get the total size of words in the register.

        Binary_Register& resize_regs(std::size_t size);           // Resize the register to 'size' number of elements. 
        Binary_Register& resize_regs(std::size_t size, Word n);

        Binary_Register& set();                                   // Set all bits to true.
        Binary_Register& set(std::size_t index);                  // Set a bit at 'index' to true.

        Binary_Register& reset();                                 // Set all bits to false.
        Binary_Register& reset(std::size_t index);                // Set a bit at 'index' to false.

        Binary_Register& flip();                                  // Flip the truth of every bit in the register.
        Binary_Register& flip(std::size_t index);                 // Flip the truth of a bit at 'index'.

        bool operator==(const Binary_Register& b) const;
        bool operator!=(const Binary_Register& b) const;
        bool operator< (const Binary_Register& b) const;
        bool operator> (const Binary_Register& b) const;
        bool operator<=(const Binary_Register& b) const;
        bool operator>=(const Binary_Register& b) const;

        Binary_Register& operator&=(const Binary_Register& other);
        Binary_Register& operator|=(const Binary_Register& other);
        Binary_Register& operator^=(const Binary_Register& other);

        Binary_Register& operator<<=(std::size_t index);
        Binary_Register& operator>>=(std::size_t index);

        Binary_Register operator&(const Binary_Register& b) const;
        Binary_Register operator|(const Binary_Register& b) const;
        Binary_Register operator^(const Binary_Register& b) const;
        Binary_Register operator~() const;

        Binary_Register operator<<(std::size_t index) const;
        Binary_Register operator>>(std::size_t index) const;

        Binary_Register& operator+=(const Binary_Register& other);
        Binary_Register& operator-=(const Binary_Register& other);
        Binary_Register& operator*=(const Binary_Register& other);
        Binary_Register& operator/=(const Binary_Register& other);
        Binary_Register& operator%=(const Binary_Register& other);

        Binary_Register operator+(const Binary_Register& b) const;
        Binary_Register operator-(const Binary_Register& b) const;
        Binary_Register operator*(const Binary_Register& b) const;
        Binary_Register operator/(const Binary_Register& b) const;
        Binary_Register operator%(const Binary_Register& b) const;

        Binary_Register& operator++();
        Binary_Register  operator++(int);

        Binary_Register& operator--();
        Binary_Register  operator--(int);

        template<typename I>
        N to_integral() const;                // Cast the register to an integral of type T.

        Binary_Register  bin_comp() const;    // Return the binary compliment of the register.

        // Get both the qotient and the remainder of the regester divided by 'other'.
        void div_rem(Binary_Register& other, Binary_Register& qot, Binary_Register& rem) const;

        float compare(const Binary_Register& other) const;

        Binary_Register& trim();    // Remove all trailing zeros, from the register.  
                                    // But leave atleast one register, even if a value of zero.

    private:
        typedef std::bitset<BITS>           single_prc_bitset;
        typedef std::bitset<BITS + BITS>    double_prc_bitset;

        static const N ONE = 1;

        Register _reg;

        void get_shift_index(std::size_t& index, std::size_t& reg_index, std::size_t& bit_index) const;

        void divide_remainder(const Binary_Register& x, Binary_Register y, Binary_Register& q, Binary_Register& r) const;

        Text get_string(N base) const;

        void  left_shift_bits(std::size_t& word_index, std::size_t& bit_index);
        void right_shift_bits(std::size_t& word_index, std::size_t& bit_index);
    };

    /********************************************************************************************/
    //
    //                              'Binary_Register' implimentation
    //
    /********************************************************************************************/

    template<typename N>
    inline Binary_Register<N>::Binary_Register() : _reg(1, 0) {
    }

    template<typename N>
    inline Binary_Register<N>::Binary_Register(const std::size_t& size) : _reg((size > 0 ? size : 1), 0) {
    }

    template<typename N>
    inline Binary_Register<N>::Binary_Register(const std::size_t& size, Word value) : _reg((size > 0 ? size : 1), value) {
    }

    template<typename N>
    inline Binary_Register<N>::Binary_Register(const Text& value, Text base) : _reg(1, 0) {

        N base_radix = to<N>(base);                // Get the base radix to use.

        Binary_Register<N> radix(1, base_radix);   // Define a Binary_Register to act as the radix.

        for (auto i : value) {                     // Loop through each digit and add it to the Binary_Register.

            Text digit_str = "";

            digit_str.push_back(i);

            N n = to<N>(digit_str);

            if (n < base_radix) {
                Binary_Register<N> digit(1, n);

                operator*=(radix);
                operator+=(digit);
            }
        }
    }

    template<typename N>
    inline Binary_Register<N>::~Binary_Register() {
    }

    template<typename N>
    inline bool Binary_Register<N>::is() const {

        for (auto i : _reg) {

            if (i) {
                return true;
            }
        }
        return false;
    }

    template<typename N>
    inline bool Binary_Register<N>::all() const {

        for (auto i : _reg) {

            if (i != MASK) {
                return false;
            }
        }
        return true;
    }

    template<typename N>
    inline std::size_t Binary_Register<N>::count() const {

        std::size_t count = 0;

        for (const auto i : _reg) {

            auto n = i;

            while (n > 0) {

                if (n & 1) {
                    count += 1;
                }
                n >>= 1;
            }
        }

        return count;
    }

    template<typename N>
    inline std::size_t Binary_Register<N>::lead_bit() const {

        std::size_t word_index = _reg.size();

        Word mask = (ONE << (BITS - ONE));

        for (auto i = _reg.crbegin(); i != _reg.crend(); ++i) {
            word_index -= 1;

            auto a = *i;

            std::size_t bit_index = BITS;

            while (a) {

                if (a & mask) {
                    return bit_index + (word_index * BITS);
                }
                a <<= 1;
                bit_index -= 1;
            }
        }

        return 0;
    }

    template<typename N>
    inline std::size_t Binary_Register<N>::last_bit() const {

        std::size_t word_index = 0;

        Word mask = 1;

        for (auto i = _reg.cbegin(); i != _reg.cend(); ++i) {

            auto a = *i;

            std::size_t bit_index = 1;

            while (a) {

                if (a & mask) {
                    return bit_index + (word_index * BITS);
                }
                a >>= 1;
                bit_index += 1;
            }
            word_index += 1;
        }

        return 0;
    }

    template<typename N>
    inline N Binary_Register<N>::lead_reg() const {

        if (_reg.empty()) {
            return N(0);
        }

        return _reg.back();
    }

    template<typename N>
    inline N Binary_Register<N>::last_reg() const {

        if (_reg.empty()) {
            return N(0);
        }

        return _reg.front();
    }

    template<typename N>
    inline bool Binary_Register<N>::at_bit(std::size_t index) const {

        std::size_t reg_index, bit_index;
        get_shift_index(index, reg_index, bit_index);

        if (reg_index < _reg.size()) {

            return _reg[reg_index] & (ONE << (bit_index - ONE));
        }

        return false;
    }

    template<typename N>
    inline N& Binary_Register<N>::at_reg(std::size_t index) {

        while (index >= _reg.size()) {

            _reg.push_back(0);
        }

        return _reg[index];
    }

    template<typename N>
    inline N Binary_Register<N>::at_reg(std::size_t index) const {

        if (index < _reg.size()) {

            return _reg[index];
        }

        return Word(0);
    }

    template<typename N>
    inline Text Binary_Register<N>::to_string() const {

        return to_string(10);
    }

    template<typename N>
    inline Text Binary_Register<N>::to_string(N base) const {

        if (base > 360) {
            return "Radix must be between 0 and 360.";
        }

        if (base == 0) {
            Text_Stream stream;

            to_string(stream);

            return stream.str();
        }

        if (!is()) {
            return "0";
        }

        return get_string(base);
    }

    template<typename N>
    inline void Binary_Register<N>::to_string(Text_Stream& stream) const {

        std::size_t i = _reg.size();

        while (i-- > 1) {
            stream << "word[" << i << "] = " << single_prc_bitset(_reg[i]).to_string() << "\n";
        }
        stream << "word[" << 0 << "] = " << single_prc_bitset(_reg[i]).to_string();
    }

    template<typename N>
    inline std::size_t Binary_Register<N>::size_bits() const {
        return _reg.size() * BITS;
    }

    template<typename N>
    inline std::size_t Binary_Register<N>::size_regs() const {
        return _reg.size();
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::resize_regs(std::size_t size) {
        
        _reg.resize(size);

        return *this;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::resize_regs(std::size_t size, Word n) {

        _reg.resize(size, n);

        return *this;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::set() {

        for (auto i = _reg.begin(); i != _reg.end(); ++i) {
            *i = MASK;
        }

        return *this;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::set(std::size_t index) {

        std::size_t reg_index, bit_index;
        get_shift_index(index, reg_index, bit_index);

        while (reg_index >= _reg.size()) {

            _reg.push_back(0);
        }

        _reg[reg_index] |= (ONE << (bit_index - ONE));

        return *this;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::reset() {

        for (std::size_t i = 0, end = _reg.size(); i < end; i += 1) {
            _reg[i] = Word(0);
        }

        return *this;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::reset(std::size_t index) {

        std::size_t reg_index, bit_index;
        get_shift_index(index, reg_index, bit_index);

        while (reg_index >= _reg.size()) {

            _reg.push_back(0);
        }

        _reg[reg_index] &= ~(1 << (bit_index - 1));

        return *this;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::flip() {

        for (std::size_t i = 0, end = _reg.size(); i < end; i += 1) {
            _reg[i] = ~_reg[i];
        }

        return *this;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::flip(std::size_t index) {

        std::size_t reg_index, bit_index;
        get_shift_index(index, reg_index, bit_index);

        while (reg_index >= _reg.size()) {

            _reg.push_back(0);
        }

        _reg[reg_index] ^= (1 << (bit_index - 1));

        return *this;
    }

    template<typename N>
    inline bool Binary_Register<N>::operator==(const Binary_Register<N>& b) const {
        return compare(b) == 0;
    }

    template<typename N>
    inline bool Binary_Register<N>::operator!=(const Binary_Register<N>& b) const {
        return compare(b) != 0;
    }

    template<typename N>
    inline bool Binary_Register<N>::operator<(const Binary_Register<N>& b) const {
        return compare(b) < 0;
    }

    template<typename N>
    inline bool Binary_Register<N>::operator>(const Binary_Register<N>& b) const {
        return compare(b) > 0;
    }

    template<typename N>
    inline bool Binary_Register<N>::operator<=(const Binary_Register<N>& b) const {
        return compare(b) <= 0;
    }

    template<typename N>
    inline bool Binary_Register<N>::operator>=(const Binary_Register<N>& b) const {
        return compare(b) >= 0;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::operator&=(const Binary_Register<N>& other) {

        while (_reg.size() < other._reg.size()) {

            _reg.push_back(0);
        }

        for (std::size_t i = 0, end = _reg.size(); i < end; i += 1) {
            _reg[i] &= other.at_reg(i);
        }

        return *this;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::operator|=(const Binary_Register<N>& other) {

        while (_reg.size() < other._reg.size()) {

            _reg.push_back(0);
        }

        for (std::size_t i = 0, end = _reg.size(); i < end; i += 1) {
            _reg[i] |= other.at_reg(i);
        }

        return *this;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::operator^=(const Binary_Register<N>& other) {

        while (_reg.size() < other._reg.size()) {

            _reg.push_back(0);
        }

        for (std::size_t i = 0, end = _reg.size(); i < end; i += 1) {
            _reg[i] ^= other.at_reg(i);
        }

        return *this;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::operator<<=(std::size_t index) {

        std::size_t word_index, bit_index;

        get_shift_index(index, word_index, bit_index);

        if (word_index) {
            _reg.insert(_reg.begin(), word_index, 0);
        }

        if (bit_index) {

            left_shift_bits(word_index, bit_index);
        }

        return *this;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::operator>>=(std::size_t index) {

        std::size_t word_index, bit_index;

        get_shift_index(index, word_index, bit_index);

        if (word_index) {

            if (word_index < _reg.size()) {

                _reg.erase(_reg.begin(), _reg.begin() + word_index);
            }
            else {
                for (auto i = _reg.begin(), end = _reg.end(); i != end; ++i) {
                    *i = 0;
                }

                return *this;
            }
        }

        if (bit_index) {

            right_shift_bits(word_index, bit_index);
        }

        return *this;
    }

    template<typename N>
    inline Binary_Register<N> Binary_Register<N>::operator&(const Binary_Register<N>& b) const {

        Binary_Register<N> a(*this);

        a &= b;

        return a;
    }

    template<typename N>
    inline Binary_Register<N> Binary_Register<N>::operator|(const Binary_Register<N>& b) const {

        Binary_Register<N> a(*this);

        a |= b;

        return a;
    }

    template<typename N>
    inline Binary_Register<N> Binary_Register<N>::operator^(const Binary_Register<N>& b) const {

        Binary_Register<N> a(*this);

        a ^= b;

        return a;
    }

    template<typename N>
    inline Binary_Register<N> Binary_Register<N>::operator~() const {

        Binary_Register<N> a = *this;

        for (std::size_t i = 0, end = a._reg.size(); i < end; i += 1) {
            a._reg[i] = ~a._reg[i];
        }

        return a;
    }

    template<typename N>
    inline Binary_Register<N> Binary_Register<N>::operator<<(std::size_t index) const {

        Binary_Register<N> a(*this);

        a <<= index;

        return a;
    }

    template<typename N>
    inline Binary_Register<N> Binary_Register<N>::operator>>(std::size_t index) const {

        Binary_Register<N> a(*this);

        a >>= index;

        return a;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::operator+=(const Binary_Register<N>& other) {

        Binary_Register<N> b(other);
        Binary_Register<N> c;

        while (b.is()) {

            c = (*this & b) << 1;

            *this ^= b;

            b = c;
        }

        return *this;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::operator-=(const Binary_Register<N>& other) {

        if (other >= *this) {
            return reset();
        }

        Binary_Register<N> b = other;

        while (b.size_regs() < size_regs()) {
            b._reg.push_back(0);
        }

        b = b.bin_comp();

        b._reg.push_back(0);  // Add a word to handle the two's compliment overflow.

        *this += b;

        _reg.pop_back(); // Get rid of the two's compliment overflow.

        return *this;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::operator*=(const Binary_Register<N>& other) {

        *this = *this * other;

        return *this;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::operator/=(const Binary_Register<N>& other) {

        *this = *this / other;

        return *this;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::operator%=(const Binary_Register<N>& other) {

        *this = *this % other;

        return *this;
    }

    template<typename N>
    inline Binary_Register<N> Binary_Register<N>::operator+(const Binary_Register<N>& b) const {

        Binary_Register<N> a = *this;

        a += b;

        return a;
    }

    template<typename N>
    inline Binary_Register<N> Binary_Register<N>::operator-(const Binary_Register<N>& b) const {

        Binary_Register<N> a = *this;

        a -= b;

        return a;
    }

    template<typename N>
    inline Binary_Register<N> Binary_Register<N>::operator*(const Binary_Register<N>& b) const {

        std::size_t count = 0;

        Binary_Register<N> x;
        Binary_Register<N> y = b;

        while (y.is()) {

            if (y.at_bit(1)) {
                x += (*this << count);
            }

            count += 1;
            y >>= 1;
        }

        return x;
    }

    template<typename N>
    inline Binary_Register<N> Binary_Register<N>::operator/(const Binary_Register<N>& b) const {

        Binary_Register<N> q;
        Binary_Register<N> r = *this;

        divide_remainder(*this, b, q, r);

        return q;
    }

    template<typename N>
    inline Binary_Register<N> Binary_Register<N>::operator%(const Binary_Register<N>& b) const {

        Binary_Register<N> q;
        Binary_Register<N> r = *this;

        divide_remainder(*this, b, q, r);

        return r;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::operator++() {

        Binary_Register<N> one(1, 1);

        operator+=(one);

        return *this;
    }

    template<typename N>
    inline Binary_Register<N> Binary_Register<N>::operator++(int) {

        Binary_Register<N> a(*this);

        operator++();

        return a;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::operator--() {

        Binary_Register<N> one(1, 1);

        operator-=(one);

        return *this;
    }

    template<typename N>
    inline Binary_Register<N> Binary_Register<N>::operator--(int) {

        Binary_Register<N> a(*this);

        operator--();

        return a;
    }

    template<typename N>
    inline Binary_Register<N> Binary_Register<N>::bin_comp() const {

        Binary_Register<N> a = ~*this;
        Binary_Register<N> one(1, 1);

        a += one;

        return a;
    }

    template<typename N>
    inline void Binary_Register<N>::div_rem(Binary_Register& other, Binary_Register& qot, Binary_Register& rem) const {

        rem = *this;

        divide_remainder(*this, other, qot, rem);
    }

    template<typename N>
    inline float Binary_Register<N>::compare(const Binary_Register<N>& other) const {

        std::size_t i = size_regs() > other.size_regs() ? size_regs() : other.size_regs();

        while (i --> 0) {

            auto x = at_reg(i);
            auto y = other.at_reg(i);

            if (x > y) {
                return 1.0;
            }

            if (x < y) {
                return -1.0;
            }
        }

        return 0.0;
    }

    template<typename N>
    inline Binary_Register<N>& Binary_Register<N>::trim() {

        while (!_reg.empty() && _reg.back() == 0) {

            _reg.pop_back();
        }

        if (_reg.empty()) {

            _reg.push_back(0);
        }

        return *this;
    }

    template<typename N>
    inline void Binary_Register<N>::get_shift_index(std::size_t& index, std::size_t& reg_index, std::size_t& bit_index) const {

        if (index) {

            if (index >= BITS) {

                reg_index = index / BITS;
                bit_index = index % BITS;

                if (!bit_index) {
                    --reg_index;
                    bit_index = BITS;
                }

                return;
            }

            reg_index = 0;
            bit_index = index;

            return;
        }

        reg_index = 0;
        bit_index = 0;
    }

    template<typename N>
    inline void Binary_Register<N>::divide_remainder(const Binary_Register<N>& x, Binary_Register<N> y, Binary_Register<N>& q, Binary_Register<N>& r) const {

        if (!y.is() || !x.is() || x < y) {
            return;
        }

        std::size_t lead_x = x.lead_bit();
        std::size_t lead_y = y.lead_bit();

        std::size_t bit_dif = (lead_x - lead_y);

        y <<= bit_dif;

        bit_dif += 2;

        while (bit_dif-- > 1) {

            if (r >= y) {
                q.set(bit_dif);
                r -= y;
            }
            y >>= 1;
        }
    }

    template<typename N>
    inline Text Binary_Register<N>::get_string(N base) const {

        Binary_Register<N> radix(1, base);
        Binary_Register<N> n = *this;

        Text_Stream stream;

        while (n.is()) {

            Binary_Register<N> q;
            Binary_Register<N> r = n;

            divide_remainder(n, radix, q, r);

            n = q;

            stream << r.at_reg(0);
        }

        Text res = stream.str();
        std::reverse(res.begin(), res.end());

        return res;
    }

    template<typename N>
    inline void Binary_Register<N>::left_shift_bits(std::size_t& word_index, std::size_t& bit_index) {

        std::size_t i = _reg.size();

        _reg.push_back(0);

        auto bit_mask = double_prc_bitset(MASK);

        while (i-- > 0) {

            auto buffer = double_prc_bitset();
            buffer |= double_prc_bitset(_reg[i]);

            buffer <<= bit_index;

            _reg[i] = static_cast<N>((buffer & bit_mask).to_ullong());

            buffer >>= BITS;
            buffer |= double_prc_bitset(_reg[i + 1]);

            _reg[i + 1] = static_cast<N>(buffer.to_ullong());
        }

        if (_reg.back() == 0) {
            _reg.pop_back();
        }
    }

    template<typename N>
    inline void Binary_Register<N>::right_shift_bits(std::size_t& word_index, std::size_t& bit_index) {

        bool pop_back = word_index ? false : true;

        if (word_index) {
            word_index -= 1;
        }
        _reg.push_back(0);

        auto inv_index = BITS - bit_index;

        std::size_t end = (_reg.size() - 1);

        auto bit_mask = double_prc_bitset(MASK);

        for (std::size_t i = 0; i < end; i += 1) {

            auto buffer = double_prc_bitset();
            buffer |= double_prc_bitset(_reg[i + 1]);

            buffer <<= inv_index;

            _reg[i] >>= bit_index;
            _reg[i] |= static_cast<N>((buffer & bit_mask).to_ullong());
        }
        _reg[end] >>= bit_index;


        while (word_index-- > 0) {
            _reg.push_back(0);
        }

        if (pop_back) {
            _reg.pop_back();
        }
    }

    template<typename N>
    template<typename I>
    inline N Binary_Register<N>::to_integral() const {
        static_assert(std::numeric_limits<I>::is_integer, "Integral required.");

        if (!_reg.empty()) {

            auto bits_of_I = std::numeric_limits<I>::digits;

            if (bits_of_I >= BITS && !_reg.empty()) {

                return I(_reg.front());
            }

            I n = 0;

            for (int i = BITS / bits_of_I; i >= 0; i -= 1) {

                n <<= bits_of_I;
                n += at_reg(i);
            }

            return static_cast<N>(n);
        }

        return I(0);
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ Great first question! Would also recommend section 4.3 (Multiple-Precision Arithmetic) of Knuth’s The Art of Computer Programming, vol. 2: Seminumerical Algorithims. \$\endgroup\$
    – Davislor
    Apr 11, 2023 at 22:57
  • \$\begingroup\$ @Davislor, I tried getting a copy of that, but the cost at the time was too much. What I was able to find was all written in assembly, which was really hard to comprehend. Found the same thing with a book by Paul Zimmerman. In that instance it was I just couldn't read the math or the sudo code. That was why I started working on this. I wanted to make a library, which while not the fastest, would be readable and understandable by any student, regardless of skill level. \$\endgroup\$
    – StormCrow
    Apr 12, 2023 at 12:59
  • \$\begingroup\$ Yep, Donald Knuth invented his own imaginary machine language to write all his algorithms in. (One that looks much more like the computers of the ’70s than today.) He talks in the introduction about why he did it that way. There’s definitely a niche for demo code in C++. \$\endgroup\$
    – Davislor
    Apr 12, 2023 at 16:13
  • \$\begingroup\$ But a nearby library ought to have a copy. \$\endgroup\$
    – Davislor
    Apr 12, 2023 at 16:15

1 Answer 1

5
\$\begingroup\$

Does this Need to be a Template Class?

You tell us that it can operate on vectors of any unsigned integral type, but is there any use case other than the native word size as an element type? (Which is normally size_t, although maybe you want to write it as using word_t = std::size_t just in case you need to define it differently for some weird target.)

You don’t actually need a double-width word to test for unsigned carry, because you can just compare the result to either operand. For multiplication, the only completely standard and portable way would be to convert 32-bit operands to unsigned long long so that all the bits of the product will fit, but some architectures have extensions you can use to do this faster.

If you really do need the template parameter, you can, as an alternative to the static_assert statements you have now, specify it as the C++20 concept template<std::unsigned_integral N>. It’s also one of several surprising names in the code. I would have expected a N template parameter to be an integral constant, not an integral type. If you do keep it, consider a name like Word.

Use a Spaceship Operator

You could use the code from your compare function to implement <=> and cut down on a lot of the boilerplate for comparisons. You probably still want operator== and operator!= declared separately, but I believe those can just be default.

Follow the Rule of Five

Or actually, six. This type wraps a std::vector, which is much more efficient to move than to copy, so it should have a copy constructor, a move constructor (which can both be default) and a swap operation.

Rvalue Reference Overloads Would be More Efficient

Currently, all or nearly all the operators that return temporaries make a copy of the first operand and update that in place. However, if either operand is moveable (Binary_Register&& instead of const Binary_Register&), you can optimize out the copy. Since nearly all the operations are commutative, modulo an inversion here or there, you can do this if either operand is moveable.

The gain is especially noticeable in an expression such as a = w + x + y + z;. The current operation would need to make four copies, but adding an overload for && on the left operand would reduce that to one: w would need to be copied, in the first addition, but then every other sum would have an xvalue (the temporary returned by the previous addition) as its left operand, so it could keep updating that in place, then move the result to a.

Do You Really Want Two’s-Complement?

The main motivation for using it in the CPU is that, for fixed-width unsigned types, the CPU can use the same logic for signed and unsigned addition and subtraction. However, here, you don’t want to do both signed and unsigned addition and subtraction. You end up making subtraction more complex by copying and inverting the second operand, and likewise the other arithmetic.

The classic solution is therefore to use a sign-and-magnitude representation for this purpose.

Some of the Individual Functions Can be Optimized

To give just one example, &= pads the destination operand to the length of the source with a loop that calls push_back(0) on the vector of words, then does element-wise &=.

First, when you know the total size, it’s much more efficient to pad with zeroes by calling resize once than by calling push_back repeatedly.

But second, bitwise and where one of the operands is 0 will always return 0, so you could have done the &= loop only up to the lesser of the two operands’ sizes, and then either zero-extended the left operand or zeroed out its remaining words.

Minor Cosmetic Suggetions

Either PascalCase or snake_case is much more common for class names than Whatever_This_Is. I’d recommend you pick one of the first two.

Avoid misleading whitespace such as while (i --> 0). That one does kind of work, but --> is not an operator, and is easy to confuse for ->, which is.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you very much for the feed back! Let me work through your suggestions. I will update the code as I implement them. \$\endgroup\$
    – StormCrow
    Apr 11, 2023 at 18:28
  • \$\begingroup\$ @StormCrow Hope it was helpful. Since you’re new, you should review the rules of the site and be aware (if you’re not already) that we discourage askers from editing their questions in response to answers. The preferred way to get feedback on a revision is to turn it into a follow-up question. \$\endgroup\$
    – Davislor
    Apr 11, 2023 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.