Как преобразовать строку в целое число произвольной длины
Я работаю над проектом по реализации арифметики с множественной точностью в C ++. Я упал на первое препятствие. Я пытаюсь преобразовать c-строку в двоичное представление целого числа, которое, вероятно, будет содержать больше битов, чем может вместить int (теоретически это может быть произвольное количество битов). По сути, я хочу создать массив long, который будет содержать двоичное представление числа, содержащегося в строке, с индексом 0, являющимся наименее значимой «конечностью» числа. Я предполагаю, что число в базовой десятке.
Я уже изучал использование кода из GMP, но он неоправданно сложен для моих нужд и содержит огромное количество зависимого от платформы кода.
Любая помощь будет отличной! Если вам нужно больше деталей, дайте мне знать.
Решение
Как сказал @SteveJessop
class Number {
public:
Number();
void FromString( const char * );
void operator *= ( int );
void operator += ( int );
void operator = ( int );
}
Number::FromString( const char * string )
{
*this = 0;
while( *string != '\0' ) {
*this *= 10;
*this += *string - '0';
string++;
}
}
Другие решения
Первое, что вы хотите сделать, это иметь работающий тестовый движок. Это умопомрачительный, простой для понимания, арифметический движок произвольной точности.
Цель этого двигателя в несколько раз. Во-первых, это делает преобразование строк в целые числа произвольной точности действительно простым. Во-вторых, это средство для проверки ваших более поздних улучшенных двигателей. Даже если это действительно медленно, вы будете более убеждены, что это правильно (а наличие двух независимых реализаций означает, что ошибки в одном случае могут быть обнаружены в другом, даже если вы не уверены в этом).
Предполагает short не менее 16 бит и char не менее 8 (используйте фактический int_8 типы стилей, если ваш компилятор их поддерживает)
short Add(unsigned char left, unsigned char right, unsigned char extra=0) { return unsigned short(left)+unsigned short(right)+unsigned short(extra); }
unsigned short Multiply(unsigned char left, unsigned char right) { return unsigned short(left)*unsigned short(right); }
std::pair<unsigned char,unsigned char> CarryCalc(unsigned short input) {
std::pair<unsigned char,unsigned char> retval;
retval.first = input & (1<<8-1);
retval.second = input>>8;
return retval;
}
struct BigNum {
std::vector<char> base256;
BigNum& operator+=( BigNum const& right ) {
if (right.base256.size() > base256.size())
base256.resize(right.base256.size());
auto lhs = base256.begin();
auto rhs = right.base256.begin();
char carry = 0;
for(; rhs != right.base256.end(); ++rhs, ++lhs) {
auto result = CarryCalc( Add( *lhs, *rhs, carry ) );
*lhs = result.first;
carry = result.second;
}
while( carry && lhs != base256.end() ) {
auto result = CarryCalc( Add( *lhs, 0, carry ) );
*lhs = result.first;
carry = result.second;
}
if (carry)
base256.push_back(carry);
return *this;
}
BigNum& scaleByChar( unsigned char right ) {
char carry = 0;
for(auto lhs = base256.begin(); lhs != base256.end(); ++lhs) {
unsigned short product = Multiply( *lhs, right );
product += carry;
auto result = CarryCalc( product );
*lhs = result.first;
carry = result.second;
}
if (carry)
base256.push_back(carry);
return *this;
}
BigNum& shiftRightBy8BitsTimes( unsigned int x ) {
if (x > base256.size()) {
base256.clear();
return *this;
}
base256.erase( base256.begin(), base256.begin()+x) )
return *this;
}
// very slow, O(x * n) -- should be O(n) at worst
BigNum& shiftLeftBy8BitsTimes( unsigned int x ) {
while( x != 0 ) {
base256.insert( base256.begin(), 0 );
--x;
}
return *this;
}
// very slow, like O(n^3) or worse (should be O(n^2) at worst, fix shiftLeft)
BigNum& operator*=( BigNum const& right ) {
unsigned int digit = 0;
BigNum retval;
while (digit < right.base256.size()) {
BigNum tmp = *this;
tmp.shiftLeftBy8BitsTimes( digit );
tmp.scaleByChar( right.base256[digit] );
retval += tmp;
++digit;
}
*this = retval;
return *this;
}
};
это быстрый и грязный целочисленный тип произвольной точности (даже не скомпилированный) с ужасной производительностью. Протестируйте что-то подобное, убедите себя в том, что оно прочное, а затем наращивайте.
Большая часть вашего кода может принять рассматриваемый класс BigNum в качестве аргумента шаблона, так что вы можете сделать один и тот же алгоритм с двумя различными реализациями и сравнить результаты для целей тестирования.
Да, и еще один совет — написать шаблонный класс, который «улучшает» библиотеку произвольной точности с помощью CRTP. Цель состоит только в том, чтобы написать *=, +=, unary -, и возможно /= и немного shift_helper а также compare_helper функции, а остальные ваши методы автоматически пишутся для вас шаблоном. Поместив шаблон в одно место, вы сможете поддерживать более одной версии вашего BigNum класс: наличие нескольких версий очень важно для тестирования.