0

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

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

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

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

有人可以提出不同的转换方法吗？谢谢。

编辑
对不起，如果您没有看到标签，我正在使用C++

4

5 回答 5

1

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

于 2011-11-02T21:25:39.070 回答
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;
}

这两个都只用于未签名。

于 2011-11-02T21:32:18.730 回答
1

最简单（不是最有效）的方法是编写两个函数，一个将大数乘以 int，另一个将 int 与大数相加。如果忽略有符号数字带来的复杂性，代码如下所示：

（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;
    }
}
于 2011-11-02T21:42:02.017 回答
0

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

于 2011-11-02T21:27:45.663 回答
0

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

于 2011-11-02T21:28:50.890 回答