Как преобразовать большие целые числа в базу 2 ^ 32?

Question

Во-первых, я делаю это для себя, поэтому, пожалуйста, не предлагайте "использовать GMP / xint / bignum" (если это вообще применимо).

Я ищу способ конвертировать большиецелые числа (скажем, БОЛЕЕ 9000 цифр) в массиве int32 с 2 ³² представлениями.Числа начинаются как строки 10-й строки.

Например, если бы я хотел преобразовать string a = "4294967300" (в базе 10), которая составляет чуть более INT_MAX, в новую базу 2 ³² массив, это будет int32_t b[] = {1,5}.Если int32_t b[] = {3,2485738}, базовое число 10 будет 3 * 2^32 + 2485738.Очевидно, что числа, с которыми я буду работать, находятся за пределами диапазона даже int64, поэтому я не могу точно превратить строку в целое число и изменить мой путь к успеху.

У меня есть функция, которая выполняет вычитание в базе10. Прямо сейчас я думаю, что просто сделаю subtraction(char* number, "2^32") и посчитаю, сколько раз я получу отрицательное число, но это может занять много времени для больших чисел.

Может кто-нибудь предложитьдругой метод конвертации?Спасибо.

РЕДАКТИРОВАТЬ
Извините, если вы не видите тег, я работаю в C ++

Answer 1

Самый простой (не самый эффективный) способ сделать это - написать две функции: одну для умножения большого числа на целое и одну для добавления целого числа к большому. Если вы игнорируете сложности, представленные числами со знаком, код выглядит примерно так:

(ИЗМЕНЕНО для использования vector для ясности и добавления кода для актуального вопроса)

void mulbig(vector<uint32_t> &bignum, uint16_t multiplicand)
{
    uint32_t carry=0;
    for( unsigned i=0; i<bignum.size(); i++ ) {
        uint64_t r=((uint64_t)bignum[i] * multiplicand) + carry;
        bignum[i]=(uint32_t)(r&0xffffffff);
        carry=(uint32_t)(r>>32);
    }
    if( carry )
        bignum.push_back(carry);
}

void addbig(vector<uint32_t> &bignum, uint16_t addend)
{
    uint32_t carry=addend;
    for( unsigned i=0; carry && i<bignum.size(); i++ ) {
        uint64_t r=(uint64_t)bignum[i]  + carry;
        bignum[i]=(uint32_t)(r&0xffffffff);
        carry=(uint32_t)(r>>32);
    }
    if( carry )
        bignum.push_back(carry);
}

Затем реализация atobignum () с использованием этих функций тривиальна:

void atobignum(const char *str,vector<uint32_t> &bignum)
{
    bignum.clear();
    bignum.push_back(0);
    while( *str ) {
        mulbig(bignum,10);
        addbig(bignum,*str-'0');
        ++str;
    }
}

Answer 2

Предполагая, что в вашем классе bignum уже есть умножение и сложение, все довольно просто:

 bignum str_to_big(char* str) {
     bignum result(0);
     while (*str) {
         result *= 10;
         result += (*str - '0');
         str = str + 1;
     }
     return result;
 }

Преобразование другим способом - та же концепция, но требует деления и по модулю

std::string big_to_str(bignum num) {
    std::string result;
    do {
        result.push_back(num%10);
        num /= 10;
    } while(num > 0);
    std::reverse(result.begin(), result.end());
    return result;
}

Оба из них только для неподписанных.

Answer 3

Чтобы преобразовать из базовых 10 строк в вашу систему нумерации, начиная с нуля, продолжайте добавлять и умножать каждую базовую 10 цифру на 10. Каждый раз, когда у вас есть перенос, добавляйте новую цифру в ваш массив 2 ^ 32.

Answer 4

Начните с преобразования числа в двоичное.Начиная справа, каждая группа из 32 битов представляет собой одну цифру base2 ^ 32.

Answer 5

Я думаю, Docjar: gnu / java / math / MPN.java может содержать то, что вы ищете, в частности код public static int set_str (int dest[], byte[] str, int str_len, int base).