Уменьшить объем памяти при создании класса BigInt

Question

Сейчас я работаю над концепцией и пишу псевдокод, когда задаю этот вопрос. Я думаю о создании довольно простого и простого в использовании интерфейса класса для представления BigInts. Я подумываю о создании пары простых структур с базовыми свойствами и членами, которые будет использовать класс BigInt. Например, вместо того, чтобы класс BigInt обрабатывал отрицательные значения напрямую, он содержал бы структуру Sign, и эта структура в основном содержала бы либо значение 0 или 1, либо в основном логический тип для указания, является ли этот BigInt положительным или отрицательным. После создания я намерен заставить класс генерировать позитив по умолчанию. Я также хотел бы иметь структуру, которая представляет цифры, где есть два варианта. Первый вариант имеет цифры 0-9, а второй, который наследует оригинал, но также включает в себя AF. Таким образом, класс, который будет классом шаблона, но только когда-либо будет иметь два допустимых типа, будет поддерживать использование десятичного и шестнадцатеричного типов. Все математические операторы будут определены вне класса, и в зависимости от его предполагаемого типа он будет вызывать и выполнять соответствующую версию функции. Однако шестнадцатеричная часть все еще является концептуальной, поскольку я хотел бы сначала запустить и запустить десятичную версию. Эти вспомогательные классы могут выглядеть примерно так:

class Sign {
private:
    bool isNegative_ { false };
    char sign_;
public:
    Sign() : isNegative_( false ) {
        sign_ = '+';
    }
    Sign( const bool isNegative ) : isNegative_( isNegative ) { 
        sign_ = isNegative_ ? '-' : '+';
    }; 

    Sign( const char sign ) {
        if ( sign == '+' || sign == '\0' || sign == ' ' ) {
            isNegative_ = false;
        } else if ( sign == '-' ) {
            isNegative_ = true;
        } else {
            // throw error improper character.
        }
    }

    bool isPostive() const { return !isNegative_; }
    bool isNegative() const { return !isNegative; }

    char sign() const { return sign_; }
    char negate() {
        isNegative_ = !isNegative_;
        sign_ = isNegative_ ? '+' : '-'; 
        return sign_;         
    }        
};

// NST = NumberSystemType
class enum NST { Decimal = 10, Hexadecimal = 16 };

template<class NT> // NT = NumberType
class Digit {
private:
    NST nst_; // determines if Decimal or Hexadecimal       
};

// Specialization for Decimal
template<NST::Decimal> // Should be same as template<10>
class Digit {
    // would like some way to define 4 bits to represent 0-9; prefer not to
    // use bitfields, but I think a char or unsigned char would be wasting 
    // memory using twice as much for what is needed. Not sure what to do here...
    // maybe std::bitset<>...


};

template<NST::Hexadecimal> // Should be same as template<16>
class Digit : public Digit<Decimal> { // Also inherits all of The first specialization.
    // same as above only needs 4 bits to represent values form 0-F
    // A half char would be excellent but does not exist in c++... and most
    // programming language's types.
    // still thinking of maybe std::bitset<>...

};

Основное различие между ними состоит в том, что первая специализация допускает только значения цифр от 0-9 и сами цифры 0-9, где вторая не имеет такого ограничения, но также позволяет использовать значения af и / AF в любом случае. Я также могу включить const char * для обозначения шестнадцатеричного префикса 0x это будет добавлено к любому содержанию значения для отображения.

Мне нравится такой подход к проектированию, поскольку я хотел бы сохранить фактические арифметические функции и операторы класса BigInt в качестве отдельных шаблонов функций, поскольку класс BigInt может поддерживать как специализированные типы шаблонов Decimal, так и Hexadecimal. Также в будущем, если все пойдет правильно, я бы также хотел добавить поддержку для работы с комплексными числами.

Класс BigInt будет выглядеть так:

template<class NT>
BigInt {
private:
    Sign sign_;
    Digit<NT> carryDigit_;
    std::vector<Digit<NT>> value_;

    // May contain some functions such as setters and getters only
    // Do not want the class to be modifying itself except for assignment only.
};

И, как указано выше, это будет также специализировано для десятичных и шестнадцатеричных типов, однако, если кто-то создает экземпляр BigInt<> myBigInt, по умолчанию это значение должно быть равно десятичному!

Для данных, которые содержатся в векторе. Я хотел бы хранить цифры в обратном порядке того, что читает. Так что, если их число 345698 во внутреннем векторе BigInt он будет храниться как 896543, Причина этого заключается в том, что когда мы выполняем арифметические операции в математике, мы работаем от наименее значимого до самого значимого, начиная с правой части слева от десятичной точки, что не имеет значения, поскольку это класс только с BigInt, и мы работаем по-своему левый. Однако, если мы сохраним каждую цифру, которая может быть только 0-9 в каждом элементе вектора вышеупомянутого класса в правильном порядке, и мы используем внешнюю функцию operator+(), это будет сложно сделать для одного BigInt для другого... пример:

Basic Arithmetic R - L    | Vector storing standard
12345                       <1,2,3,4,5>
+ 678                       <6,7,8>
------  
13023

Здесь индексы <5> & <8> не совпадают, поэтому сложно понять, как добавить значение с несколькими цифрами к одному со многими. Мой подход заключается в том, что если мы будем хранить число в обратном порядке:

                         | Vector stored in reverse
                           <5,4,3,2,1>
                           <6,7,8>

Тогда сложение становится простым! Все, что нам нужно сделать, это добавить каждую цифру из обоих векторов BigInt к одному и тому же значению индекса. И мы используем цифру переноса для переноса на следующее поле. Результирующий BigInt вернется с размером, который по крайней мере равен или больше, чем самый большой из двух BigInts. Если значение carryDigit имеет значение, то операция сложения на следующей итерации будет включать 3 сложения вместо двух. Теперь при получении BigInt для отображения мы можем вернуть либо вектор>, за исключением того, что когда пользователь получает его, это не "BigInt", это вектор цифр, и он также находится в правильном порядке. Это может даже быть возвращено строковым представлением. Этот класс может быть создан с помощью вектора>, и он изменит порядок, когда он сохранит его внутри.

Это общая концепция моего класса BigInt, мне просто интересно, если это хороший план дизайна, если он будет считаться эффективным, и я предполагаю, что главный вопрос, который у меня есть, о том, что использовать для хранения фактических цифр в пределах Класс Digit... будет std::bitset<> было бы целесообразно сохранить отпечаток памяти или было бы лучше использовать char и не беспокоиться о дополнительном пространстве с простотой реализации?

Answer 1

-Обновить-

Хорошо, я взял несколько советов, и это то, что я до сих пор. Я еще не включил концепцию хранения значений в обратном порядке, что не должно быть слишком сложным. В настоящее время я удалил все внешние классы, и моя подпись класса BigInt выглядит следующим образом:

class BigInt {
private:
    short sign_;
    uint32_t carry_{0};
    std::vector<uint32_t> value_;

public:
    BigInt() : sign_( 0 ) {}

    BigInt(  const uint32_t* value, const std::size_t arraySize, short sign = 0 ) : 
    sign_( sign ) {
        if( sign_ != 0 ) sign_ = -1;
        value_.insert( value_.end(), &value[0], &value[arraySize] );
        std::reverse( value_.begin(), value_.end() );
    }

    BigInt( const std::vector<uint32_t>& value, short sign = 0 ) : 
    sign_( sign ) {
        if( sign_ != 0 ) sign_ = -1;
        value_.insert( value_.end(), value.begin(), value.end() );
        std::reverse( value_.begin(), value_.end() );
    }

    BigInt( std::initializer_list<uint32_t> values, short sign = 0 ) : 
    sign_( sign ) {
        if( sign_ != 0  ) sign_ = -1;
        value_.insert( value_.end(), values.begin(), values.end() );
        std::reverse( value_.begin(), value_.end() );
    }

    std::vector<uint32_t> operator()() {
        //value_.push_back( static_cast<uint32_t>( sign_ ) ); // causes negative to be pushed into container multiple times...
        std::reverse( value_.begin(), value_.end() );
        return value_;
    }
};

Я думаю, что это хорошее начало: есть несколько способов создать тот, который дает вызывающей стороне некоторую гибкость, так как вы можете создать BigInt с указателем, массивом, вектором или даже списком инициализатора. Поначалу может показаться нелогичным иметь знак в конце конструктора, но я хочу, чтобы значение знака было параметром по умолчанию, когда значение положительное. Если что-то кроме 0 передается для значения знака, он будет преобразован в -1, Еще немного времени, и у меня будет полная сигнатура этого класса, после чего я смогу перейти к операторам, которые будут работать над ним.

В приведенном выше коде есть некоторые незначительные подводные камни, но я постоянно над ними работаю.

Answer 2

Наименьшая адресуемая единица памяти в C++ - это байт, а байт составляет не менее 8 бит (и обычно ровно 8 бит). Так что ваша идея действительно тратит впустую память.

Я также подозреваю, что вы не знакомы с математикой. То, что вы называете "NumberSystemType", обычно называется базой. Итак, мы говорим о Base-10 или Base-16.

Теперь Base-10 полезен только для потребления человеком, и, следовательно, бессмысленно для такого рода значимых вещей. В любом случае, люди не могут иметь дело с числами, которые имеют более 20 десятичных цифр. Итак, выберите базу, которая будет полезна для компьютеров. И выбрать один. Нет необходимости поддерживать несколько баз. Как отмечает Пэдди, база 2^32 является вполне разумной базой для компьютеров.