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

Question

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

编辑： 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

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

也就是说，我想我会将八进制数转换为基数 1000000000 的数字，然后打印它（这是一个微不足道的问题，每个基数 1000000000 的数字只是简单地映射到 9 个基数 10 的数字）。

转换为基数 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 作为基数，以便一次可以处理一位数字（3 位），并且 32 位算术不会因中间结果而溢出。我还尝试使用 64 位整数或 double 的 53 位整数部分，但代码的运行速度总是比本例慢（原因之一可能是内部循环中的除法可以转换为32 位情况下的乘法）。

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

Answer 2

这就是我想出的：

template<typename Iter>
int read_octal(Iter begin, Iter end)
{
    int x = 0;
    int f = 1;
    for (; begin != end; ++begin)
    {
        x += *begin * f;
        f *= 8;
    }
    return x;
}

int main()
{
    int test[] = {2, 6, 3};
    int result = read_octal(test + 0, test + 3);
    std::cout << result << '\n';
}

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

6k 到底是什么意思？一个 int 通常有 32 位，一个八进制数字有 3 位。因此，范围内的元素不能超过 10 个，否则 x 将溢出。

我在将十六进制字符串转换为其十进制表示形式时也遇到问题？

好吧，您总是可以自己编写一个函数来解析十六进制格式的字符串：

int parse_hex(const char* p)
{
    int x = 0;
    for (; *p; ++p)
    {
        x = x * 16 + digit_value(*p);
    }
    return x;
}

最可移植的 digit_value 版本是：

int digit_value(char c)
{
    switch (c)
    {
        case '0': return 0;
        case '1': return 1;
        case '2': return 2;
        case '3': return 3;
        case '4': return 4;
        case '5': return 5;
        case '6': return 6;
        case '7': return 7;
        case '8': return 8;
        case '9': return 9;
        case 'A': 
        case 'a': return 10;
        case 'B': 
        case 'b': return 11;
        case 'C': 
        case 'c': return 12;
        case 'D': 
        case 'd': return 13;
        case 'E': 
        case 'e': return 14;
        case 'F': 
        case 'f': return 15;
    }
}