c++ - 将数字的八进制表示形式转换为十进制

Question

假设有一个包含 N 个元素(N 可以非常大)的 vector 或数组，其中包含一个非负整数的八进制表示。如何从此数组中获取数字的十进制表示形式？代码必须非常快。

编辑:N 个元素的数组 A 包含一个非负整数 K 的八进制表示，即 A 的每个元素都属于区间 [0; 7](包括两端)

例子:A[0] = 2; A[1] = 6; A[2] = 3

现在一个简单的计算是 2*8pow0 + 6*8pow1 + 3*8pow2 = 2+ 48+ 192 = 242

我试过了，但它似乎不适用于大输入 > 6K

//vector<int> A is the input
using namespace std;
vector<int>::iterator it = A.begin();

unsigned int k = 0;
unsigned int x = 0;
while(it < A.end()){
   x = x | (*it<<3*k);
   k++;
   it++;
}

我在将十六进制字符串转换为其十进制表示形式时也遇到了问题？这是在 C++ 中执行此操作的正确方法吗: //假设 S 是包含十六进制表示的输入字符串 //像F23

std::stringstream ss;
ss << std::hex << S;
ss >> x;

Answer 1

任意精度八进制到十进制的转换相当烦人，因为无法本地化计算。换句话说，八进制数最高有效位的变化甚至会改变十进制表示中最低有效位。

也就是说，我认为我会将八进制数转换为 base-1000000000 数字，然后打印它(这是一个微不足道的问题，每个 base-1000000000 数字只是简单地映射到 9 base-10 数字) .

转换为 base-1000000000 很简单，因为您只需要支持递增和乘以 2(只需将输入视为二进制，每个八进制数字为三位)。

编辑

我尝试用 C++ 实现它，这是结果代码

#include <stdio.h>
#include <vector>

int main(int argc, const char *argv[]) {
    // Base 100,000,000 accumulator
    // Initialized with one digit = 0
    std::vector<unsigned> big(1);
    const unsigned DIGIT = 100000000;

    for (int c=getchar(); c >= '0' && c <= '7'; c=getchar()) {
        // Multiply accumulator by 8 and add in incoming digit
        int carry = c - '0';
        for (int i=0,n=big.size(); i<n; i++) {
            unsigned x = big[i] * 8 + carry;
            carry = x / DIGIT;
            big[i] = x - carry * DIGIT;
        }
        if (carry) big.push_back(carry);
    }

    // Output result in decimal
    printf("%i", big.back());
    for (int i=int(big.size())-2; i>=0; i--) {
        printf("%08i", big[i]);
    }
    putchar('\n');
    return 0;
}

在我的 PC 上，将 80,000 位八进制数转换为十进制数(生成 72246 位数字)的时间约为 1.2 秒。使用 python eval/str 做同样的事情时间大约是 3 秒。使用的数字是 "01234567"* 10000。

上面的代码使用 100,000,000 作为基数，因此它可以使用 32 位算术一次处理一个数字(3 位)，而不会因中间结果而溢出。我也尝试使用 64 位整数或 double 的 53 位整数部分，但代码运行速度总是比这种情况慢(一个原因可能是内部循环中的除法可以转换为32 位情况下的乘法)。

这仍然是一个简单的 O(n^2) 实现，需要很长时间才能转换 10,000,000 位八进制数。