Преобразовать восьмеричное представление числа в десятичное

Question

Предположим, что у каждого есть вектор или массив из N элементов (N может быть очень большим), содержащих восьмеричное представление неотрицательного целого числа.Как мне получить десятичное представление числа из этого массива?Код должен быть действительно быстрым.

РЕДАКТИРОВАТЬ: массив A из N элементов содержит восьмеричное представление неотрицательного целого числа 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

Преобразование восьмеричной в десятичную точность Arbitray довольно раздражает, поскольку нет способа локализовать вычисления. Другими словами, изменение самой значимой цифры восьмеричного числа изменит даже самую младшую цифру в десятичном представлении.

Тем не менее, я думаю, что я бы преобразовал восьмеричное число в, скажем, число base-1000000000, а затем напечатал бы это (это вместо тривиальной проблемы, каждая цифра base-1000000000 просто отображается тривиально в 9 цифр base-10) .

Преобразование в base-1000000000 просто, потому что вам нужно только поддерживать увеличение и умножение на два (просто рассмотрите вход как двоичный с тремя битами для каждой восьмеричной цифры).

EDIT

Я пытался реализовать его на 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;
}

На моем ПК время преобразования восьмизначного восьмеричного числа в десятичное (в результате 72246 цифр) составляет около 1,2 секунды. Делая то же самое, используя python eval / str, время составляет около 3 секунд. Используемое число было "01234567" * 10000.

Приведенный выше код использует 100 000 000 в качестве основы, чтобы он мог обрабатывать одну цифру (3 бита) за раз с 32-разрядной арифметикой, не переполняющейся промежуточными результатами. Я попытался также использовать 64-битные целые или 53-битную целую часть double, но код выполнялся всегда медленнее, чем в этом случае (одна из причин, вероятно, - это деление во внутреннем цикле, которое можно преобразовать в умножение в 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;
    }
}