如何将 Biginteger 转换为字符串

Question

我有一个包含数位的向量，向量代表以 2^32 为底的系统中的大整数。例如：

vector <unsigned> vec = {453860625, 469837947, 3503557200, 40}

这个向量表示这个大整数：

base = 2 ^ 32
3233755723588593872632005090577 = 40 * base ^ 3 + 3503557200 * base ^ 2 + 469837947 * base + 453860625

如何在字符串中获取这个十进制表示形式？

Answer 1

这是一种做你想做的事情的低效方法，从表示任意大小整数的字值向量中获取十进制字符串。

我更愿意将其实现为 class，以便更好地封装，因此可以添加数学运算符，但为了更好地符合问题，这只是一堆用于操纵 std::vector<unsigned> 对象。但是，这确实使用了 typedef BiType 作为 std::vector<unsigned> 的别名。

执行二进制除法的函数构成了这段代码的大部分。其中大部分重复使用 std::bitset 可以完成的工作，但对于任意大小的位集，作为 unsigned 单词的向量。如果您想提高效率，请插入一个按字而不是按位进行运算的除法算法。此外，除法代码是通用的，当它只用于除以 10 时，因此您可以将其替换为专用除法代码。

该代码通常假定一个 unsigned 单词的向量，并且基数是最大 unsigned 值加一。对于较小的基数或不是 2 的幂的基数（二元除法要求基数是 2 的幂数），无论出现什么问题，我都留下了评论。

此外，我只测试了 1 个案例，即您在 OP 中提供的案例——这是新的、未经验证的代码，因此您可能需要进行更多测试。如果您发现问题案例，我很乐意在这里修复错误。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

namespace bigint {
using BiType = std::vector<unsigned>;

// cmp compares a with b, returning 1:a>b, 0:a==b, -1:a<b
int cmp(const BiType& a, const BiType& b) {
    const auto max_size = std::max(a.size(), b.size());
    for(auto i=max_size-1; i+1; --i) {
        const auto wa = i < a.size() ? a[i] : 0;
        const auto wb = i < b.size() ? b[i] : 0;
        if(wa != wb) { return wa > wb ? 1 : -1; }
    }
    return 0;
}

bool is_zero(BiType& bi) {
    for(auto w : bi) { if(w) return false; }
    return true;
}

// canonize removes leading zero words
void canonize(BiType& bi) {
    const auto size = bi.size();
    if(!size || bi[size-1]) return;
    for(auto i=size-2; i+1; --i) {
        if(bi[i]) {
            bi.resize(i + 1);
            return;
        }
    }
    bi.clear();
}

// subfrom subtracts b from a, modifying a
// a >= b must be guaranteed by caller
void subfrom(BiType& a, const BiType& b) {
    unsigned borrow = 0;
    for(std::size_t i=0; i<b.size(); ++i) {
        if(b[i] || borrow) {
            // TODO: handle error if i >= a.size()
            const auto w = a[i] - b[i] - borrow;
            // this relies on the automatic w = w (mod base),
            // assuming unsigned max is base-1
            // if this is not the case, w must be set to w % base here
            borrow = w >= a[i];
            a[i] = w;
        }
    }
    for(auto i=b.size(); borrow; ++i) {
        // TODO: handle error if i >= a.size()
        borrow = !a[i];
        --a[i];
        // a[i] must be set modulo base here too
        // (this is automatic when base is unsigned max + 1)
    }
}

// binary division and its helpers: these require base to be a power of 2
// hi_bit_set is base/2
// the definition assumes CHAR_BIT == 8
const auto hi_bit_set = unsigned(1) << (sizeof(unsigned) * 8 - 1);  

// shift_right_1 divides bi by 2, truncating any fraction
void shift_right_1(BiType& bi) {
    unsigned carry = 0;
    for(auto i=bi.size()-1; i+1; --i) {
        const auto next_carry = (bi[i] & 1) ? hi_bit_set : 0;
        bi[i] >>= 1;
        bi[i] |= carry;
        carry = next_carry;
    }
    // if carry is nonzero here, 1/2 was truncated from the result
    canonize(bi);
}

// shift_left_1 multiplies bi by 2
void shift_left_1(BiType& bi) {
    unsigned carry = 0;
    for(std::size_t i=0; i<bi.size(); ++i) {
        const unsigned next_carry = !!(bi[i] & hi_bit_set);
        bi[i] <<= 1; // assumes high bit is lost, i.e. base is unsigned max + 1
        bi[i] |= carry;
        carry = next_carry;
    }
    if(carry) { bi.push_back(1); }
}

// sets an indexed bit in bi, growing the vector when required
void set_bit_at(BiType& bi, std::size_t index, bool set=true) {
    std::size_t widx = index / (sizeof(unsigned) * 8);
    std::size_t bidx = index % (sizeof(unsigned) * 8);
    if(bi.size() < widx + 1) { bi.resize(widx + 1); }
    if(set) { bi[widx] |= unsigned(1) << bidx; }
    else    { bi[widx] &= ~(unsigned(1) << bidx); }
}

// divide divides n by d, returning the result and leaving the remainder in n
// this is implemented using binary division
BiType divide(BiType& n, BiType d) {
    if(is_zero(d)) {
        // TODO: handle divide by zero
        return {};
    }
    std::size_t shift = 0;
    while(cmp(n, d) == 1) { 
        shift_left_1(d);
        ++shift;
    }
    BiType result;
    do {
        if(cmp(n, d) >= 0) {
            set_bit_at(result, shift);
            subfrom(n, d);
        }
        shift_right_1(d);
    } while(shift--);
    canonize(result);
    canonize(n);
    return result;
}

std::string get_decimal(BiType bi) {
    std::string dec_string;

    // repeat division by 10, using the remainder as a decimal digit
    // this will build a string with digits in reverse order, so
    // before returning, it will be reversed to correct this.
    do {
        const auto next_bi = divide(bi, {10});
        const char digit_value = static_cast<char>(bi.size() ? bi[0] : 0);
        dec_string.push_back('0' + digit_value);
        bi = next_bi;
    } while(!is_zero(bi));
    std::reverse(dec_string.begin(), dec_string.end());
    return dec_string;
}

}

int main() {
    bigint::BiType my_big_int = {453860625, 469837947, 3503557200, 40};
    auto dec_string = bigint::get_decimal(my_big_int);
    std::cout << dec_string << '\n';
}

输出：

3233755723588593872632005090577

如何将 Biginteger 转换为字符串

How to convert Biginteger to string

c++

biginteger