c++ - 将数字 vector 从基数转换为基数

Question

如何转换 vector<int>在基地a至 vector<int>在基地b不使用像 gmp 这样的库？
包含数字的数字。 a和 b小于 1024。a可以小于或大于 b .
我考虑过使用标准的基本转换算法，但数字甚至不适合 long long .

Answer 1

基本上，您要做的是在基数 a 中实现 div/mod b，然后对源编号重复执行此操作，从而构建目标编号。当 b < a 时，经典的长除法算法是执行此操作的最简单和最有效的方法，因为您将始终处理个位数。当 b > a 时，有点棘手；您可以使用经典的长除法，或者先隐式地将数字转换为基数 a^k，其中 a^k >= b 并适合 int(平凡的转换)，然后使用个位数长除法转换为 b .

当然，如果 a == b^k 或 a^k == b(一个基数是另一个基数的整数次方)，这很简单，因为您根本不需要除法。很大程度上取决于“a”和“b”是不会改变的实际常量，还是它们是变量。

template<int A, int B> int divmod(std::vector<int> &a) {
    // a is a vector of digits in base A
    // divide a by B in place, returning the remainder
    // implementation left as an exercise for the reader
}

template<int A, int B> std::vector<int> cvtBase(std::vector<int> a) {
    // a is a vector of digits in base A
    // convert it to a vector of digits in base B
    // vectors are in little endian order (least significant digit first)
    std::vector<int> b;
    do {
        b.push_back(divmod<A,B>(a));
    } while (!isZero(a));
    return b;
}