如何将大整数转换为基数 2^32？

Question

首先，我是为自己做这件事，所以请不要建议“使用 GMP / xint / bignum”（如果它适用的话）。

我正在寻找一种将大整数（例如超过 9000 位数字）转换为 2³² 表示形式的 int32 数组的方法。这些数字将以 10 为基数的字符串开始。

例如，如果我想将刚刚超过 INT_MAX 的 string a = "4294967300"（以 10 为基数）转换为新的基数 2^{32< /sup> 数组，则为 int32_t b[] = {1,5}。如果 int32_t b[] = {3,2485738}，则以 10 为基数的数字将为 3 * 2^32 + 2485738。显然，我将使用的数字甚至超出了 int64 的范围，因此我无法准确地将字符串转换为整数并修改我的成功方式。}

我有一个以 10 为基数进行减法的函数。现在我想我只需执行 subtraction(char* number, "2^32") 并计算在得到 a 之前有多少次负数，但对于较大的数字可能需要很长时间。

有人可以建议一种不同的转换方法吗？谢谢。

编辑
抱歉，如果您没有看到该标签，我正在使用 C++

Answer 1

假设您的 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 2

要将基数为 10 的字符串转换为您的编号系统，请从零开始继续将每个基数 10 数字与 10 相加和相乘。每次有进位时，都会向基数 2^32 数组添加一个新数字。

Answer 3

最简单（不是最有效）的方法是编写两个函数，一个将一个大数乘以一个 int，另一个将一个 int 添加到一个大数。如果您忽略有符号数字引入的复杂性，代码看起来像这样：（

为了清楚起见，编辑使用向量并为实际问题添加代码）

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 4

我认为Docjar：gnu/java/math/MPN.java 可能包含您要查找的内容，特别是 public static int set_str (int dest[], byte[] str, int str_len, int base) 的代码。

Answer 5

首先将数字转换为二进制。从右边开始，每组 32 位都是一个 base2^32 数字。